Faster random generation of linear extensions
Faster random generation of linear extensions
复制标题
更快地随机生成线性扩展
DOI：
10.1016/s0012-365x(98)00333-1
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
M. Dyer
中科院分区：
文献类型：
--
作者：
Russ Bubley;M. Dyer
本文研究了近似抽样理论中的经典问题--偏序的线性扩张集上的(几乎)一致抽样问题。以前的技术要么依赖于深刻的几何论证，要么不能完全通用。最近，焦点集中在卡尔扎诺夫和卡奇扬马尔科夫链上。本文定义了一个稍有不同的马尔可夫链，并用路径耦合的方法给出了它的快速混合的一个非常简单的证明。证明了该链的混合时间为O(N3logn)，大大改进了以往Karzanov链和Khchiyan链的最优界O(N5logn)。我们还展示了一个经典的度量，斯皮尔曼定律，可以用换位来重新表述。
This paper examines the problem of sampling (almost) uniformly from the set of linear extensions of a partial order, a classic problem in the theory of approximate sampling. Previous techniques have relied on deep geometric arguments, or have not worked in full generality. Recently, focus has centred on the Karzanov and Khachiyan Markov chain. In this paper, we define a slightly different Markov chain, and present a very simple proof of its rapid mixing, using the method of path coupling. We show that this chain has mixing time O(n3logn), which significantly improves the previous best bound for this problem, which was a bound of O(n5logn), for the Karzanov and Khachiyan chain. We also show how a classical metric, Spearman's footrule, may be reformulated in terms of transpositions.