Hitting time of trajectory

Workshop introduction

In general, we will use the following notation in the problem list. We consider aperiodic irreducible Markov chains on a state space, $\Omega$ with unique invariant (stationary) distribution $\pi$. In the discrete time setting we allow the matrix $(P)_{x,y\in\Omega}$ with $P_{xy}=P(x,y)$ to denote the transition matrix of the Markov chain.

A chain is reversible if $\pi(x)P(x,y)=\pi(y)P(y,x)$ for all $x,y\in\Omega$. $Q(x,y)=\pi(x)P(x,y)$ is the edge measure on $(x,y)$. We denote by $t_{\mbox{mix}}$ the total variation mixing time defined as

and set $t_{\mbox{mix}}=t_{\mbox{mix}}(\epsilon)$, where the total variation distance

Section context

For a nonreversible chain with transition matrix $P(x,y)$, define its time-reversal by $\hat P(x,y)=(\pi(x))^{-1}\pi(y)P(y,x)$. Then the symmetrization of the chain is given by the Markov chain with transition matrix $\frac 12 (P+\hat P)$.

Historical workshop record. Current open/solved status has not been independently reassessed.

Status note in the source

Such an upper bound is known for the mixing time. The current best bound on the hitting time of a trajectory is $|E||V|(1+\log \frac {|E|}{|V|})$.