文章基本信息

标题：A permuted random walk exits faster
本地全文：下载
作者：Richard Pymar ; Perla Sousi
期刊名称：Latin American Journal of Probability and Mathematical Statistics
电子版ISSN：1980-0436
出版年度：2014
卷号：XI
页码：185-195
出版社：Instituto Nacional De Matemática Pura E Aplicada
摘要：Let be a permutation of f0; : : : ; ng. We consider the Markov chain Xwhich jumps from k 6= 0; n to (k + 1) or (k 􀀀 1), equally likely. When X is at 0it jumps to either (0) or (1) equally likely, and when X is at n it jumps to either(n) or (n􀀀1), equally likely. We show that the identity permutation maximizesthe expected hitting time of n, when the walk starts at 0. More generally, we provethat the hitting time of a random walk on a strongly connected d-regular directedgraph is maximized when the graph is the line [0; n] \ Z with d 􀀀 2 self-loops atevery vertex and d 􀀀 1 self-loops at 0 and n.
关键词：Markov chain; directed graph; hitting time.