DATA605 - Homework 10

Markov Chains / Random Walks

Problem

Smith is in jail and has 1 dollar; he can get out on bail if he has 8 dollars.

A guard agrees to make a series of bets with him. If Smith bets A dollars, he wins A dollars with probability .4 and loses A dollars with probability .6.

Find the probability that he wins 8 dollars before losing all of his money if

1. he bets 1 dollar each time (timid strategy).
2. he bets, each time, as much as possible but not more than necessary to bring his fortune up to 8 dollars (bold strategy).
3. Which strategy gives Smith the better chance of getting out of jail?

SOLUTION:

Smith’s situation is similar to the Gambler’s Ruin problem described in the class’ textbook.

Smith, the gambler, starts with a “stake” of size s = 1. He will play until his capital reaches the value M = 8 to be bailed out or the value 0, which will keep him in jail. In the language of Markov chains, these two values correspond to absorbing states. We are interested in studying the probability of occurrence of each of these two outcomes.

Therefore, one can use the equation (on page 489 of CHAPTER 12.2 RANDOM WALKS):

\(P = \frac{1−(\frac{q}{p})^s}{1−(\frac{q}{p})^M}\)

(a) Probability of Smith betting 1 dollar each time (timid strategy)

The given values can be associated with the formula’s variables as follows:

M <- 8
s <- 1
p <- 0.4
q <- 0.6

P_timid <- ( 1 - ( (q/p)^s ) ) / ( 1 - ( (q/p)^M ) )

P_timid
#> [1] 0.02030135

Therefore, the probability of Smith winning $8 with a timid strategy is 0.0203013 or 2.03%.

(b) Probability of Smith betting as much as possible but not more than necessary to bring his fortune up to 8 dollars (bold strategy).

Build a Markov chain to represent the states and transitions that Smith would have to face depending on which strategy he tries to follow.

Build a state transition matrix to represent the Markov chain transitions between 0, 1, 2, 4, and 8 dollars.

tran_mat <- matrix(c(1,0,0,0,0,
                   0.6,0,0.4,0,0,
                   0.6,0,0,0.4,0,
                   0.6,0,0,0,0.4,
                   0,0,0,0,1), ncol = 5, nrow = 5, byrow = TRUE)

rownames(tran_mat) <- c("1","2","3","4","5")
colnames(tran_mat) <- c("0","1","2","4","8")

tran_mat
#>     0 1   2   4   8
#> 1 1.0 0 0.0 0.0 0.0
#> 2 0.6 0 0.4 0.0 0.0
#> 3 0.6 0 0.0 0.4 0.0
#> 4 0.6 0 0.0 0.0 0.4
#> 5 0.0 0 0.0 0.0 1.0

Define a matrix to represent the initial state in which Smith will bet 1 dollar.

init_state <- matrix(c(0, 1, 0, 0, 0), ncol=5,nrow = 1,byrow = TRUE)

Since Smith needs to bet as much as possible but not more than necessary to bring his fortune up to 8 dollars (bold strategy), We need to calculate probabilities for transitions between 1, 2, 4, and 8 dollars.

Begin by multiplying the initial state by the transition matrix to obtain transition 1 probabilities

p1 <- init_state %*% tran_mat

p1
#>        0 1   2 4 8
#> [1,] 0.6 0 0.4 0 0

Multiply p1 state by transition matrix to obtain transition 2

p2 <- p1 %*% tran_mat

p2
#>         0 1 2    4 8
#> [1,] 0.84 0 0 0.16 0

Multiply p2 state by transition matrix to obtain transition 3

p3 <- p2 %*% tran_mat

p3
#>          0 1 2 4     8
#> [1,] 0.936 0 0 0 0.064

Multiply p3 state by transition matrix to obtain transition 4

p4 <- p3 %*% tran_mat

p4
#>          0 1 2 4     8
#> [1,] 0.936 0 0 0 0.064

From the results above, if Smith takes the bold strategy by betting each time as much as possible, then he has a 0.064 or 6.4% probability of winning the 8 dollars necessary to make bail.

(c) Which strategy gives Smith the better chance of getting out of jail?

After comparing the results from sections (a) and (b), we can conclude that the bold strategy yields the best chance with 6.4% probability of making bail.