Reversible Markov-chain surprise bound

Let XX be a reversible Markov chain with finite state space, and let π\pi be the stationary distribution of XX. For states xx and yy, write τ(y)\tau(y) for the hitting time of yy starting from xx. Reversible surprise conjecture. For all t>0t>0,

Px(τ(y)=t)=O(1tmax(1,log1π(x))).\mathbf{P}_x(\tau(y)=t)=O\left(\frac{1}{t}\sqrt{\max\left(1,\log\frac{1}{\pi(x)}\right)}\right).

This conjecture would improve the bound in the paper's theorem for reversible chains and is motivated by an example showing a gap between the known upper bound and the currently available lower-bound construction. Its resolution is not supplied here.

Sources & referencesView supporting material

Primary source

James Norris, Yuval Peres and Alex Zhai, “Surprise probabilities in Markov chains”, arXiv:1408.0822 (2014).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.