A permuted random walk exits faster

zbMATH Open1295.60084arXiv1304.6704MaRDI QIDQ5413239FDOQ5413239

Authors: Richard Pymar, Perla Sousi 

Publication date: 29 April 2014

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$.

Full work available at URL: https://arxiv.org/abs/1304.6704

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

zbMATH Keywords

Markov chainhitting timedirected graph

Mathematics Subject Classification ID

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

Cited In (5)

• Many Random Walks Are Faster Than One
• Correction to: ``Speeding up Markov chains with deterministic jumps
• Permuted random walk exits typically in linear time
• Speeding up Markov chains with deterministic jumps
• 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)