Finite Hitting Theorem(MCMT)
- Some Remarks on the proof of Finite Hitting Theorem(Lemma 1.13 in MC&MT)
- what is this theorem saying
- why we have the limit of $\varepsilon$
- why can we get the equation (1.17)
- left things
因为我看 Markov Chain and Mixing Times 这本书主要是看英文版，所以相关的博客都尽可能使用英文书写，也算是对自己英文写作的一种训练吧。
Some Remarks on the proof of Finite Hitting Theorem(Lemma 1.13 in MC&MT)
Last Updated: 2024/04/08
what is this theorem saying
incomplete now.
why we have the limit of $\varepsilon$
What we have in the proof on the book:
\[\exists r\in \mathbb{N}, \varepsilon\in\mathbb{R}, r > 0, \varepsilon >0 \Rightarrow \forall z,w\in\mathcal{X},\exists j\leq r, P^{j}\left(z, w\right)>\varepsilon. \tag{1}\]What we want to derive:
\[\mathbf{P}_{x}\left(t <\tau_{y}^{+}\leq t+r \right)>\varepsilon \tag{2}\]The way(obvious?) we can use:
\[\begin{aligned} \mathbf{P}_{x}\left(t <\tau_{y}^{+}\leq t+r \right) &=\sum_{z\in\mathcal{X}}\sum_{i=1}^{r} \left(\mathbf{P}\left(X_{t}=z\right)P^{i}\left(z, y\right)\right) \\ &\geq \sum_{z\in\mathcal{X}} \left(\mathbf{P}\left(X_{t}=z\right)P^{j_{z}}\left(z, y\right)\right) \\ &> \sum_{z\in\mathcal{X}} \left(\mathbf{P}\left(X_{t}=z\right)\cdot\varepsilon\right) \\ &= \varepsilon\sum_{z\in\mathcal{X}} \mathbf{P}\left(X_{t}=z\right) \\ &= \varepsilon \end{aligned} \nonumber\]Take care that the above $j_{z}$ represents the arbitrarily-selected, according $j$ of state $z$ for equation (1).
why can we get the equation (1.17)
We can get this by:
\[\begin{aligned} \mathbf{P}_{x}\left\{\tau_{y}^{+}>kr\right\} &= \left(\mathbf{P}_{x}\left\{\tau_{y}^{+}>kr\right\}+\mathbf{P}_{x}\left\{\tau_{y}^{+}\leq \left(k-1\right)r\right\}\right) \frac{\mathbf{P}_{x}\left\{\tau_{y}^{+}>kr\right\}} {\mathbf{P}_{x}\left\{\tau_{y}^{+}>kr\right\}+\mathbf{P}_{x}\left\{\tau_{y}^{+}\leq \left(k-1\right)r\right\}} \\ &= \left(1-\mathbf{P}_{x}\left(\left(k-1\right)r <\tau_{y}^{+}\leq kr \right)\right) \frac{\mathbf{P}_{x}\left\{\tau_{y}^{+}>kr\right\}} {\mathbf{P}_{x}\left\{\tau_{y}^{+}>kr\right\}+\mathbf{P}_{x}\left\{\tau_{y}^{+}\leq \left(k-1\right)r\right\}} \\ &<\left(1-\varepsilon\right) \frac{\mathbf{P}_{x}\left\{\tau_{y}^{+}>kr\right\}} {\mathbf{P}_{x}\left\{\tau_{y}^{+}>kr\right\}+\mathbf{P}_{x}\left\{\tau_{y}^{+}\leq \left(k-1\right)r\right\}} \\ &< \left(1-\varepsilon\right) \frac{\mathbf{P}_{x}\left\{\tau_{y}^{+}>\left(k-1\right)r\right\}} {\mathbf{P}_{x}\left\{\tau_{y}^{+}>\left(k-1\right)r\right\}+\mathbf{P}_{x}\left\{\tau_{y}^{+}\leq \left(k-1\right)r\right\}} \\ &= \left(1-\varepsilon\right) \frac{\mathbf{P}_{x}\left\{\tau_{y}^{+}>\left(k-1\right)r\right\}} {\mathbf{P}_{x}\left\{\tau_{y}^{+}\in\mathbb{N}^{+}\right\}} \\ &= \left(1-\varepsilon\right)\mathbf{P}_{x}\left\{\tau_{y}^{+}>\left(k-1\right)r\right\} \end{aligned} \nonumber\]left things
Other parts are actually specifically explained in the proof, so here we don't redo it again.