Repository logo
 

A permuted random walk exits faster

Accepted version
Peer-reviewed

Type

Article

Change log

Authors

Pymar, Richard 
Sousi, P 

Abstract

Let σ be a permutation of {0, . . . , n}. We consider the Markov chain X which jumps from k̸=0,ntoσ(k+1)orσ(k−1),equallylikely. WhenX isat0itjumpstoeitherσ(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 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-directed graph is maximized when the graph is the line [0, n] ∩ Z with d − 2 self-loops at every vertex and d − 1 self-loops at 0 and n.

Description

Keywords

Journal Title

ALEA : Latin American Journal of Probability and Mathematical Statistics

Conference Name

Journal ISSN

Volume Title

11

Publisher

Instituto Nacional de Matemática Pura e Aplicada

Publisher DOI