In a Markov chain started at a state x, the hitting time τ(y) is the first time that the chain reaches another state y. We study the probability Px(τ(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:#R##N##R##N#• In any Markov chain with n states, Px(τ(y) = t) ≤ n/t.#R##N##R##N#• In a reversible chain with n states, Px(τ(y) = t) ≤ [EQUATION]2n/t for t ≥ 4n + 4.#R##N##R##N#• For random walk on a simple graph with n ≥ 2 vertices, Px(τ(y) = t) ≤ 4e log n/t.#R##N##R##N#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.#R##N##R##N#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,#R##N##R##N#[EQUATION]
['James Norris', 'Yuval Peres', 'Alex Zhai']
Surprise probabilities in Markov chains