Determining probability of a draw in simple coin flipping game Consider a 2-player game where each player flips a coin every round. If a player flips heads, they get a point for that round. Either both players get a point, only one, or none. The game ends when either of the players get to 10 points. If the game ends with both players getting 10 points, then a draw occurs. What is the probability of getting a draw?
I solved a simpler version of this problem (players only needed 3 points to win) using a Markov chain, where each game state is the score. For the simpler case I have these states:
0-0, 1-0, 1-1, 2-0, 2-1, 2-2, 3-X(win), 3-3
Players are indistinguishable from one another (2-1 and 1-2 are functionally the same) and winning scores are indistinguishable except for ties (3-0, 3-1, 3-2 are all wins for a player, 3-3 is a tie)
Then I got this Markov matrix:
$M =\begin{bmatrix} 0.25&0&0&0&0&0&0&0 \\ 0.5&0.25&0&0&0&0&0&0 \\ 0.25&0.25&0.25&0&0&0&0&0 \\ 0&0.25&0&0.25&0&0&0&0 \\ 0&0.25&0.5&0.25&0.25&0&0&0 \\ 0&0&0.25&0&0.25&0.25&0&0 \\ 0&0&0&0.5&0.5&0.5&1&0 \\ 0&0&0&0&0&0.25&0&1 \end{bmatrix}$
Calculating probabilities:
$\lim_{k \to \infty}M^k\begin{bmatrix}1\\0\\0\\0\\0\\0\\0\\0\end{bmatrix} = \begin{bmatrix}0\\0\\0\\0\\0\\0\\\frac{70}{81}\\\frac{11}{81}\end{bmatrix}$
So the draw probability in this case is $\frac{11}{81}$.
The Markov matrix for this is an 8x8, but if I were to do the same for the 10 point game, I would get a (1+2+...+10)+2=57x57 matrix, which is a bit impractical to handle.
Are there more optimized methods for this type of problem?
 A: Let $X_i$ be outcome of $i^{th}$ coin toss for player $1$.
