A permuted random walk exits faster

MaRDI QIDQ5413239zbMATH OpenFDO

Authors Richard Pymar, Perla Sousi

Publication date 29 April 2014

Full work available at URL https://arxiv.org/abs/1304.6704, http://alea.impa.br/articles/v11/11-05.pdf

zbMATH Keywords

directed graphhitting timeMarkov chain

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: Let $sigma$ be a permutation of $0,ldots,n$. We consider the Markov chain $X$ which jumps from $keq0,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 $$ with $d-2$ self-loops at every vertex and $d-1$ self-loops at 0 and $n$.

Recommendations

• Permuted random walk exits typically in linear time
• Maximum hitting time for random walks on graphs
• Hitting times for random walks on vertex-transitive graphs
• Random permutation graphs and related Markov chains
• scientific article; zbMATH DE number 2067820

Cited in

(5)

• Correction to: ``Speeding up Markov chains with deterministic jumps
• Speeding up Markov chains with deterministic jumps
• Permuted random walk exits typically in linear time
• Many Random Walks Are Faster Than One
• Random walks on regular trees can not be slowed down

This page was built for publication: A permuted random walk exits faster

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5413239)