A few weeks ago, I came across the following problem.
Alice and Bob are planning to gamble against each other. Before they start to play the game, Bob wants to calculate its chance of winning to determine if he has a positive expectation.
The game works as follows. Charlie starts throwing two dice and he records the sum of the two dice each time. If at a certain point a sequence of two $7$s in a row occurs, Alice wins the game and the game ends. If on the contrary, a sequence of three strictly increasing numbers occurs, Bob wins the game and the game ends.
What is the probability that Bob (or Alice) wins the game?
I am looking for a theoretical method of solving this problem. I tried a few different ones but it all didn't seem to work. I am thinking that some version of using Markov chains could work, although I don't see how.
After doing some simulations I found:
- The expectation of the number of tries before a sequence of two $7$s is a row occurs, is approximately $42$.
- The expectation of the number of tries before a sequence of three increasing numbers is a row occurs, is approximately $10.5$.
- It doesn't seem to work to divide the expectations of the number of tries although you come close, i.e., there is probably some dependence relation going on.
- The probability of Alice winning is approximately $19\%$.
Edit: I got the following probabilty of Alice winning to be equal to $$ \frac{450074090171}{556534555787} \approx 80.87\% $$ after applying joriki's method. Via simulations and doing some confidence interval analysis, this appears to be correct since it is inside some of the 95% confidence intervals I constructed: $$ [80.76215853,80.98464147]. $$
I used the following ordering of the $20$ unknowns: $$(p_2,p_3^-,p_4^-,...,p_{11}^-,p_3^+,p_4^+,...,p_{11}^+,p_{12})$$
The matrix induced by the linear equations is given by $[A_1,A_2]$ (I multiplied the equations by $36$, note that at two places I have written a * which is related to Alice winning, i.e., two $7$s in a row) $$ A_1 = \begin{pmatrix}-35&0&0&0&0&0&0&0&0&0\\ 1&-34&0&0&0&0&0&0&0&0\\ 1&2&-33&0&0&0&0&0&0&0\\ 1&2&3&-32&0&0&0&0&0&0\\ 1&2&3&4&-31&0&0&0&0&0\\ 1&2&3&4&5&-36*&0&0&0&0\\ 1&2&3&4&5&6&-31&0&0&0\\ 1&2&3&4&5&6&5&-32&0&0\\ 1&2&3&4&5&6&5&4&-33&0\\ 1&2&3&4&5&6&5&4&3&-34\\ 1&2&0&0&0&0&0&0&0&0\\ 1&2&3&0&0&0&0&0&0&0\\ 1&2&3&4&0&0&0&0&0&0\\ 1&2&3&4&5&0&0&0&0&0\\ 1&2&3&4&5&0*&0&0&0&0\\ 1&2&3&4&5&6&5&0&0&0\\ 1&2&3&4&5&6&5&4&0&0\\ 1&2&3&4&5&6&5&4&3&0\\ 1&2&3&4&5&6&5&4&3&2\\ 1&2&3&4&5&6&5&4&3&2\\ \end{pmatrix} $$ $$ A_2 = \begin{pmatrix}2&3&4&5&6&5&4&3&2&1\\ 0&3&4&5&6&5&4&3&2&1\\ 0&0&4&5&6&5&4&3&2&1\\ 0&0&0&5&6&5&4&3&2&1\\ 0&0&0&0&6&5&4&3&2&1\\ 0&0&0&0&0&5&4&3&2&1\\ 0&0&0&0&0&0&4&3&2&1\\ 0&0&0&0&0&0&0&3&2&1\\ 0&0&0&0&0&0&0&0&2&1\\ 0&0&0&0&0&0&0&0&0&1\\ -36&0&0&0&0&0&0&0&0&0\\ 0&-36&0&0&0&0&0&0&0&0\\ 0&0&-36&0&0&0&0&0&0&0\\ 0&0&0&-36&0&0&0&0&0&0\\ 0&0&0&0&-36&0&0&0&0&0\\ 0&0&0&0&0&-36&0&0&0&0\\ 0&0&0&0&0&0&-36&0&0&0\\ 0&0&0&0&0&0&0&-36&0&0\\ 0&0&0&0&0&0&0&0&-36&0\\ 0&0&0&0&0&0&0&0&0&-35\\ \end{pmatrix} $$ Its inverse should now be calculated and multiplied with the vector $$ \begin{pmatrix}0&0&0&0&0&0&0&0&0&0&-33&-30&-26&-21&-15&-10&-6&-3&-1&0&\end{pmatrix}'. $$ The $20$th component of the resulting vector is now equal to $p_{12}$, the probability of Bob winning the game. Thanks to joriki for finding the solution method and finding an error I made!
You could do this using a Markov chain, but since you only want a single winning probability (say, Bob's), you don't need all the machinery and can just directly set up a system of linear equations. There are $2\cdot11-2=20$ non-terminal states you can be in: For each of the $11$ possible last rolls from $2$ to $12$, you need to remember whether the previous step was a strict increase or not; except for $2$ you know that it wasn't and for $12$ you don't care. That gives you $20$ variables, and you can set up $20$ equations for them by propagating each state. If we denote the winning probabilities in the states as $p_\sigma^\pm$, where $\sigma$ is the sum last rolled and $+$ indicates a strict increase (and $-$ its absence), we have for instance
$$ p_6^-=\frac1{36}\left(1p_2+2p_3^-+3p_4^-+4p_5^-+5p_6^-+6p_7^++5p_8^++4p_9^++3p_{10}^++2p_{11}^++1p_{12}\right) $$
and
$$ p_7^+=\frac1{36}\left(1p_2+2p_3^-+3p_4^-+4p_5^-+5p_6^-+6\cdot0+5\cdot1+4\cdot1+3\cdot1+2\cdot1+1\cdot1\right) $$
(where $0$ is Bob's winning probability if Alice wins and $1$ is Bob's winning probability if Bob wins).
Bob's winning probability in the initial state is $p_{12}$ (since the first roll isn't an increase, and likewise no roll after $12$ is an increase).