Holroyd's interval hitting-time conjecture for finite Markov chains

At least 11 years old · documented by

Let XX be a Markov chain with finite state space SS, where ∣S∣=n|S|=n, and let xx and yy be any two states. Holroyd's interval hitting-time conjecture. For all t>nt>n,

Px(t≤τ(y)≤t+n)=O(nt).\mathbf{P}_x(t\leq\tau(y)\leq t+n)=O\left(\frac{n}{t}\right).

This conjecture asks for an interval bound on hitting-time probabilities without the periodicity present in the paper's extremal example. It is attributed to Holroyd and is presented as an open question; no resolution is given in the source.

References

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.