the proof of Markov chain recurrent state in the book Neural Networks and Learning Machines

Question

It's about the definition of a recurrent state. I think there might be something wrong in this book. it is said as following.

Suppose a Markov chain starts in state i. State i is said to be a recurrent state if the Markov chain returns to state i with probability 1; that is,
pi =P(ever returning to state i) =1
If the probability pi is less than 1, state iis said to be a transientstate (Leon-Garcia, 1994). If the Markov chain starts in a recurrent state, that state reoccurs an infinite number of times. If it starts in a transient state, that state reoccurs only a finite number of times, which may be explained as follows: We may view the reoccurrence of state i as a Bernoulli trial with a probability of success equal to pi .The number of returns is thus a geometric random variable with a mean of (1 - 1/pi). If pi < 1, it follows that the number of an infinite number of successes is zero.Therefore, a transient state does not reoccur after some finite number of returns.

You can see those italics. I can't figure out what kind of the Bernoulli trail it is. Why it has a mean of (1 - 1/pi), which indicates that when pi < 1, the mean is less than zero. Maybe it is a typo, maybe it should have meant to be (1/pi - 1). But it still seems make no sense. I mean if you want to prove that the probability for a transient state to reoccur an infinite number of times is zero, you can just use the limitation of pi^n is zero when pi<1. It has really confused me for quite a long time. Anyone has any advice here?

Answer 1

There might be a mistake somewhere along the line, because the book should say:

The expected number of returns is $$ \frac{p_i}{1 - p_i}.$$

But the main idea is still there. This is an invocation of the geometric series, which you can derive as follows:

Consider the series $$S = \sum_{j=0}^N x^j$$ for any complex $x \ne 0.$ This series has an exact solution which you can obtain by both multiplying and dividing by $1-x$: $$ \begin{split} S &= \frac{1}{1-x} (1-x) S \\ &= \frac{1}{1-x} \sum_{j=0}^N x^j (1-x) \\ &= \frac{1}{1-x} \left[ \sum_{j=0}^N x^j - \sum_{j=1}^{N+1} x^j \right] \\ &= \frac{1 - x^{N+1}}{1-x}, \end{split} $$

where, in the last step, I simply subtracted all the identical terms from both sums.

For $|x < 1|,$ using the above result we can see that $$ \lim_{N \rightarrow \infty} \sum_{n=0}^N x^n = \frac{1}{1-x}, $$ which is the geometric series result used by the textbook.

Now, if you have a Markov chain in state $i$ with probability $p_i$ of returning to state $i$ at least once at a later time, then it has a probability $p_i^n$ of returning to state $i$ at least $n$ times. The expected number of times to return to $i$ is just the sum over the number of possible times it can return to $i$ multiplied by the probability of returning to it that number of times. Because the probability of returning to state $i$ exactly $n$ times is $p_i^n (1 - p_i),$ then the expected number of times it will return to state $i$ is,

$$ \begin{split} E(\text{num returns}) &= \sum_{j=0}^\infty j p_i^j (1 - p_i) \\ &= p_i (1-p_i) \sum_{j=0}^\infty j p_i^{j-1} \\ &= p_i (1-p_i) \frac{d}{d p_i} \sum_{j=0}^\infty p_i^j \\ &= p_i (1-p_i) \frac{d}{d p_i} \frac{1}{1-p_i} \\ &= \frac{p_i}{1 - p_i}. \end{split} $$

Your alternative proof is insufficient. To simply assert that $\lim_{N\rightarrow\infty}p(N\text{ returns}) = 0$ does not imply that the expected number of returns is finite. There are series' that diverge, where the terms still approach zero as the series progresses. For example, suppose the probability of hitting state $i$ exactly $N$ times is $6 / (\pi N)^2$ for $N>0$ and $0$ for $N=0$ (this is a valid probability mass function). The limit of the terms in this sequence is still $0$ for infinite $N$, however, the expected number of times the state returns to $i$ would be represented by a divergent series, and thus, would not be finite.