A process moves on the integers 1, 2, 3, 4, and 5. It starts at 1 and, on each successive step, moves to an integer greater than its present position, moving with equal probability to each of the remaining larger integers. State five is an absorbing state. Find the expected number of steps to reach state five.
The transition matrix for this situation is:
\(P = \begin{array}{ccccc|c} & 1 & 2 & 3 & 4 & 5 \\ 1 & 0 & 1/4 & 1/4 & 1/4 & 1/4 \\ 2 & 0 & 0 & 1/3 & 1/3 & 1/3 \\ 3 & 0 & 0 & 0 & 1/2 & 1/2 \\ 4 & 0 & 0 & 0 & 0 & 1 \\ \hline 5 & 0 & 0 & 0 & 0 & 1 \end{array}\)
The matrix \(Q\) then is:
\(Q=\left(\begin{matrix} 0 & 1/4 & 1/4 & 1/4 \\ 0 & 0 & 1/3 & 1/3 \\ 0 & 0 & 0 & 1/2 \\ 0 & 0 & 0 & 0 \end{matrix} \right)\)
Therefore,
\(I-Q=\left(\begin{matrix} 1 & -1/4 & -1/4 & -1/4 \\ 0 & 1 & -1/3 & -1/3 \\ 0 & 0 & 1 & -1/2 \\ 0 & 0 & 0 & 1 \end{matrix} \right)\)
matrix_one <- matrix(c(1, 0, 0, 0, -1/4, 1, 0, 0, -1/4, -1/3, 1, 0, -1/4, -1/3, -1/2, 1), nrow = 4)
matrix_two <- solve(matrix_one)
matrix_two## [,1] [,2] [,3] [,4]
## [1,] 1 0.25 0.3333333 0.5
## [2,] 0 1.00 0.3333333 0.5
## [3,] 0 0.00 1.0000000 0.5
## [4,] 0 0.00 0.0000000 1.0The expected number of steps to reach step five can now be found by summing the first row: \(1 + 1/4 + 1/3 + 1/2=12/12+3/12+4/12+6/12=25/12=2.08\overline 3\)
We can confirm this finding by analyzing the possible outcomes. The possible sequences are:
1,5 (one step, \(p=1/4\))
1,2,5 (two steps, \(p=1/4\times1/3=1/12\))
1,3,5 (two steps, \(p=1/4\times1/2=1/8\))
1,4,5 (two steps, \(p=1/4\times1=1/4\))
1,2,3,5 (three steps, \(p=1/4\times1/3\times1/2=1/24\))
1,2,4,5 (three steps, \(p=1/4\times1/3\times1=1/12\))
1,3,4,5 (three steps, \(p=1/4\times1/2\times1=1/8\))
1,2,3,4,5 (four steps, \(p=1/4\times1/3\times1/2\times1=1/24\))
Weighting these produces: \(E(X)=(1\times1/4)+(2\times1/12)+(2\times1/8)+(2\times1/4)+(3\times1/24)+(3\times1/12)+(3\times1/8)+(4\times1/24) \\ =1/4+1/6+1/4+1/2+1/8+1/4+3/8+1/6\\=6/24+4/24+6/24+12/24+3/24+6/24+9/24+4/24\\=50/24\\=25/12\)
Therefore, \(E(X)=25/12\), as desired.