I'm reading Jeffrey's A first look at rigorous probability theory, in particular, Proposition 8.4.10. Here is a sketch of the proposition and its proof:
There are two places in the Proof I'm stuck on.
The first one is in the first paragraph. I'm confused about why a finite state space implies that $h_{ji}^{(m)} \geq \delta$ for all states $j$, and for some $m \in$ N and $\delta > 0$?
The second confusion follows immediately at the beginning of the second paragraph, that is, how does the author come up with the result $1 - h_{ii}^{(n)} \leq (1- \delta)^{\lfloor n/m \rfloor}$?
Any advice is greatly appreciated!!
The first point follows from $$ \lim_{m \to \infty} h_{ji}^{(m)} = f_{ji} > 0. $$ The idea is that for these things to be converging to something positive, eventually they all have to stay positive.
Let's make things concrete. For that limit above to hold, there has to be a value $k_j$ such that $h_{ji}^{(k_j)} \ge \frac12 f_{ji}$. (Otherwise, if $h_{ji}^{(m)}$ never reaches even $\frac12 f_{ji}$, how can it converge to $f_{ji}$?) Note that $h_{ji}^{(m)}$ is non-decreasing, so we have $h_{ji}^{(m)} \ge \frac12 f_{ji}$ for all $m \ge k_j$.
Now choose $\delta$ to be minimum of $\frac12 f_{ji}$ over all states $j$, and let $m$ be the maximum of $k_j$ over all states $j$. Then for each $j$, $h_{ji}^{(m)} \ge h_{ji}^{(k_j)} \ge \frac12 f_{ji} \ge \delta$.
For the second point: having $h_{ji}^{(m)} \ge \delta$ tells us that no matter where the random walk is at any time, with probability at least $\delta$ it will visit state $i$ in the next $m$ steps. We're looking at $1 - h_{ii}^{(n)}$: the probability that the random walk stays away from state $i$ for $n$ steps.
In the first $m$ steps, there's at least a $\delta$ probability of visiting $i$. If that doesn't work out, then in the next $m$ steps, there's at least a $\delta$ probability of visiting $i$. If that doesn't work out either, then in the next $m$ steps, there's again at least a $\delta$ chance of probability $i$, and so on.
So the probability of avoiding $i$ is at most $1-\delta$ after $m$ steps, at most $(1-\delta)^2$ after $2m$ steps, at most $(1-\delta)^3$ after $3m$ steps, and so on. It is at most $(1 - \delta)^{\lfloor n/m\rfloor}$ after $\lfloor n/m\rfloor m$ steps, by the same reasoning. Since $n \ge \lfloor n/m\rfloor m$, the probability is at most $(1 - \delta)^{\lfloor n/m\rfloor}$ after $n$ steps, too.