# Find E[N]. (Absorbing States MC)

Assume we toss a dice until odd number appears four consecutive times, and in such a case we stop the game. Let $N$ be the total number of times we will toss the dice. Find $E[N]$.

Lets say for states $S=\{0,1,2,3,4\}$. Here is the transition matrix for Markov Chain ... $$\begin{array}{c|ccccc} & 0 & 1 & 2 & 3 & 4 \\ \hline 0 & 1/2 & 1/2 & 0 & 0 & 0 \\ 1 & 1/2 & 0 & 1/2 & 0 & 0 \\ 2 & 1/2 & 0 & 0 & 1/2 & 0 \\ 3 & 1/2 & 0 & 0 & 0 & 1/2 \\ 4 & 0 & 0 & 0 & 0 & 1 \end{array}$$

P.S. or Assume we toss a dice until the number 1 appears for 3 consecutive times, and in such a case we stop the game. Let $N$ be the total number of times we will toss the dice. Find $E[N]$.

Here the transition matrix would be;

$$\begin{array}{c|ccccc} & 0 & 1 & 2 & 3 \\ \hline 0 & 5/6 & 1/6 & 0 & 0 \\ 1 & 5/6 & 0 & 1/6 & 0 \\ 2 & 5/6 & 0 & 0 & 1/6 \\ 3 & 0 & 0 & 0 & 1 \\ \end{array}$$

-
Do you require it to be the same odd number all four times? –  Michael Hardy Feb 3 '13 at 16:03
Assuming the die is six-sided, you can think of this as tossing a fair coin until four consecutive heads appear. A slight modification of the arguments in this post can be made to find $\Bbb E(N)$. –  David Mitra Feb 3 '13 at 16:04
Try drawing a Markov chain. Let state $s_i$ be the state where $i$ consecutive odd numbers appears. The probability of going to state $s_0$ is 1/2 and the probability to proceed to $s_{i+1}$ is 1/2. Then you can trace the paths of length N leading to $s_4$. Good luck. –  Peder Feb 3 '13 at 16:17
–  Byron Schmuland Feb 3 '13 at 19:14
@ByronSchmuland: that's why this seemed so familiar. –  robjohn Feb 4 '13 at 0:35

Instead of the matrix that appears in the question, we will use $$M=\begin{bmatrix} \tfrac12&\tfrac12&0&0&0\\ \tfrac12&0&\tfrac12&0&0\\ \tfrac12&0&0&\tfrac12&0\\ \tfrac12&0&0&0&\tfrac12\\ 0&0&0&0&0\vphantom{\tfrac12} \end{bmatrix}\tag{1}$$ A die having thrown $4$ odds will appear in the $5^{\text{th}}$ column only on the roll that it gets there and then is removed. The expected number of rolls will then be the $5^{\text{th}}$ column of $$v\sum_{n=0}^\infty nM^n=vM(I-M)^{-2}\tag{2}$$ where $v=\begin{bmatrix}1&0&0&0&0\end{bmatrix}$, the initial state.

That is, $\mathrm{E}[N]$ is the $5^{\text{th}}$ column of \begin{align} &\begin{bmatrix} 1&0&0&0&0 \end{bmatrix} \begin{bmatrix} \tfrac12&\tfrac12&0&0&0\\ \tfrac12&0&\tfrac12&0&0\\ \tfrac12&0&0&\tfrac12&0\\ \tfrac12&0&0&0&\tfrac12\\ 0&0&0&0&0\vphantom{\tfrac12} \end{bmatrix} \begin{bmatrix} 16 & 8 & 4 & 2 & 1\vphantom{\tfrac12} \\ 14 & 8 & 4 & 2 & 1\vphantom{\tfrac12} \\ 12 & 6 & 4 & 2 & 1\vphantom{\tfrac12} \\ 8 & 4 & 2 & 2 & 1\vphantom{\tfrac12} \\ 0 & 0 & 0 & 0 & 1\vphantom{\tfrac12} \end{bmatrix}^2 \\[6pt] &=\begin{bmatrix} 1&0&0&0&0 \end{bmatrix} \begin{bmatrix} 416 & 216 & 112 & 58 & 30 \\ 386 & 200 & 104 & 54 & 28 \\ 328 & 170 & 88 & 46 & 24 \\ 216 & 112 & 58 & 30 & 16 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix}\\[6pt] &=\begin{bmatrix} 416 & 216 & 112 & 58 & \color{#C00000}{30} \end{bmatrix}\tag{3} \end{align} Thus, $\mathrm{E}[N]=30$

Another Approach

Using the method from this answer, we use $p=\frac12$ and $n=4$ to get \begin{align} \mathrm{E}[N] &=\frac{1-\left(\tfrac12\right)^4}{\left(\tfrac12\right)^4\left(1-\tfrac12\right)}\\[6pt] &=30\tag{4} \end{align}

Validation of the Series

Equation $(2)$ is simply the power series $$\sum_{n=0}^\infty nx^n=\frac{x}{(1-x)^2}\tag{5}$$ which converges for $|x|<1$, applied to $M$. We need to verify that the series converges when applied to $M$. \begin{align} \sum_{n=0}^mnM^n(I-M)^2 &=\sum_{n=0}^mnM^n(I-2M+M^2)\\ &=\sum_{n=0}^m(nM^n-2nM^{n+1}+nM^{n+2})\\ &=\sum_{n=0}^mnM^n-2\sum_{n=1}^{m+1}(n-1)M^n+\sum_{n=2}^{m+2}(n-2)M^n\\ &=\left(M+\sum_{n=2}^mnM^n\right)-2\left(mM^{m+1}+\sum_{n=2}^m(n-1)M^n\right)\\ &+\left((m-1)M^{m+1}+mM^{m+2}+\sum_{n=2}^m(n-2)M^n\right)\\ &=M-(m+1)M^{m+1}+mM^{m+2}\tag{6} \end{align} The characteristic polynomial of $M$ is $P(x)=16x^5-8x^4-4x^3-2x^2-x$ and the absolutely largest root of $P$ is $0.96378098774146265213$. Since this is less than $1$, the series converges. Therefore, we get $$\sum_{n=0}^\infty nM^n(I-M)^2=M\tag{7}$$ which becomes $(2)$.

-
Can you please provide more info about the formula? reference book or article would be helpful. $v\sum_{n=0}^\infty nM^n=vM(I-M)^{-2}$ –  Faheem Feb 5 '13 at 12:58
@Faheem: I have added a validation of the series. –  robjohn Feb 5 '13 at 14:27
Thanks robjohn ... –  Faheem Feb 5 '13 at 22:35
If i take the M=[0.5 0.5 0 0 0; 0.5 0 0.5 0 0; 0.5 0 0 0.5 0; 0.5 0 0 0 0.5; 0 0 0 0 1]; The one in question, showing that the state 4 being the absorbing state (represented by 1 on forth row and forth column). If I calculate (I-M)^-2, it results in Inf !!! –  Faheem Feb 5 '13 at 22:46
@Faheem: Yes it does; since the bottom row of $I-M$ is all zeros, the determinant is $0$. –  robjohn Feb 5 '13 at 23:40