Reversible Markov-chain surprise bound
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.