科研之友
微信
新浪微博
Facebook
分享链接
摘要
Let sigma be a permutation of {0,...,n}. We consider the Markov chain X which jumps from k not equal 0, n to sigma(k + 1) or sigma (k + 1), equally likely. When X is at 0 it jumps to either sigma(0) or sigma(1) equally likely, and when X is at n it jumps to either sigma(n) or sigma(n - 1), equally likely. We show that the identity permutation maximizes the expected hitting time of n, when the walk starts at 0. More generally, we prove that the hitting time of a random walk on a strongly connected d-regular directed graph is maximized when the graph is the line [0,n] boolean AND Z with d - 2 self-loops at every vertex and d - 1 self-loops at 0 and n.
- 出版日期2014
