How to get a perfectly random sample from a generic Markov chain and generate a random spanning tree of a directed graph
How to get a perfectly random sample from a generic Markov chain and generate a random spanning tree of a directed graph
复制标题
DOI：
10.1006/jagm.1997.0917
复制
发表时间：
1998-05-01
期刊：
影响因子：
--
通讯作者：
Wilson, DB
中科院分区：
文献类型：
--
作者：
Propp, JG;Wilson, DB
计算概率论中的一个普遍问题是根据链的稳态概率定律从马尔可夫链的状态空间生成随机样本。另一个问题是根据均匀分布，或更一般地根据由图或有向图的边上的权重给出的分布来生成图的随机生成树或有向图的生成树状。本文给出了这两个问题的算法，改进了早期的结果并利用了两个问题之间的对偶性。每一种新算法都取决于最近引入的过去耦合技术或循环擦除随机游走和“循环弹出”的相关概念。 (C) 1998 年学术出版社。
A general problem in computational probability theory is that of generating a random sample from the state space of a Markov chain in accordance with the steady-state probability law of the chain. Another problem is that of generating a random spanning tree of a graph or spanning arborescence of a directed graph in accordance with the uniform distribution, or more generally in accordance with a distribution given by weights on the edges of the graph or digraph. This article gives algorithms for both of these problems, improving on earlier results and exploiting the duality between the two problems. Each of the new algorithms hinges on the recently introduced technique of coupling from the past or on the linked notions of loop-erased random walk and "cycle popping." (C) 1998 Academic Press.