Homework-10

library(tidyverse)
library(expm) 
set.seed(39)

Problem Statement

Smith finds himself incarcerated with only 1 dollar, needing 8 dollars to secure his release on bail. A guard offers him a series of betting opportunities. If Smith wagers A dollars, he wins A dollars with a probability of 0.4 and loses A dollars with a probability of 0.6. Determine the probability of him winning 8 dollars before losing all of his money under the following strategies:

(a) Betting 1 dollar each time (timid strategy)

(b) Betting as much as possible, but not exceeding the amount needed to reach 8 dollars, each time (bold strategy)

(c) Determine which strategy offers Smith the better chance of securing his release

Solution

We approach the problem using both simulation and a Markov process model to ascertain the probabilities associated with each strategy.

Strategy 1 - Simulation

Setting key parameters such as the number of simulations, Smith’s initial balance, and the win/loss probabilities:

We’ll start by setting some key parameters. I’ll chose the number of simulations (10,000), Smith’s starting balance ($\$1$), and the probabilities of winning and losing (0.4 and 0.6, respectively).

n_sims <- 10^4
balance <- 1
p_win <- 0.4
p_lose <- 0.6

We simulate the timid strategy, where Smith bets 1 dollar each time, and then the bold strategy, where he bets as much as needed but not exceeding 8 dollars:

results <- data.frame()
wager <- 1
  
for (n in 1:n_sims) {
  balance <- 1
  n_rounds <- 0 
  while (balance > 0 & balance < 8) {
    win_lose <- sample(x = c(1,0), size = 1, prob = c(p_win, p_lose))
    balance <- ifelse(
      win_lose == 1,
      balance + wager,
      balance - wager
    )
    n_rounds <- n_rounds + 1
  }
  
  free_notfree <- ifelse(
    balance == 8,
    'free', 'not_free'
  )
  
  result <- list(
    balance = balance,
    result = free_notfree,
    n_rounds = n_rounds
  )
  
  results <- rbind(results, result)
}

cat(
  'No. of simulations in which Smith is free: ',
  nrow(filter(results, result == 'free')), '\n',
  'No. of simulations overall: ', 
  n_sims, '\n',
  'Probability of freedom with timid strategy: ',
  round(nrow(filter(results, result == 'free')) / n_sims * 100, 3),'%',
  sep = ''
)

## No. of simulations in which Smith is free: 201
## No. of simulations overall: 10000
## Probability of freedom with timid strategy: 2.01%

Let’s try it again, but with the bold strategy. This time, the wager will be the minimum of either Smith’s current balance, or 8 minus that balance. For example, if Smith has $3, he will bet all three dollars. If he has $5, he will bet only the three dollars required to get him to $8 (i.e. 8 - 5 = 3).

results <- data.frame()
  
for (n in 1:n_sims) {
  balance <- 1
  n_rounds <- 0
  while (balance > 0 & balance < 8) {
    wager <- min(balance, 8 - balance)
    win_lose <- sample(x = c(1,0), size = 1, prob = c(p_win, p_lose))
    balance <- ifelse(
      win_lose == 1,
      balance + wager,
      balance - wager
    )
    n_rounds <- n_rounds + 1
  }
  
  free_notfree <- ifelse(
    balance == 8,
    'free', 'not_free'
  )
  
  result <- list(
    balance = balance,
    result = free_notfree,
    n_rounds = n_rounds
  )
  
  results <- rbind(results, result)
}

cat(
  'No. of simulations in which Smith is free: ',
  nrow(filter(results, result == 'free')), '\n',
  'No. of simulations overall: ', 
  n_sims, '\n',
  'Probability of freedom with bold strategy: ',
  round(nrow(filter(results, result == 'free')) / n_sims * 100, 3),'%',
  sep = ''
)

## No. of simulations in which Smith is free: 665
## No. of simulations overall: 10000
## Probability of freedom with bold strategy: 6.65%

Based on this simulation, Smith is better off with the bold strategy! It gives him a ~6.76% chance of freedom, while the timid strategy only gives him a ~2.1% chance.

Strategy 2 - Simulation with Markov Process

Let’s try the same exercise, but modeling the bet as a markov process. Each state will represent a certain balance for Smith (i.e. having one dollar, having two dollars, etc.). For each strategy, we’ll require a transition matrix to detail the probabilities of moving up or down in a state.

For the timid strategy, each row of the transition matrix will only have two non-zero values, corresponding to the probability of moving up a state (i.e. winning a dollar, with a probability of 0.4) or moving down a state (i.e. losing a dollar, with a probability of 0.6). The only exceptions are the first and last rows, which correspond to absorbing states. If Smith’s balance falls to zero dollars, he can no longer bet, so he has a probability of 1 of remaining in that state. Similarly, if Smith gets $8, he will stop betting because he’ll be free. So the probability of remaining in that state is also 1.

timid_probs <- matrix(0, nrow = 9, ncol = 9)

for (i in 1:8) {
  if (i > 1) timid_probs[i, i-1] <- 0.6
  if (i < 9 & i > 1) timid_probs[i, i+1] <- 0.4
}

timid_probs[1, 1] <- 1
timid_probs[9, 9] <- 1 

timid_probs