Let $Y_i$ be outcome of $i^{th}$ coin toss for player $2$.
P(drawing at $\ell^{th}$ toss) =
P($\sum_{i=1}^{\ell-1} X_i = 9, X_{\ell} = 1$ , $\sum_{i=1}^{\ell-1} Y_i = 9, Y_{\ell} = 1$ ) = $0.5 P(\sum_{i=1}^{\ell-1} X_i = 9) \times 0.5 P(\sum_{i=1}^{\ell-1} Y_i = 9)$.
Now $P(\sum_{i=1}^{\ell-1} X_i = 9) = P(\sum_{i=1}^{\ell-1} Y_i = 9) = {\ell-1 \choose 9} \frac{1}{2^{\ell-1}}$. Now sum over $\ell$ to get ur answer.
A: Here is a semi-solution, for general $ k $. I try and compute for $ n = 3 $. Unfortunately, it looks like I have a different value. Of course, there may be some calculation mistake.  For $ k = 10$, you will need to do some calculations to finish it off.
The number of coin tosses until you get $ k $ heads follow  a negative Binomial distribution with parameters $ k $ and $ p $. Here we are taking the number of tosses (not the number of failures) as the variable and a fair coin, i.e., $ p = 1/2$. Player 1 wins if the negative binomial with parameters $k$ and $1/2$ (number of tosses to get $k$ heads), associated with her coin tosses, is smaller than the corresponding negative binomial with parameters $k$ and $1/2$, associated with the coin tosses of player 2 and vice versa. Thus, the game will be a draw if and only if both negative Binomial random variables assume the same value. Since the coin tosses of player 1 and player 2 are independent, clearly the negative Binomial random variables are independent. Thus, we have the required probability as
\begin{equation*}
\alpha_k  = \mathbb{P} ( X_1 = X_2 )
\end{equation*}
where $ X_1, X_2 $ are independent and both having negative Binomial     distribution with parameters $ k $ and $ 1/2 $.
Writing down the pmf, we have
\begin{equation*}
\alpha_k = \mathbb{P} ( X_1 = X_2 ) = \sum_{ n = k}^{\infty} \binom{n-1}{k-1} \frac{1}{2^n}  \binom{n-1}{k-1} \frac{1}{2^n} = \sum_{ n = k}^{\infty} \binom{n-1}{k-1}^2  \frac{1}{4^n} . 
\end{equation*}
Now, to sum this we use the expansion of $ (1-x)^{-k} $ for $ k \geq 1 $ (here $k = 10 $). Note that
\begin{equation*}
(1-x)^{-k} = \sum_{ n = 0}^{ \infty} \binom{ n+k-1}{ n } x^n = \sum_{ n = 0}^{ \infty} \binom{ n+k-1}{ k-1 } x^n. 
\end{equation*}
Now, set
\begin{equation*}
f_k (x) = x^{k-1} (1-x)^{-k}
\end{equation*}
and observe that
\begin{equation*}
f_k (x)  = x^{k-1} (1-x)^{-k} = \sum_{ n = 0}^{ \infty} \binom{ n+k-1}{ k-1 } x^{n+k-1} = \sum_{ n = k }^{ \infty} \binom{ n-1}{ k-1 } x^{n-1}. 
\end{equation*}
Differentiate both sides $(k-1)$ times with respect to $ x $ and taking the derivative inside the sum (can be done since the power series converges absolutely for $|x| < 1 $), we have
\begin{equation*}
f_{k}^{(k-1)} (x) =  \sum_{ n = k}^{ \infty} \binom{ n-1}{ k-1 }  (n-1)(n-2) \dotsm (n-k+1) x^{n-k}.
\end{equation*}
Now, dividing by $ (k-1)! $ and multiplying by $ x^{k} $, we have
\begin{align*}
\frac{x^{k}}{(k-1)!} f_{k}^{(k-1)} (x)   & =  \sum_{ n = k}^{ \infty} \binom{ n-1}{ k-1 }  \frac{ (n-1)(n-2) \dotsm (n-k+1) }{ (k-1)!}  x^{n} \\
& = \sum_{ n = k}^{ \infty} \binom{ n-1}{ k-1 } \binom{ n-1}{ k-1 }   x^{n} \\
& = \sum_{ n = k}^{ \infty} \binom{ n-1}{ k-1 }^2    x^{n}  .
\end{align*}
Thus, we have
\begin{equation*}
\alpha_k = \frac{x^{k}}{(k-1)!} f_{k}^{(k-1)} (x) \biggl|_{ x = 1/4} .
\end{equation*}
For $ k = 3 $, we have
\begin{equation*}
\frac{x^{3}}{(3-1)!}  f_3^{(2)} (x) = \frac{x^{3}}{2} \Biggl[ 2 (1-x)^{-3} - 12 x (1-x)^{-4} + 12 x^2 (1-x)^{-5} \Biggr].
\end{equation*}
We have
\begin{align*}
\alpha_3 & = \frac{x^{3}}{(3-1)!}  f_3^{(2)} (x) \biggl|_{ x = 1/4}  \\ 
& = \frac{ 1}{2 \cdot 4^3} \Biggl[ 2 \times\Bigl( \frac{3 }{4} \Bigr)^{-3} - 12 \times \frac{1}{ 4} \times \Bigl( \frac{3 }{4} \Bigr)^{-4} + 12 \times \frac{1}{ 4^2} \times \Bigl( \frac{3 }{4} \Bigr)^{-5} \Biggr] \\
& = \frac{ 1}{ 2 \cdot  4^3}  \Biggl[  2 \times \Bigl( \frac{4 }{3} \Bigr)^{3} - 3 \times  \Bigl( \frac{4 }{3} \Bigr)^{4} + 3 \times \frac{1}{ 4} \times \Bigl( \frac{4 }{3} \Bigr)^{5} \Biggr] \\
& = \frac{ 1}{2 \cdot  4^3} \times \frac{4^3}{ 3^4}   \Bigl[  2 \times 3 - 3 + 4 \Bigr] = \frac{ 7 }{ 162 }. 
\end{align*}
