Mixing Time for a Random Walk on Rooted Trees
Mixing Time for a Random Walk on Rooted Trees
复制标题
在有根树上随机游走的混合时间
DOI：
10.37236/228
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Jason E. Fulman
中科院分区：
文献类型：
--
作者：
Jason E. Fulman
我们定义了$n$顶点上有根无标号树集的一个类似Plancherel测度，并定义了一个以该测度为平稳分布的马尔可夫链。利用对易关系的组合学，我们证明了阶数$n^2$步长是收敛到平稳分布的必要条件和充分条件。
We define an analog of Plancherel measure for the set of rooted unlabeled trees on $n$ vertices, and a Markov chain which has this measure as its stationary distribution. Using the combinatorics of commutation relations, we show that order $n^2$ steps are necessary and suffice for convergence to the stationary distribution.