Take the 2-minute tour ×
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.

Say I have a Markov chain $\{X_n: n \geq 1\}$ with state space $E = \{1,2,3,4,5\}$ and transition matrix,

$$ P = \begin{bmatrix} 0 & 1/2 & 1/2 & 0 & 0 \\\ 1/2 & 0 & 1/2 & 0 & 0 \\\ 1/4 & 1/4 & 0 & 1/4 & 1/4 \\\ 0 & 0 & 1/2 & 0 & 1/2 \\\ 0 & 0 & 0 & 1/2 & 1/2\ \end{bmatrix} $$

With a stationary distribution,

$$ \pi^T = [1/6 \quad 1/6 \quad 1/3 \quad 1/6 \quad 1/6]$$

Assuming that $X_1 = 1$, it is easy to use this information to calculate the expected number of transitions between successive visits to state 1 (the answer is $1/\pi_1 = 6$}.

What is not clear to me, however, is how to calculate the expected number of transitions between successive visits to state 1 conditional on the fact that state 5 is never visited.

Two potential approaches to answer this are:

1) Constructing the Markov chain graph without state 5, recalculating the transition matrix and the stationary distribution. This approach yields a transition matrix of

$$ P = \begin{bmatrix} 0 & 1/2 & 1/2 & 0 \\\ 1/2 & 0 & 1/2 & 0 \\\ 1/3 & 1/3 & 0 & 1/3 \\\ 0 & 0 & 1 & 0\ \end{bmatrix} $$

a stationary distribution of

$$ \pi^T = [1/4 \quad 1/4 \quad 3/8 \quad 1/8]$$

and an answer of 4.

2) Calculating the answer as $(1/\pi_1)$ after conditioning the stationary distribution to account for the fact that state $5$ is not visited. In other words, we normalize $\pi_1 \ldots \pi_4$ by a factor of $1 - \pi_5$ to account for the fact that state $5$ is not visited. This yields a stationary distribution

$$ \pi^T = [1/5 \quad 1/5 \quad 2/5 \quad 1/5 \quad 0]$$

and an answer of $5$.

Some friends have argued that approach #1 is the correct approach, but cannot explain why approach #2 is wrong.

Any insight is appreciated.

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

The reason number 2 is wrong is that each number is predicated upon being able to either go to or come from 5 in each state, which does not uniformly affect each of the states. The degree to which each state's steady state varies depends upon the column corresponding to 5 in the transition matrix, which is not the same for each.

share|improve this answer
    
+1 Put it in other way: conditioning on the fact that we never come into state 5, also implies conditioning on the fact that we never come from state 5. This must alter the steady state probabilities. –  leonbloy Dec 5 '12 at 1:55
add comment

Well, I don't even think the first approach is correct. Notice that in the original MC, the expected number of jumps between to two visits in 1 is 1/$\pi_1=6$, and so is it for state 5. If the first approach is correct, then on average, there are 4 visits to state 1 between two successive visits to 5, which is not intuitively correct. In fact, the desired answer should be 1, since it is proportional to the stationary distribution, in particular, let $x(1,5)$ be the number of visits to state 1 before first return to 5 given that initially the Markov chain was in state 5, we have $\frac{x(1,5)}{x(5,5)} = \frac{\pi_1}{\pi_5}$, (this can be shown by proving that $x(\cdot,5)$ satisfies $x(\cdot,5) = x(\cdot,5)P$), and notice that $x(5,5)=1$, we have $x(1,5)=1$.

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.