Surprise probabilities in Markov chains

DOI10.1017/S0963548317000074MaRDI QIDQ5366964zbMATH OpenFDO

Authors

Publication date 10 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: In a Markov chain started at a state $x$, the hitting time $au(y)$ is the first time that the chain reaches another state $y$. We study the probability $mathbf{P}_x(au(y)=t)$ that the first visit to $y$ occurs precisely at a given time $t$. Informally speaking, the event that a new state is visited at a large time $t$ may be considered a "surprise". We prove the following three bounds: 1) In any Markov chain with $n$ states, $mathbf{P}_x(au(y)=t)lefracnt$. 2) In a reversible chain with $n$ states, $mathbf{P}_x(au(y)=t)lefracsqrt2nt$ for $tge4n+4$. 3) For random walk on a simple graph with $nge2$ vertices, $mathbf{P}_x(au(y)=t)lefrac4elognt$. We construct examples showing that these bounds are close to optimal. The main feature of our bounds is that they require very little knowledge of the structure of the Markov chain. To prove the bound for random walk on graphs, we establish the following estimate conjectured by Aldous, Ding and Oveis-Gharan (private communication): For random walk on an $n$-vertex graph, for every initial vertex $x$, [ sum_y left( sup_{t ge 0} p^t(x, y) ight) = O(log n). ]

Recommendations

• Surprise probabilities in Markov chains
• Chernoff-Hoeffding bounds for Markov chains: generalized and simplified
• Large Deviation Bounds for Markov Chains
• Mixing and hitting times for finite Markov chains
• Tight inequalities among set hitting times in Markov chains

Cites work

• scientific article; zbMATH DE number 1256746 (Why is no real title available?)
• scientific article; zbMATH DE number 3255204 (Why is no real title available?)
• A self-avoiding random walk
• Characterization of cutoff for reversible Markov chains
• Intersections of random walks.
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Nonconcentration of return times
• On absorption times and Dirichlet eigenvalues
• Operator Limit Theorems
• Probability. Theory and examples.
• Total variation cutoff in a tree

Cited in

(4)

• A paradox for expected hitting times
• No cutoff in spherically symmetric trees
• Surprise probabilities in Markov chains
• A probabilistic proof of Cooper \& Frieze's ``First Visit Time Lemma

This page was built for publication: Surprise probabilities in Markov chains

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