Section 11.2, Question 9

Data 605

Heather Geiger - November 2, 2018

Question

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.

Answer

Let’s start by making the transition matrix.

transition_matrix <- matrix(c(0,rep(0.25,times=4),0,0,rep((1/3),times=3),0,0,0,rep(0.5,times=2),0,0,0,0,1,0,0,0,0,1),byrow=TRUE,ncol=5,nrow=5)

transition_matrix

##      [,1] [,2]      [,3]      [,4]      [,5]
## [1,]    0 0.25 0.2500000 0.2500000 0.2500000
## [2,]    0 0.00 0.3333333 0.3333333 0.3333333
## [3,]    0 0.00 0.0000000 0.5000000 0.5000000
## [4,]    0 0.00 0.0000000 0.0000000 1.0000000
## [5,]    0 0.00 0.0000000 0.0000000 1.0000000

Next get the matrix N, and multiply it by a vector of ones equal to the number of rows in R.

N = inverse of (identity_matrix_of_same_size - transition_matrix_for_non_absorbing_states_only)

identity_matrix <- function(n){
    matrix_to_return = matrix(0,nrow=n,ncol=n)
    for(i in 1:n)
    {
        matrix_to_return[i,i] = 1
    }
    return(matrix_to_return)
}

N = solve(identity_matrix(4) - transition_matrix[1:4,1:4])

N %*% matrix(1,ncol=1,nrow=nrow(N))

##          [,1]
## [1,] 2.083333
## [2,] 1.833333
## [3,] 1.500000
## [4,] 1.000000

The expected number of steps to reach 5, starting from 1, is 2.083, aka 2 and 1/12.

This expected number comes from there being a 6/24 (1/4) chance of reaching 5 in exactly 1 step, an 11/24 chance in exactly 2 steps, a 6/24 chance in exactly 3 steps, and a 1/24 chance in exactly 4 steps.

We also note that the expected number of steps to reach 5 starting from 2 is 1.83, aka 1 and 5/6.