Chapter 11. Problem 9.

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, until it reaches 5. Find the expected number of steps it takes to reach the integer five.

Let’s assume that \(E(i)\) is expected number of steps to move from integer i to integer 5. The problem asks to solve for \(E(1)\).

When process’ present position is 5: \(E(5) = 0\) since 5 is the largest number in the interval [1;5]

E5 <- 0

When process’ present position is 4: \(E(4) = 1\) as only 5 is greater than 4

E4 <- 1

When process’ present position is 3: process can move to 4 or 5 with equal probability \(\frac{1}{2}\)

E3 <- 1/2*(E4+1)+1/2*(E5+1)
E3
## [1] 1.5

When process’ present position is 2: process can move to 3,4 or 5 with equal probability \(\frac{1}{3}\)

E2 <- 1/3*(E3+1)+1/3*(E4+1)+1/3*(E5+1)
E2
## [1] 1.833333

When process’ present position is 1: process can move to 2,3,4 or 5 with equal probability \(\frac{1}{4}\)

E1 <- 1/4*(E2+1)+1/4*(E3+1)+1/4*(E4+1)+1/4*(E5+1)
round(E1,0)
## [1] 2