ASYMPTOTIC EVOLUTION OF ACYCLIC RANDOM MAPPINGS
ASYMPTOTIC EVOLUTION OF ACYCLIC RANDOM MAPPINGS
复制标题
无环随机映射的渐近演化
DOI：
10.1214/ejp.v12-437
复制
发表时间：
2007
影响因子：
1.4
通讯作者：
Tye Lidman
中科院分区：
文献类型：
--
作者：
S. Evans;Tye Lidman
从一个$n$元素集到其自身的非循环映射是一个映射$\varphi$，使得如果$\varphi^k（x）= x$对于某个$k$和$x$，则$\varphi（x）= x$。等价地，对于足够大的$\ell$，$\varphi^\ell = \varphi^{\ell+1} = \ldots$。我们研究了马氏链序列在这类映射集合上的n \rightarrow \infty$行为。在链的每一步，在$n$元素集中的一个点被随机均匀地选择，并且通过用一个新的随机独立均匀地选择的点替换该点的当前图像来修改当前映射，条件是所得到的映射再次是非循环的。我们可以将非循环映射表示为有向图（这样的图将是有根树的集合），并将这些有向图视为具有某些额外结构的度量空间。非正式的计算表明，与马尔可夫链相关联的度量空间值过程，经过适当的时间和“空间”重新标度后，应收敛为$n \rightarrow \infty$到一个真实的树（$R$-tree）值马尔可夫过程，该过程相对于标准反射布朗桥自然诱导的测度是可逆的。虽然我们没有证明这样的极限定理，我们使用狄利克雷形式的方法来构建一个马尔可夫过程，这是亨特相对于一个合适的Gromov-Hausdorff度量和发展的启发式参数所建议的动态。这个过程类似于埃文斯和温特早期的工作中出现的一个类似的非正式限制的马尔可夫链相关的子树修剪和嫁接树（SPR）重排从遗传学的。
An acyclic mapping from an $n$ element set into itself is a mapping $\varphi$ such that if $\varphi^k(x) = x$ for some $k$ and $x$, then $\varphi(x) = x$. Equivalently, $\varphi^\ell = \varphi^{\ell+1} = \ldots$ for $\ell$ sufficiently large. We investigate the behavior as $n \rightarrow \infty$ of a sequence of a Markov chain on the collection of such mappings. At each step of the chain, a point in the $n$ element set is chosen uniformly at random and the current mapping is modified by replacing the current image of that point by a new one chosen independently and uniformly at random, conditional on the resulting mapping being again acyclic. We can represent an acyclic mapping as a directed graph (such a graph will be a collection of rooted trees) and think of these directed graphs as metric spaces with some extra structure. Informal calculations indicate that the metric space valued process associated with the Markov chain should, after an appropriate time and ``space'' rescaling, converge as $n \rightarrow \infty$ to a real tree ($R$-tree) valued Markov process that is reversible with respect to a measure induced naturally by the standard reflected Brownian bridge. Although we don't prove such a limit theorem, we use Dirichlet form methods to construct a Markov process that is Hunt with respect to a suitable Gromov-Hausdorff-like metric and evolves according to the dynamics suggested by the heuristic arguments. This process is similar to one that appears in earlier work by Evans and Winter as a similarly informal limit of a Markov chain related to the subtree prune and regraft tree (SPR) rearrangements from phylogenetics.