Winning game probability

Question

At each round of a game with two players Alice and Bob, Alice can win with a fixed probability $a$ and Bob can win a fixed probability $b$, such that $a+b < 1$, otherwise there is a draw.
The game ends when one of the two players wins $N$ times in a row.
What is the probability that Alice will win the game?

Answer 1

Here goes a combinatorial proof of the answer (formula (1)) by Christian Remling.

If Alice wins, then after the last draw (or after the beginning if there were no draws) we have a sequence $B^jTA^N$, where $0\leqslant j\leqslant N−1$, $T$ is either empty or starts with $A$ and ends with $B$, and $T$ has no $N$ consecutive $A$'s or $B$'s. Then the probability of such thing is $b^ja^N\operatorname{prob}(T)$, and summing up over $j$ we get $a^Ns_N(b)\operatorname{prob}(T)$. Now sum up over $T$ and over all sequences before the last draw (including this last draw). Note that reflected $T$'s are exactly what appears for Bob's win, and have the same probabilities. Thus the ratio of probabilities of Alice' and Bob's wins equals $a^Ns_N(b):b^Ns_N(a)$.

As Sam Hopkins notes in the comment, if Bob had to win $M$ consecutive rounds, the ratio is $a^Ns_M(b):b^Ms_N(a)$ that is proved by the literally the same argument.

Answer 2

As indicated in the comments, this is not difficult in principle, but the details seem tedious. Alice wins with probability $$ \frac{a^NS_N(b)}{a^NS_N(b)+b^NS_N(a)} , \tag1 $$ with $$ S_N(x)=1+x+\ldots+x^{N-1} = \frac{1-x^N}{1-x} . $$

We can think of this as a random walk (or Markov chain) on $-N,-N+1, \ldots, N$. We start at $0$, and being at site $n$ means that we have just seen $|n|$ consecutive wins for Alice ($n<0$) or Bob ($n>0$).

We are interested in the probability of reaching $-N$ before $N$ was visited. Denote this probability, with the game starting at $n$, by $p_n$; so we want $p_0$. Then, from the transition rules, \begin{align*} p_0 &= ap_{-1} + bp_1 + (1-a-b)p_0 \tag2 \\ p_{-n} & = ap_{-n-1} + bp_1+(1-a-b)p_0 \\ p_n & =bp_{n+1} + ap_{-1}+(1-a-b)p_0 . \end{align*} We also have the boundary conditions $p_{-N}=1$, $p_N=0$. Starting at $n=N$, we find $p_{N-1}=ap_{-1}+(1-a-b)p_0$, then $p_{N-2}=a(1+b)p_{-1}+(1-a-b)(1+b)p_0$ etc., until $$ p_1=S_{N-1}(b)(ap_{-1}+(1-a-b)p_0). $$ Similarly, $$ p_{-1} =a^{N-1} +S_{N-1}(a)(bp_1+(1-a-b)p_0) . $$ We now need to solve this remaining $3\times 3$ linear system for $p_0$ (and $p_{\pm 1}$). A moderately convenient way of doing this is to use $(2)$ to rewrite the last two equations as \begin{align*} p_1 & = S_{N-1}(b)(p_0-bp_1) \\ p_{-1} &= S_{N-1}(a)(p_0-ap_{-1}) + a^{N-1} , \end{align*} solve these for $p_{\pm 1}$ in terms of $p_0$ and plug into $(2)$ to produce an equation for $p_0$ only. (Or, more sensibly perhaps, use a computer algebra system.) This gives $p_0=a^N/(DS_N(a))$, with $$ D=a+b-2+\frac{1}{S_N(a)}+\frac{1}{S_N(b)} . $$ This is where I stopped in an earlier version of this answer, but the expression can be further massaged to reach $(1).$

Answer 3

Simply discard when we get draws, as there are identical sub-problems with the original one.
Compute straightforward the probability when Alice wins by how many alternating $a,b$ groups we have:
$(1+b+...+b^{N-1})a^N$ ,
$(1+b+...+b^{N-1})(a+...+a^{N-1})(b+...+b^{N-1})a^N$ ,
$(1+b+...+b^{N-1})(a+...+a^{N-1})(b+...+b^{N-1})(a+...+a^{N-1})(b+...+b^{N-1})a^N$ ,
and so on.

Let $r=(a+...+a^{N-1})(b+...+b^{N-1})$
then Alice wins with probability:
$(1+r+r^2+...)(1+b+...+b^{N-1})a^N$ ,
and Bob:
$(1+r+r^2+...)(1+a+...+a^{N-1})b^N$ ,
and we get the same ratio between them:
$a^N\frac{1-b^N}{1-b}$ : $b^N\frac{1-a^N}{1-a}$

Alice wins probability:
$A = \frac{a^N(1-a)(1-b^N)}{a^N(1-a)(1-b^N) + b^N(1-b)(1-a^N)}$