CUNY 605 Homework Assignment Week 10

Reference: http://www2.math.uu.se/~takis/L/McRw/HANDOUTS/hw4sol.pdf, https://clubs.ntu.edu.sg/spmsclub/math/PYP/MAS%20&%20MAEC%20year%204/MAS446MTH437_1213.pdf, https://clubs.ntu.edu.sg/spmsclub/math/PYP/MAS%20&%20MAEC%20year%204/MAS446MTH437_1213.pdf

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).

We formulate the problem as a Markov chain of nine states. Each state represents the amount of dollars that Smith has.

The Markov chain \((X_n,n = 0,1,...)\) representing the evolution of Smith’s money has diagram.

If the timid strategy is adopted, then the one-step transition matrix P is:

To answer this question, we will be using the fundamental matrix of P, which is defined as \(F = (I-Q)^{-1}\).

row1 <- c(1,0,0,0,0,0,0,0,0) #0
row2 <- c(0,1,0,0,0,0,0,0,0) #8
row3 <- c(0.6,0,0,0.4,0,0,0,0,0) #1
row4 <- c(0,0,0.6,0,0.4,0,0,0,0) #2
row5 <- c(0,0,0,0.6,0,0.4,0,0,0) #3
row6 <- c(0,0,0,0,0.6,0,0.4,0,0) #4
row7 <- c(0,0,0,0,0,0.6,0,0.4,0) #5
row8 <- c(0,0,0,0,0,0,0.6,0,0.4) #6
row9 <- c(0,0.4,0,0,0,0,0,0.6,0) #7
limited_p <- matrix(c(row1,row2,row3,row4,row5,row6,row7,row8,row9), nrow = 9, byrow = TRUE)
limited_p
##       [,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.0  1.0  0.0  0.0  0.0  0.0  0.0  0.0  0.0
##  [3,]  0.6  0.0  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.4  0.0  0.0  0.0  0.0  0.0  0.6  0.0

As you can see, we can now identify Q and create the Fundamental Matrix F.

I <- diag(7)

row1 <- c(0,0.4,0,0,0,0,0)
row2 <- c(0.6,0,0.4,0,0,0,0)
row3 <- c(0,0.6,0,0.4,0,0,0)
row4 <- c(0,0,0.6,0,0.4,0,0)
row5 <- c(0,0,0,0.6,0,0.4,0)
row6 <- c(0,0,0,0,0.6,0,0.4)
row7 <- c(0,0,0,0,0,0.6,0)
Q <- matrix(c(row1,row2,row3,row4,row5,row6,row7), nrow = 7, byrow = TRUE)

F_matrix <- solve(I - Q)
F_matrix
##           [,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.63283109

Now let’s create our R matrix and F * R matrix:

R <- matrix(c(0.6,0,0,0,0,0,0,0,0,0,0,0,0,0.4), ncol = 2, byrow = TRUE)
R
##      [,1] [,2]
## [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.4
FR <- F_matrix %*% R
FR
##           [,1]       [,2]
## [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.65313243

The states 1 through 7 are listed on the left and they are the transient states. The columns (which are numbered 1 and 2) are absorbing states 0 and 8 respectively. As a result, if we are at starting state 1. What is the probability of ending up in state 8?

answer <- FR[1,2]
answer
## [1] 0.02030135

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

Given that the strategy has changed, this will require a new transition matrix. The probabilities continues to remain the same with winning at 0.4 and losing at 0.6. However, dollar bet A will be the maximum dollar amount that Smith has (up to maximum amount required to get to $8). So for example, if Smith starts with one dollar, he will bet one dollar. If he wins, he will have two dollars, and he will then again bet two dollars. If he then wins, he will have a total of four dollars and will bet four dollars again. If Smith has four dollars and loses, he will lose all four dollars and enter the absorbing state of zero dollars.

row0 <- c(1,0,0,0,0,0,0,0,0)
row1 <- c(0.6,0,0.4,0,0,0,0,0,0)
row2 <- c(0.6,0,0,0,0.4,0,0,0,0)
row3 <- c(0.6,0,0,0,0,0,0.4,0,0)
row4 <- c(0.6,0,0,0,0,0,0,0,0.4)
row5 <- c(0,0,0.6,0,0,0,0,0,0.4)
row6 <- c(0,0,0,0,0.6,0,0,0,0.4)
row7 <- c(0,0,0,0,0,0,0.6,0,0.4)
row8 <- c(0,0,0,0,0,0,0,0,1)
bold_trans <- matrix(c(row0,row1,row2,row3,row4,row5,row6,row7,row8), nrow = 9, byrow= TRUE)
bold_trans
##       [,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

