# 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$? Jan 22, 2013 at 19:19