A simple Markov chain for independent Bernoulli variables conditioned on their sum

2020/12/05 by Jeremy Heng, Heng, Jeremy, Pierre Jacob +3 · 2 citations
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.2012.03103

openalex publication_date 2020/12/05 · openalex created_date 2020/12/21 · openalex updated_date 2026/07/28

Abstract

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², 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 N log N iterations. Our proof relies on couplings and an auxiliary Markov chain defined on a partition of the space into favorable and unfavorable pairs.

Cited by

• Sequential Monte Carlo algorithms for agent-based models of disease transmission
• Quo nomine vis vocari? A random-copying model explains the temporal sequence of papal names

Related

• A study of counts of Bernoulli strings via conditional Poisson processes
• Beyond Poisson Approximation: Sums of Markovian Bernoulli Variables with Applications to Brownian Motions and Branching Processes
• Tree Bounds for Sums of Bernoulli Random Variables: A Linear\n Optimization Approach
• Tight Probability Bounds with Pairwise Independence
• Parallel and interacting Markov chains Monte Carlo method