#2 the matrix way. There is infinite time but 3 absorbing states (as I interpret it), meaning 3 states where the probability of staying is 1. It is possible to find the limit of the transition matrix raised to the # of rolls as they approach infinity, known as the limiting matrix. Our answer will be encoded in the bottom-left corner of the limiting matrix. The top-left corner will be a 3x3 identity matrix and the other two corners will be all 0's because after infinite time there is no chance of being anywhere but one of the absorbing states.
To find this limit, we need to set up our transition matrix in a more particular way known as standard form: the absorbing states must all come before the non-absorbing states. In #1 it didn't matter and I had two absorbing states on opposite corners.
The matrix will be much larger (103x103 when playing to 10) because the probability of reaching an absorbing state is a function of not only the score difference like before, but also the current total score. Making matters worse, I don't think there's a way to organize it so that there's a single visual pattern like before.
However, we can still arrange it in a way that's easy to code. For instance after the absorbing states, let's group all the Player A scores together: 0-0, 0-1, 0-2...0-9, 1-0, 1-1, 1-2...1-9, and so on. This way it's easy to create a formula for the score represented by a given row:
A's score = floor[(row-4) / n]
B's score = row - 4 - A*n
where n = victory score
The probabilities we'll need to enter are 2/5, 1/5, 2/5, (2/5 + 2/5), and (2/5 + 1/5).
If the score is (a,b):
There is a 2/5 chance of reaching score (a+1, b), which is column (row+n).
There is a 1/5 chance of reaching score (a, b+1), which is column (row+1).
There is a 2/5 chance of reaching score (a+1, b+1), which is column (row+n+1).
However, we must check that we're not about to leave the matrix. If the score we're about to increment is n-1, then instead of the columns given by those formulas, the value belongs in one of the first 3 columns instead (transitioning to an absorbing state). Except in the bottom row, the value will be either 4/5 or 3/5 because when a player reaches a score of n-1, they can wiin with a 1-1 roll.
Once we have the matrix all set, there are two sub-matrices of interest:
R = all the elements from rows 4 to n and columns 1 to 3.
Q = all the elements to the right of R.
P(A win) = 1st element of (I-Q)
-1R
P(B win) = (1,2)
P(tie) = (1,3)
Code:
import LinearAlgebra.I
function firsto(p::Float64, q::Float64, n::Int64)
r = 1-p-q
x = p+r
y = q+r
len = n^2 + 3
m = fill(0.0, len, len)
m[len,1:3] = [p q r]
for k=4:(len-1)
a = floor((k-4)/n)
b = k-4-n*a
if a < n-1
m[k, k+n] = p
if b < n-1
m[k, k+n+1] = r
m[k, k+1] = q
else m[k,2]=y end
else
m[k,1] = x
m[k, k+1] = q
end
end
return (inv(I-m[4:len, 4:len])*m[4:len, 1:3])[1,1:3]
end
One line of code at the end for the actual math, and all the preceding code for setting the matrix. We don't need to set the absorbing states since we're only using the elements below them.
Results:
Code:
julia> firsto(.4, .2, 10)
3-element Array{Float64,1}:
0.8088217206170584
0.13836485459260212
0.05281342479033959
julia> firsto(.4, .2, 20)
3-element Array{Float64,1}:
0.9068162142710839
0.07089393110886681
0.022289854620049475
This disagrees with my binomial formula. 80.88% is correct; something I did in my last post was wrong. When I use that same binomial formula for playing to a score of 2, it gives an answer of 58.67% which is wrong.
We can calculate by hand the case of playing to a score of 2:
P(A win) = p²(1 + 2q) + pr = .4²(1 + 2*.2) + 2*.4² = 54.4%
which the matrix method agrees with.
So next I have to figure out what's wrong with my binomial formula.
Last edited by heehaww; 07-27-2020 at 10:21 PM.
