Permuted random walk exits typically in linear time

DOI10.1137/1.9781611973204.7MaRDI QIDQ5194759zbMATH OpenOpenAlexFDO

Authors Shirshendu Ganguly, Yuval Peres

Publication date 17 September 2019

Published in 2014 Proceedings of the Eleventh Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45) Random walks on graphs (05C81) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Abstract: Given a permutation sigma of the integers {-n,-n+1,...,n} we consider the Markov chain X_{sigma}, which jumps from k to sigma (kpm 1) equally likely if k eq -n,n. We prove that the expected hitting time of {-n,n} starting from any point is Theta(n) with high probability when sigma is a uniformly chosen permutation. We prove this by showing that with high probability, the digraph of allowed transitions is an Eulerian expander; we then utilize general estimates of hitting times in directed Eulerian expanders.

Recommendations

• A permuted random walk exits faster
• Random walk generated by random permutations of {1, 2, 3,  ,n+ 1}
• scientific article; zbMATH DE number 2067820
• Random permutation graphs and related Markov chains
• Maximum hitting time for random walks on graphs

Cited in

(5)

• Correction to: ``Speeding up Markov chains with deterministic jumps
• Speeding up Markov chains with deterministic jumps
• Random walk generated by random permutations of {1, 2, 3,  ,n+ 1}
• A permuted random walk exits faster
• Random walks on regular trees can not be slowed down

This page was built for publication: Permuted random walk exits typically in linear time

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