MCMC for conditional Bernoullis

Jeremy Heng, Pierre Jacob [currently in Paris!] and Nianqiao Ju are in a recent arXival considering the simulation of a conditional Bernoulli, namely generating a vector of N Bernoullis with different probabilities under the constraint that their sum is fixed as I. Rather than going for a perfect simulator, with cost O(NI), they opt for the simplest of MCMC samplers, where a 0 and a 1 entries are exchanged at random. In connection with a recent spate of MCMC works using coupling, they establish convergence in O(N log N) steps, even when the probabilities are arbitrarily close to zero and one. Including the case when they are Uniformly generated. From a mundane perspective, I wonder at the appeal of using the probabilities to select the exchange pair. I realise sorting the probabilities is already of order O(N log N) avoiding selecting highly probable 1’s and highly probable 0’s should speed up converge, unless the gain is negligible. And to link MCMC and exact simulation in this setting, what would the cost of perfect sampling by sampling from the past be? Presumably much higher since there is little chance a total ordering can be found on the starting states.

One Response to “MCMC for conditional Bernoullis”

  1. Pierre Jacob Says:

    Thanks Christian for the feedback! The co-author is Jeremy Heng, not Jimmy Heng :-)
    https://sites.google.com/view/jeremyheng/

    Yes I imagine there might be possible gains over this very simple MCMC method, but in terms of scaling with N, this one seems to do the job. We conjecture that N log N is essentially the best possible dependency in N… at least it’s hard to imagine anything sub-linear. As you noticed, the difficulty in doing something more clever (taking the probabilities into account) is that the cost per iteration would probably increase, so it might be worth it, but it’s not obvious.

    I will talk about this and other related problems at the Seminaire Parisien de Statistique on March 22 (which should be virtual and eventually announced here https://sites.google.com/site/semstats/ann%C3%A9e-2020-2021).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.