(IP, Chapter 11: Markov Chains, pg. 424)
15) Consider the game of tennis when deuce is reached. If a player wins the next point, he has advantage. On the following point, he either wins the game or the game returns to deuce. Assume that for any point, player A has probability .6 of winning the point and player B has probability .4 of winning the point.
(a) Set this up as a Markov chain with state 1: A wins; 2: B wins; 3: advantage A; 4: deuce; 5: advantage B.
# Compose transition matrix
state_names <- c("S1: Game A", "S2: Game B", "S3: Ad A", "S4: Deuce", "S5: Ad B")
P_deuce <- matrix(c(1, 0, 0, 0, 0,
0, 1, 0, 0, 0,
.6, 0, 0, .4, 0,
0, 0, .6, 0, .4,
0, .4, 0, .6, 0),
nrow = 5, byrow = TRUE)
colnames(P_deuce) <- state_names
rownames(P_deuce) <- state_names
P_deuce
## S1: Game A S2: Game B S3: Ad A S4: Deuce S5: Ad B
## S1: Game A 1.0 0.0 0.0 0.0 0.0
## S2: Game B 0.0 1.0 0.0 0.0 0.0
## S3: Ad A 0.6 0.0 0.0 0.4 0.0
## S4: Deuce 0.0 0.0 0.6 0.0 0.4
## S5: Ad B 0.0 0.4 0.0 0.6 0.0
(b) Find the absorption probabilities.
# Change the transition matrix to canonical form
P_deuce <- P_deuce[, c(3:5, 1:2)]
P_deuce <- P_deuce[c(3:5, 1:2),]
P_deuce
## S3: Ad A S4: Deuce S5: Ad B S1: Game A S2: Game B
## S3: Ad A 0.0 0.4 0.0 0.6 0.0
## S4: Deuce 0.6 0.0 0.4 0.0 0.0
## S5: Ad B 0.0 0.6 0.0 0.0 0.4
## S1: Game A 0.0 0.0 0.0 1.0 0.0
## S2: Game B 0.0 0.0 0.0 0.0 1.0
Q_deuce <- P_deuce[1:3, 1:3] # Subset matrix Q (transient to transient)
R_deuce <- P_deuce[1:3, 4:5] # Subset matrix R (transient to absorbing)
I_deuce <- diag(3) # Compose an identity matrix I with same dimensions as Q
N_deuce <- solve(I_deuce - Q_deuce) # Compute the fundamental matrix by solving the set of linear equations
M_deuce <- N_deuce %*% R_deuce # Compute absorption probabilities
M_deuce
## S1: Game A S2: Game B
## S3: Ad A 0.8769231 0.1230769
## S4: Deuce 0.6923077 0.3076923
## S5: Ad B 0.4153846 0.5846154
(c) At deuce, find the expected duration of the game and the probability that B will win.
# Compute expected steps to absorption
c_deuce <- c(rep(1, 3)) # Column vector of 1s
Nc_deuce <- N_deuce %*% c_deuce # Calculate expected steps to absorption
# Expected duration of the game in steps
Nc_deuce[2,1]
## S4: Deuce
## 3.846154
# Probability that B will win
M_deuce[2,2]
## [1] 0.3076923