# Markov Process: Show that the minimum time taken to get back to state $1$ is $(0.5)^{k-1}$

Suppose that the chain is intitially in state $1$, i.e $P(X_0 = 1) = 1$. Let $\tau$ denote the time of first returen 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} = 1 \times (0.5)^k \times (0.5) = (0.5)^{k+1}$$

Where have I gone wrong?

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}$?

-

Your answer is correct. However, you forgot that you actually did the calculations for $1+k+1$ steps, and shows that it occurred with probability $0.5^{k+1}$. With a small change of variables, you can show that for $k$ steps, it occurs with probability $0.5^{k-1}$.

As for the second part, review the sum to infinity of a geometric progression. With a first term of $a$ and a common ratio of $r$ (with absolute value strictly less than 1), then the sum is $\frac {a}{1-r}$. In particular, apply it to $a= 0.5, r=0.5$.

Edit: As you stated, let's consider what it means for the particle to return to state 1. First, it moves from state 1 to state 4 (1 move). Then, it has to stay around state 4 for some time (k moves). Then it has to return to state 1 (1 move). This occurs with probability $P_{14} \times P_{44}^k \times P_{41} = (0.5)^{k+1}$. Hence, the probability that the first return is on the (1 + k + 1 = k+2)th move is $(0.5)^{k+1}$.

Thus, the probability that the first return is on the kth move is $(0.5)^{k-1}$.

-
What do you mean by the change of variables bit? How have I already calculated for $1 + k +1$? – Kaish Jan 22 '13 at 19:19
@Kaish Read edit. – Calvin Lin Jan 22 '13 at 23:18