A permuted random walk exits faster

Abstract

Let $\sigma$ be a permutation of $\{0,\dots ,n\}$. We consider the Markov chain $X$ which jumps from $k\ne 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$-directed graph is maximized when the graph is the line $[0,n]\cap \mathbb{Z}$ with $d-2$ self-loops at every vertex and $d-1$ self-loops at 0 and $n$.