## MCMC for conditional Bernoullis

**J**eremy 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.

February 22, 2021 at 5:33 pm

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).