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!


Edit: this is wrong.

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.

  • $\begingroup$ 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! $\endgroup$ – OnoL Apr 17 at 19:17
  • $\begingroup$ @onol oops you're right, what I wrote is nonsense $\endgroup$ – Amichai Lampert Apr 17 at 19:48
  • $\begingroup$ @AmichaiLampert Not a problem~ Thanks for your comments! $\endgroup$ – user146512 Apr 18 at 4:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.