Markov Chain upper bound on the probability of hitting time

Question

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!

Answer 1

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.

Answer 2

I guess we can study the following quantity $$f(T) = \max_{x \in \Omega} \mathbb{P}(\tau_y = T | x_0 = x).$$ This quantity satisfy two inequalities.

1. For any $T \geq 1$, $f(T) \leq f(T - 1)$.

Proof: It suffices to show, for any $x \in \Omega$, that
$$\mathbb{P}(\tau_y = T | x_0 = x) \leq f(T - 1).$$ If $x = y$, this is trivial since $\mathbb{P}(\tau_y = T | x_0 = x) = 0$. Otherwise, we run one step of the chain to obtain $$\mathbb{P}(\tau_y = T | x_0 = x) = \sum_{x' \in \Omega} p(x, x') \mathbb{P}(\tau_y = T - 1 | x_0 = x') \leq \sum_{x' \in \Omega} p(x, x') f(T - 1) = f(T - 1)$$ as desired.

2. We have $$\sum_{T \geq 0} f(T) \leq |\Omega|.$$ Proof: This comes from the observation that $$f(T) \leq \sum_{x \in \Omega} \mathbb{P}(\tau_y = T | x_0 = x).$$ So $$\sum_{T \geq 0} f(T) \leq \sum_{x \in \Omega} \sum_{T \geq 0} \mathbb{P}(\tau_y = T | x_0 = x) = |\Omega|.$$ Combining these two inequalities, we immediately obtain $$(T + 1) f(T) \leq \sum_{T \geq 0} f(T) \leq |\Omega|$$ as desired.