Reversible Markov-chain surprise bound
Reversible Markov-chain surprise bound
Let be a reversible Markov chain with finite state space, and let be the stationary distribution of . For states and , write for the hitting time of starting from . Reversible surprise conjecture. For all ,
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.