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.

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

share|improve this question
1  
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
1  
    
@ByronSchmuland: that's why this seemed so familiar. –  robjohn Feb 4 '13 at 0:35
add comment

1 Answer 1

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

share|improve this answer
    
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
show 1 more 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.