Mixing times for neighbour transposition shuffles on graphs
Mixing times for neighbour transposition shuffles on graphs
复制标题
图上相邻转置洗牌的混合时间
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Stefan Erikshed
中科院分区：
文献类型：
--
作者：
Stefan Erikshed
本文将研究对称群Sn上的马尔可夫链，即n个不同对象的排列集合。状态空间为Sn的马尔可夫链通常称为洗牌链。因此状态空间就是n张牌的重排序。这里考虑某种类型的洗牌链；图上的邻接换位。这是普通随机置换洗牌的推广。普通随机换位洗牌的每一步都是随机选择牌组中的任意一对牌，然后交换它们的位置。图上的相邻转置意味着n张牌被放置在n顶点图的顶点上。在每一步中，图中相邻的一对牌（即与边相连的两张牌）被选择并调换。如果图是连通的，那么牌组最终会很好地混合在一起。换句话说，链的分布收敛于Sn上的均匀性。本文研究了两类图（棒棒糖图和随机图G(n, p)）上的洗牌收敛到均匀性的速度。更准确地说，确定了这些洗牌的混合时间界限。混合时间是马尔可夫链在接近平稳均匀分布时的步数。与通常处理收敛速率问题时一样，我们令|Sn|→∞，在n内得到渐近结果。导出了棒棒糖图上相邻转置的混合时间的下界和上界，均为n log n阶。进一步，建立了连通随机图上相邻转置的混合时间的n log n阶下界。证明了直径有界随机图的同阶上界。
This thesis will treat Markov chains on the symmetric group Sn, i.e. the set of permutations of n distinct objects. Markov chains with the state space Sn are often referred to as card shuffling chains. The state space is thus the reorderings of a deck of n cards. A certain type of card shuffling chains is considered here; neighbour transpositions on graphs. This is a generalization of ordinary random transpositions shuffle. Each step of the ordinary random transpositions shuffle consists of randomly selecting any pair of cards in the deck and then switch their places. Neighbour transpositions on a graph means that the n cards is placed on the vertices of a n-vertex graph. At each step a neighbour pair of cards in the graph (i.e. two cards at positions connected with an edge) is selected and transposed. If the graph is connected, the deck will eventually be well mixed. In other words, the distribution of the chain converges to uniformity on Sn. This thesis deals with the rate of convergence to uniformity for card shuffling on two families of graphs, lollipop graphs and random graphs, G(n, p). More precisely, bounds on the mixing time of these shuffles is determined. The mixing time is the number of steps of the Markov chain until it is close to its stationary uniform distribution. As usual when dealing with convergence rate problems we let |Sn| → ∞, yielding asymptotic results in n. Lower and upper bounds, both of order n log n, on the mixing time for neighbour transpositions on lollipop graphs is derived. Further, lower bounds of order n log n, on the mixing time for neighbour transpositions on connected random graphs is established. Upper bounds of the same order is proved for random graphs with bounded diameter.