Question: 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: (a) he bets 1 dollar each time (timid strategy).
In order to solve for this problem, we can utilize the Gambler’s Ruin equation from out textbook:
\(P = \frac{1 - (\frac{q}{p})^{s}}{1 - (\frac{q}{p})^{M}}\)
where \(M = 8\), \(s = 1\), \(p = 0.4\), and \(q = 0.6\), since the probability of Smith winning A dollars is 0.4, losing A dollars is 0.6, Smith starts with a stake of 1 (1 dollar), and it’ll be played until Smith reaches a capital of 8.
With this in mind, we can solve the probability:
\(P = \frac{1 - (\frac{0.6}{0.4})^{1}}{1 - (\frac{0.6}{0.4})^{8}}\)
prob <- (1 - (0.6/0.4)^1) / (1 - (0.6/0.4)^8)
prob## [1] 0.02030135ANSWER: The probability that Smith wins 8 dollars before losing all of his money if he bets 1 dollar each time (and applies a timid strategy) is about 0.0203.
We can also solve this problem using matrices and Markov chains. First, we can set up our transition matrix
P <- matrix(c(0,1,0,0,0,0,0,0,0,
0.6,0,0.4,0,0,0,0,0,0,
0,0.6,0,0.4,0,0,0,0,0,
0,0,0.6,0,0.4,0,0,0,0,
0,0,0,0.6,0,0.4,0,0,0,
0,0,0,0,0.6,0,0.4,0,0,
0,0,0,0,0,0.6,0,0.4,0,
0,0,0,0,0,0,0.6,0,0.4,
0,0,0,0,0,0,0,0,1), nrow=9, byrow=TRUE)
rownames(P) <- c("0","1","2","3","4","5","6","7","8")
colnames(P) <- c("0","1","2","3","4","5","6","7","8")
P## 0 1 2 3 4 5 6 7 8
## 0 0.0 1.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0
## 1 0.6 0.0 0.4 0.0 0.0 0.0 0.0 0.0 0.0
## 2 0.0 0.6 0.0 0.4 0.0 0.0 0.0 0.0 0.0
## 3 0.0 0.0 0.6 0.0 0.4 0.0 0.0 0.0 0.0
## 4 0.0 0.0 0.0 0.6 0.0 0.4 0.0 0.0 0.0
## 5 0.0 0.0 0.0 0.0 0.6 0.0 0.4 0.0 0.0
## 6 0.0 0.0 0.0 0.0 0.0 0.6 0.0 0.4 0.0
## 7 0.0 0.0 0.0 0.0 0.0 0.0 0.6 0.0 0.4
## 8 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0# Matrix with just transient states
Q <- P[2:8, c(2:8)]
Q## 1 2 3 4 5 6 7
## 1 0.0 0.4 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
## 3 0.0 0.6 0.0 0.4 0.0 0.0 0.0
## 4 0.0 0.0 0.6 0.0 0.4 0.0 0.0
## 5 0.0 0.0 0.0 0.6 0.0 0.4 0.0
## 6 0.0 0.0 0.0 0.0 0.6 0.0 0.4
## 7 0.0 0.0 0.0 0.0 0.0 0.6 0.0# Matrix with just absorbing states
R <- P[2:8, c(1,9)]
R## 0 8
## 1 0.6 0.0
## 2 0.0 0.0
## 3 0.0 0.0
## 4 0.0 0.0
## 5 0.0 0.0
## 6 0.0 0.0
## 7 0.0 0.4Now, with the matrices separated into transient and absorbing states, we can use matrix decomposition to break down the matrix with transient states (\(N = (I - Q)^{-1}\)):
# Fundamental matrix
I <- diag(7)
N <- solve(I-Q)
N## 1 2 3 4 5 6 7
## 1 1.6328311 1.054718 0.6693101 0.4123711 0.2410785 0.1268834 0.05075337
## 2 1.5820777 2.636796 1.6732752 1.0309278 0.6026963 0.3172086 0.12688343
## 3 1.5059477 2.509913 3.1792228 1.9587629 1.1451229 0.6026963 0.24107851
## 4 1.3917526 2.319588 2.9381443 3.3505155 1.9587629 1.0309278 0.41237113
## 5 1.2204600 2.034100 2.5765266 2.9381443 3.1792228 1.6732752 0.66931007
## 6 0.9635210 1.605868 2.0340999 2.3195876 2.5099128 2.6367962 1.05471848
## 7 0.5781126 0.963521 1.2204600 1.3917526 1.5059477 1.5820777 1.63283109Finally, we can find our absorption probabilities:
# Absorption probablities
X <- N %*% R
X## 0 8
## 1 0.9796987 0.02030135
## 2 0.9492466 0.05075337
## 3 0.9035686 0.09643140
## 4 0.8350515 0.16494845
## 5 0.7322760 0.26772403
## 6 0.5781126 0.42188739
## 7 0.3468676 0.65313243As we can see, if we just isolate \(s = 1\), we get:
paste0('The probability starting with a stake of 1 is ', round(X["1","8"], 4), '.')## [1] "The probability starting with a stake of 1 is 0.0203."
- he bets, each time, as much as possible but not more than necessary to bring his fortune up to 8 dollars (bold strategy).
Now, if Smith takes a bolder approach in his betting strategy, the transition matrix will look like:
\[\begin{equation} P = \begin{bmatrix} 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\\ \end{bmatrix} \end{equation}\]
With the columns of the matrix indicating transitions between 0, 1, 2, 4, and 8 dollars:
P2 <- 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(P2) <- c("1","2","3","4","5")
colnames(P2) <- c("0","1","2","4","8")
P2## 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.0Since our initial state, matching our transition matrix above, will start with 1 dollar:
\[\begin{equation} initial = \begin{bmatrix} 0 & 1 & 0 & 0 & 0\\ \end{bmatrix} \end{equation}\]
initial <- matrix(c(0, 1, 0, 0, 0), ncol=5,nrow = 1,byrow = TRUE)With the transition matrix set, and the inital state ready as well, we can apply this to our Markov chain:
p1 <- initial %*% P2
p1## 0 1 2 4 8
## [1,] 0.6 0 0.4 0 0p2 <- p1 %*% P2
p2## 0 1 2 4 8
## [1,] 0.84 0 0 0.16 0p3 <- p2 %*% P2
p3## 0 1 2 4 8
## [1,] 0.936 0 0 0 0.064p4 <- p3 %*% P2
p4## 0 1 2 4 8
## [1,] 0.936 0 0 0 0.064ANSWER: We can see that if Smith takes a bolder approach and bets each time, as much as possible but not more than necessary to bring his fortune up to 8 dollars, he’ll have about a 0.064 probability of getting out on bail.
- Which strategy gives Smith the better chance of getting out of jail?
ANSWER: As we can see from the calculation of our probabilites in parts a and b, it would be wiser for Smith to take the bolder approach in order to have a better chance of getting out on bail and obtaining the 8 dollars from betting.