# Markov Chain upper bound on the probability of hitting time

I encountered the following problem.

• $$\{x_t\}$$: Markov chain in discrete time;

• $$\Omega$$: a finite state space s.t. $$|\Omega|=n<\infty$$;

• $$\tau_w\equiv\min\{t\ge 0\,|\,x_t=w\}$$, $$w\in\Omega$$ (first hitting time).

Prove: For each $$T\ge 1$$ and every $$x,y\in \Omega$$ $$\Pr(\tau_y=T|x_0=x)\le\frac nT.$$

Effort: This is a surprising result as the setup is terribly general. I proceeded by induction. Using recursive characterization, we have $$\Pr(\tau_y=T+1|x_0=x)=\sum_{z\ne y}\Pr(\tau_y=T|x_0=z)p(x,z),$$ where $$p(x,z)=\Pr(x_{t+1}=x|x_t=z)$$ is the transition probability. For each Markov chain, using the inductive hypothesis, we can easily confirm that this holds for $$T$$ sufficiently large. So far I cannot see how to show this for a general $$T\ge n+1$$.

Any hints or comments will be highly appreciated!

This seems incorrect. Multiplying both sides by T and summing over T we get $$E( \tau _y | x_0 =x) \leq n$$. I don't see why this should be true in general.
• Please correct me if wrong. You meant that if the conclusion holds, we should necessarily have $T\Pr(\tau_y=T|x_0=x)\le n$ for each $T$. But when summing up the left-hand-side over $T$ to get expectation, we need also sum up the right-hand-side, which is the sum of infinitely many $n$, and thus is $\infty$, being true unconditionally. Would you clarify on this? Thanks! – OnoL Apr 17 at 19:17