Random Random Walks on Zd 2
Random Random Walks on Zd 2
复制标题
Zd 2 上的随机随机游走
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
David Bruce Wilsondbwilson
中科院分区：
文献类型：
--
作者：
David Bruce Wilsondbwilson
我们通过在n个随机选择的并行向量类上放置边来考虑在d维二进制立方体Zd2上所需的图类上的随机行走。图的混合时间是随机行走在忘记起点并到达随机位置之前的步数。在本文中，我们通过找到这个混合时间的精确表达式来解决Diaconis问题，该表达式适用于所有的n > d和几乎所有向量类的选择。这个结果改进了以前的一些界限。我们的方法使用了计算机科学中通用哈希函数的概念，可以应用于其他阿贝尔群上的类似问题。
We consider random walks on classes of graphs de®ned on the ddimensional binary cube Zd2 by placing edges on n randomly chosen parallel classes of vectors. The mixing time of a graph is the number of steps of a random walk before the walk forgets where it started, and reaches a random location. In this paper we resolve a question of Diaconis by ®nding exact expressions for this mixing time that hold for all n > d and almost all choices of vector classes. This result improves a number of previous bounds. Our method, which has application to similar problems on other Abelian groups, uses the concept of a universal hash function, from computer science.