Q9 p423

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.

To solve this, we first have to make a transition matrix of the possible steps.
Starting at 1, if I win, I can move to 2,3,4, & 5 with a 25% chance each.
At 2, if I win, I can move to 3,4, & 5 with a 33.33333% chance each.
At 3, if I win, I can move to 4, & 5 with a 50% chance each.
At 4, if I win, I can move to 5 with a 100% chance.
5 is the absorbing state so we stay 100% of the times at 5.

stages = c('1','2','3','4','5') 
transit_matrix = matrix(c(0,.25,.25,.25,.25,
                          0,0,.33,.33,.33,
                          0,0,0,.5,.5,
                          0,0,0,0,1,
                          0,0,0,0,1), 
                        byrow = T, nrow = 5, 
                        dimnames = list(stages,stages))
print(transit_matrix)
##   1    2    3    4    5
## 1 0 0.25 0.25 0.25 0.25
## 2 0 0.00 0.33 0.33 0.33
## 3 0 0.00 0.00 0.50 0.50
## 4 0 0.00 0.00 0.00 1.00
## 5 0 0.00 0.00 0.00 1.00

This transition matrix acts as our P matrix that we can use to find Q.
Q will be the transient matrix when we are at stage 5 so we remove the row/column for stage 5. \(\begin{bmatrix}0&0.25&0.25&0.25&\\0&0&0.33&0.33&\\0&0&0&0.5&\\0&0&0&0&\\&&&&1\end{bmatrix}\)

Q = matrix(c(0,.25,.25,.25,
            0,0,.33,.33,
            0,0,0,.5,
            0,0,0,0),
            byrow = T, nrow = 4)
print(Q)
##      [,1] [,2] [,3] [,4]
## [1,]    0 0.25 0.25 0.25
## [2,]    0 0.00 0.33 0.33
## [3,]    0 0.00 0.00 0.50
## [4,]    0 0.00 0.00 0.00

We can then use q for the formula \(M = (I - Q)^-1\) where I is the identity matrix.

I = matrix(c(1,0,0,0,
                    0,1,0,0,
                    0,0,1,0,
                    0,0,0,1), 
                    byrow = T, nrow = 4)
print(I)
##      [,1] [,2] [,3] [,4]
## [1,]    1    0    0    0
## [2,]    0    1    0    0
## [3,]    0    0    1    0
## [4,]    0    0    0    1
M = solve(I - Q)

print(M)
##      [,1] [,2]   [,3]    [,4]
## [1,]    1 0.25 0.3325 0.49875
## [2,]    0 1.00 0.3300 0.49500
## [3,]    0 0.00 1.0000 0.50000
## [4,]    0 0.00 0.0000 1.00000

We can then sum up the first row of the resulting matrix to find the number of steps:
\(1 + 0.25 + 0.3325 + 0.49875 = 2.08125\)
Rounding to the nearest step, we expect the number of steps to reach state five to be 2.