##       [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
##  [1,]  1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
##  [2,]  0.6  0.0  0.4  0.0  0.0  0.0  0.0  0.0  0.0
##  [3,]  0.0  0.6  0.0  0.4  0.0  0.0  0.0  0.0  0.0
##  [4,]  0.0  0.0  0.6  0.0  0.4  0.0  0.0  0.0  0.0
##  [5,]  0.0  0.0  0.0  0.6  0.0  0.4  0.0  0.0  0.0
##  [6,]  0.0  0.0  0.0  0.0  0.6  0.0  0.4  0.0  0.0
##  [7,]  0.0  0.0  0.0  0.0  0.0  0.6  0.0  0.4  0.0
##  [8,]  0.0  0.0  0.0  0.0  0.0  0.0  0.6  0.0  0.4
##  [9,]  0.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0  1.0

With this matrix, we can again run a simulation. We’ll use the same framework as before, but instead of randomly sampling a win or loss for each bet, we’ll randomly choose a new state based on the transition probabilities for the row corresponding to the balance at the beginning of each turn.

results <- data.frame()
  
for (n in 1:n_sims) {
  balance <- 1
  n_rounds <- 0 
  while (balance > 0 & balance < 8) {
    balance <- sample(x = c(0:8), size = 1, prob = timid_probs[balance+1,])
    n_rounds <- n_rounds + 1
  }
  
  free_notfree <- ifelse(
    balance == 8,
    'free', 'not_free'
  )
  
  result <- list(
    balance = balance,
    result = free_notfree,
    n_rounds = n_rounds
  )
  
  results <- rbind(results, result)
}

cat(
  'No. of simulations in which Smith is free: ',
  nrow(filter(results, result == 'free')), '\n',
  'No. of simulations overall: ', 
  n_sims, '\n',
  'Probability of freedom with timid strategy: ',
  round(nrow(filter(results, result == 'free')) / n_sims * 100, 3),'%',
  sep = ''
)

## No. of simulations in which Smith is free: 192
## No. of simulations overall: 10000
## Probability of freedom with timid strategy: 1.92%

Our result is pretty close to the original simulation!

We can also raise our transition matrix to a large power to simulate a steady state, then grab the probability of transitioning from $1 to $8 (i.e. from state 2 to state 9).

p_success <- (timid_probs %^% n_sims)[2, 9]

cat('Probability of freedom: ', round(p_success*100, 3),'%', sep = '')

## Probability of freedom: 2.03%

Again, we see a similar probability of success for the timid strategy.

Let’s move to the bold strategy. Our transition matrix for this strategy will differ a bit. Now, whenever Smith wins, he will move up not by one state, but by the size of his wager, which differs based on his current balance. Similarly, when he loses, he will fall down by the number of states equal to his wager. As with the original simulation, this wager can be defined as minimum of either Smith’s current balance, or 8 minus that balance (we’ll use 9 to account for the indexing of the matrix). We’ll also set the first and final states as absorbing states once again.

bold_probs <- matrix(0, nrow = 9, ncol = 9)

for (i in 1:8) {
  wager <- min (i-1, 9-i)
  bold_probs[i, i-wager] <- 0.6
  bold_probs[i, i+wager] <- 0.4
}

bold_probs[1, 1] <- 1
bold_probs[9, 9] <- 1 
bold_probs

##       [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
##  [1,]  1.0    0  0.0    0  0.0    0  0.0    0  0.0
##  [2,]  0.6    0  0.4    0  0.0    0  0.0    0  0.0
##  [3,]  0.6    0  0.0    0  0.4    0  0.0    0  0.0
##  [4,]  0.6    0  0.0    0  0.0    0  0.4    0  0.0
##  [5,]  0.6    0  0.0    0  0.0    0  0.0    0  0.4
##  [6,]  0.0    0  0.6    0  0.0    0  0.0    0  0.4
##  [7,]  0.0    0  0.0    0  0.6    0  0.0    0  0.4
##  [8,]  0.0    0  0.0    0  0.0    0  0.6    0  0.4
##  [9,]  0.0    0  0.0    0  0.0    0  0.0    0  1.0

Let’s simulate! We can use the same exact set-up, but plug in the transition matrix corresponding to the bold strategy.

results <- data.frame()
  
for (n in 1:n_sims) {
  balance <- 1
  n_rounds <- 0 
  while (balance > 0 & balance < 8) {
    balance <- sample(x = c(0:8), size = 1, prob = bold_probs[balance+1,])
    n_rounds <- n_rounds + 1
  }
  
  free_notfree <- ifelse(
    balance == 8,
    'free', 'not_free'
  )
  
  result <- list(
    balance = balance,
    result = free_notfree,
    n_rounds = n_rounds
  )
  
  results <- rbind(results, result)
}

cat(
  'No. of simulations in which Smith is free: ',
  nrow(filter(results, result == 'free')), '\n',
  'No. of simulations overall: ', 
  n_sims, '\n',
  'Probability of freedom with timid strategy: ',
  round(nrow(filter(results, result == 'free')) / n_sims * 100, 3),'%',
  sep = ''
)

## No. of simulations in which Smith is free: 639
## No. of simulations overall: 10000
## Probability of freedom with timid strategy: 6.39%

We again see a higher probability of success for the bold strategy.

And again, we can approximate a steady state by raising our transition matrix to a high power and looking at the probability of moving from state 2 (having $1) to state 9 (having $8).

p_success <- (bold_probs %^% n_sims)[2, 9]

cat('Probability of freedom: ', round(p_success*100, 3),'%', sep = '')

## Probability of freedom: 6.4%

Conclusion