n维有向de Bruijn图和无向de Bruijn图上的随机游动(英文)

The Random Walks on n-dimensional de Bruijn Digraphs and Graphs

本文对有向和无向de Bruijn图上的随机游动进行了研究,得出了有向de Bruijn图上简单随机游动任意两点之间平均击中时间的显式表达式,并证明了有向和无向de Bruijn图上随机游动的快速收敛性.

In this paper, we provide the explicit formula of the expected hitting times for random walk on de Bruijn graphs. Furthermore we show that both random walks on directed and undirected de Bruijn graphs are rapidly mixing.