Assignment 10

Week 10, Markov Chains / Random Walks

Fundamentals of Computational Mathematics

CUNY MSDS DATA 605, Fall 2018

Rose Koh

11/3/2018

12.2 The gambler’s ruin 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

The gambler starts with a stake of size of \(s\) and plays until their stake reaches the value \(M\) or the value \(0\), absorbing states.

** (a) he bets 1 dollar each time (timid strategy). **

The Markov chain \((X_n, n = 0,1,…)\) represents the evolution of Smith’s money. Let \(p(i)\) represent the probaility that the chain reaches state 8 before reaching state 0 starting from state i.

\[p(i)=Pi(S_8 <S_0)=P(S_8 <S_0|X_0 =i).\]

\(P_{broke} = \frac{(q/p)^z - (q/p)^M}{(1 - q/p)^M}\)

\(P_{win} = 1 - P_{broke} =\\ 1 - \frac{(0.6/0.4)^1 - (0.6/0.4)^8}{1 1 (0.6/0.4)^8} =\)

p <- 0.4
q <- 1 - p
z <- 1
M <- 8
(q_z <- (((q/p)^z - 1)/((q/p)^M - 1)))

## [1] 0.02030135

This means that the probability that the chain reaches state 8 before reaching state 0 starting from state 1 is equal to .0203.

We can also create simulation as follows:

game <- as.integer(100000)
win <- 0

for (i in 1:game) {
  j <- 1 #initializing for new game
  while (j>0 & j<8) { # end conditions
    j <- j + sample(c(-1,1),1,
                    replace=TRUE,
                    prob=c(0.6,0.4))
  }
  win <- win+(j>=8) # winning condition
}
prob<- win/100000 # approx 0.0203

paste0("Smith gets out on bail ", win, " times out of ", game, " times of simiulations, with prob. of success at approximately  ", prob, "%")

## [1] "Smith gets out on bail 1955 times out of 100000 times of simiulations, with prob. of success at approximately  0.01955%"

** (b) he bets, each time, as much as possible but not more than necessary to bring his fortune up to 8 dollars (bold strategy). **

When Smiith bets \(x\) dollars, he either loses or gains \(x\) dollars. When he bets his entire money each time up to 8 times, he must either win each time or gets broke to lose. If he bets a dollar and wins, he’d gain 2 dollars. If he continues to bet 2 dollars and wins, then he’d gain 4 dollars. And if he bets 4 dollars and wins, then he’d gain 8 dollars. His winning sequence is thus 1,2,4,8. He starts with a dollar and wins 3 bets in a row at prob. .4. We can solve this with Binomial distribution as follows.

dbinom(3, 3, 0.4)

## [1] 0.064

# or Chances of all successes p^n
0.4^3

## [1] 0.064

We can also create simulation as follows:

p <- 0.4
win <- 0

for (i in 1:game) {
    j <- 1
    while (j > 0 & j < 8) {
        if (runif(1) <= p) {
            j <- j + j
        } else {
            j <- j - j
        }
    }
    if (j >= 8) {
        win <- win + 1
    }
}

win/game

## [1] 0.06515

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

Bold of course!