A simple Markov chain for independent Bernoulli variables conditioned on their sum
Nianqiao Phyllis Ju, Purdue University
We consider a vector of N independent binary variables, each with a different probability of success. The distribution of the vector conditional on its sum is known as the conditional Bernoulli distribution. Assuming that N goes to infinity and that the sum is proportional to N, exact sampling costs order N^2, while a simple Markov chain Monte Carlo algorithm using ‘swaps’ has constant cost per iteration. We provide conditions under which this Markov chain converges in order NlogN iterations. Our proof relies on couplings and an auxiliary Markov chain defined on a partition of the space into favorable and unfavorable pairs. This talk is based on joint work with Jeremy Heng and Pierre Jacob.