Again, let’s identify our standard matrix as described above in stem A.

row1 <- c(1,0,0,0,0,0,0,0,0)
row2 <- c(0,1,0,0,0,0,0,0,0)
row3 <- c(0.6,0,0,0.4,0,0,0,0,0)
row4 <- c(0.6,0,0,0,0,0.4,0,0,0)
row5 <- c(0.6,0,0,0,0,0,0,0.4,0)
row6 <- c(0.6,0.4,0,0,0,0,0,0,0)
row7 <- c(0,0.4,0,0.6,0,0,0,0,0)
row8 <- c(0,0.4,0,0,0,0.6,0,0,0)
row9 <- c(0,0.4,0,0,0,0,0,0.6,0)

standard_matrix_bold <- matrix(c(row1,row2,row3,row4,row5,row6,row7,row8,row9), nrow = 9, byrow = TRUE)
standard_matrix_bold
##       [,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.0  1.0    0  0.0    0  0.0    0  0.0    0
##  [3,]  0.6  0.0    0  0.4    0  0.0    0  0.0    0
##  [4,]  0.6  0.0    0  0.0    0  0.4    0  0.0    0
##  [5,]  0.6  0.0    0  0.0    0  0.0    0  0.4    0
##  [6,]  0.6  0.4    0  0.0    0  0.0    0  0.0    0
##  [7,]  0.0  0.4    0  0.6    0  0.0    0  0.0    0
##  [8,]  0.0  0.4    0  0.0    0  0.6    0  0.0    0
##  [9,]  0.0  0.4    0  0.0    0  0.0    0  0.6    0

Let’s identify matrix R and Q and create it in R:

R <- matrix(c(0.6,0,0.6,0,0.6,0,0.6,0.4,0,0.4,0,0.4,0,0.4), ncol=2, byrow=TRUE)
R
##      [,1] [,2]
## [1,]  0.6  0.0
## [2,]  0.6  0.0
## [3,]  0.6  0.0
## [4,]  0.6  0.4
## [5,]  0.0  0.4
## [6,]  0.0  0.4
## [7,]  0.0  0.4
row1 <- c(0,0.4,0,0,0,0,0)
row2 <- c(0,0,0,0.4,0,0,0)
row3 <- c(0,0,0,0,0,0.4,0)
row4 <- c(0,0,0,0,0,0,0)
row5 <- c(0,0.6,0,0,0,0,0)
row6 <- c(0,0,0,0.6,0,0,0)
row7 <- c(0,0,0,0,0,0.6,0)
Q <- matrix(c(row1,row2,row3,row4,row5,row6,row7), nrow = 7, byrow = TRUE)
Q
##      [,1] [,2] [,3] [,4] [,5] [,6] [,7]
## [1,]    0  0.4    0  0.0    0  0.0    0
## [2,]    0  0.0    0  0.4    0  0.0    0
## [3,]    0  0.0    0  0.0    0  0.4    0
## [4,]    0  0.0    0  0.0    0  0.0    0
## [5,]    0  0.6    0  0.0    0  0.0    0
## [6,]    0  0.0    0  0.6    0  0.0    0
## [7,]    0  0.0    0  0.0    0  0.6    0

Find the Fundamental Matrix F:

I <- diag(7)
fundamental_F <- solve(I - Q)
fundamental_F
##      [,1] [,2] [,3] [,4] [,5] [,6] [,7]
## [1,]    1  0.4    0 0.16    0  0.0    0
## [2,]    0  1.0    0 0.40    0  0.0    0
## [3,]    0  0.0    1 0.24    0  0.4    0
## [4,]    0  0.0    0 1.00    0  0.0    0
## [5,]    0  0.6    0 0.24    1  0.0    0
## [6,]    0  0.0    0 0.60    0  1.0    0
## [7,]    0  0.0    0 0.36    0  0.6    1

To obtain the probabilities of a transient state going to either absorbing state zero dollars or eight dollars, we multiply the fundamental matrix by R.

FR <- fundamental_F %*% R
FR
##       [,1]  [,2]
## [1,] 0.936 0.064
## [2,] 0.840 0.160
## [3,] 0.744 0.256
## [4,] 0.600 0.400
## [5,] 0.504 0.496
## [6,] 0.360 0.640
## [7,] 0.216 0.784

So again, with the left rows representing the transient states, one dollar, two dollars, etc. and columns representing zero dollars and eight dollars respectively, the probability that Smith reach eight dollars with the bold strategy is:

answer <- FR[1,2]
answer
## [1] 0.064

The probability is 0.064.

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

The bold strategy is a better choice for Smith.