Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

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

share|improve this question
    
There's a typo: $P( \tau = \inf ) = 0 $. –  lmorin Apr 22 '13 at 11:45
    
Does state 4 communicates with other states ? –  lmorin May 22 '13 at 12:15
add comment

2 Answers 2

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

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.