Title: Random sampling of contingency tables and partitions: Two practical examples of the Burnside process Show Chinese title

Title: 随机抽样列联表和划分：Burnside过程的两个实际例子

Abstract: This paper gives new, efficient algorithms for approximate uniform sampling of contingency tables and integer partitions. The algorithms use the Burnside process, a general algorithm for sampling a uniform orbit of a finite group acting on a finite set. We show that a technique called `lumping' can be used to derive efficient implementations of the Burnside process. For both contingency tables and partitions, the lumped processes have far lower per step complexity than the original Markov chains. We also define a second Markov chain for partitions called the reflected Burnside process. The reflected Burnside process maintains the computational advantages of the lumped process but empirically converges to the uniform distribution much more rapidly. By using the reflected Burnside process we can easily sample uniform partitions of size $10^{10}$. Show Chinese abstract

Abstract: 本文给出了用于近似均匀抽样列联表和整数分拆的新颖、高效算法。 这些算法使用了Burnside过程，这是一种用于采样有限群在有限集上作用的均匀轨道的通用算法。 我们表明，一种称为“lumping”的技术可以用来推导Burnside过程的有效实现。 对于列联表和分拆而言，lumped过程的每步复杂度远低于原始马尔可夫链。 我们还为分拆定义了一个称为反射Burnside过程的第二个马尔可夫链。 反射Burnside过程保持了lumped过程的计算优势，但经验上收敛到均匀分布的速度要快得多。 通过使用反射Burnside过程，我们可以轻松地抽样大小为$10^{10}$的均匀分拆。