Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

which isn't the right answer.

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

share|cite|improve this question
up vote 1 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.