论文标题
一个简单的马尔可夫链，用于以其总和为条件的独立伯努利变量
A simple Markov chain for independent Bernoulli variables conditioned on their sum
论文作者
论文摘要
我们考虑$ n $独立二进制变量的向量，每个变量的成功概率不同。矢量条件上的分布称为条件伯努利分布。假设$ n $转到无限且总和与$ n $成比例，那么精确的采样费用$ n^2 $，而使用“交换”的简单马尔可夫链蒙特卡洛算法每迭代持续成本。我们提供了该马尔可夫链以$ n \ log n $迭代顺序收敛的条件。我们的证明依赖于耦合和在空间的分区中定义为有利和不利对的辅助马尔可夫链。
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 $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.
