Show that the probability that the first return to state $1$ occurs at time $k$ is $(0.5)^{k-1}$

Question

Suppose that the chain is intitially in state $1$, i.e $P(X_0 = 1) = 1$. Let $\tau$ denote the time of first return to state $1$, i.e

$$\tau = \min\{n > 0: X_N = 1\}.$$

Show that

$$P(\tau = k) = (0.5)^{k-1}, k = 2, 3, ...$$

State $1$ only communicates with state $4$. I have already (correctly) got that $P_{14} = 1, P_{44} = \frac{1}{2}, P_{41} = \frac{1}{2}$.

So to do this question, what basically happens is that my process will first go from $1$ to $4$. It will then stay in $4$ for some time $k$. Then, it will either remain in $4$ or go back to $1$. The probability of this happening is

$$P_{14} \times P_{44}^k \times P_{41}^k = 1 \times (0.5)^k \times (0.5)^k = (0.5)^{2k}$$

which isn't the right answer.

Where have I gone wrong?

EDIT: Also, the next part tells me that using this relation and the definition of recurrence, I need to verify that state $1$ is recurrent. In the answers, they say

We need to show that $P(\tau = \infty) = 1$. Observe that

$$P(\tau < \infty) = \sum_{k = 2}^{\infty} P(\tau = k) = \sum_{k = 2}^{\infty} (0.5)^{k-1} = \sum_{j = 1}^{\infty} (0.5)^j = \frac{0.5}{1 - 0.5} = 1$$

How have they managed to do this. I get what we want to show, due to the definition of recurrence, but why have they then worked it out for $\tau < \infty$ and how have they gone between each of the summation signs to get $\frac{0.5}{1-0.5}$?

Answer 1

Well I don't remember much about Markov process. But I see a first mistake.

$$P_{14} \times P_{44}^x \times P_{41} = 1 \times (0.5)^x \times 0.5 = (0.5)^{x+1}$$

I just changed to follow the idea that from 1, the probability of going to 4 is 1. From 4 you can stay $x$ steps and if you are "lucky", you can go back to 1.

If you use the notation with $k$, from 4, you can go back in 1 in $(0.5)^{k+1}$, $k$ = $0, 1, ...$

You can change to $(0.5)^{k}$, $k$ = $1, 2, ...$

And from here, you need the step between 1 and 4 at the beginning.

$$P(\tau = k) = (0.5)^{k-1}, k = 2, 3, ...$$

Hope it helps.

Answer 2

Since Thierry Silbermann has already answered the first part of the question, I will confine myself to the second part.

Let $A_k$ denote the event that $\tau = k$. Then, $A_2, A_3, A_4, \ldots$ are disjoint or mutually exclusive events. Then, the third axiom of probability theory tells us that the event

$$B = \{\tau ~\text{has finite value}\} = A_2 \cup A_3 \cup A_4 \cup \cdots$$ has probability $$P(B) = P(A_2 \cup A_3 \cup A_4 \cup \cdots) = P(A_2) + P(A_3) + P(A_4) + \cdots$$ where the sum on the right is really $$\begin{align} \lim_{k \to \infty} \bigr[P(A_2) + P(A_3) + P(A_4) + \cdots + P(A_k)\bigr] &= \lim_{k \to \infty} \bigr[0.5 + (0.5)^2 + \cdots + (0.5)^{k-1}\bigr]\\ &= \lim_{k \to \infty} (0.5)\times \frac{1-(0.5)^{k-1}}{1-0.5}\\ &= \lim_{k \to \infty} 1-(0.5)^{k-1}\\ &= 1. \end{align}$$ Note that we have used the formula for a geometric series in the calculation.

Since $P(B) = 1$, the complementary event $B^c$ that the system stays in State $4$ forever and never returns to State $1$ thus has probability $0$. Note that $B^c$ is not necessarily the empty or impossible event $\emptyset$; that is, it is not necessary to deny the logical possibility that the system never ever returns to State $1$. It is just that the probability model assigns a probability of $0$ to such an occurrence.

Since this is stats.SE, it is worth considering that none of us will ever be in a position to verify and cross-validate that $B^c$ actually occurred.