Alice and Bob are playing a game. They randomly determine who starts, then they take turns flipping a number of coins (N) and adding them to a growing pile. The first one to collect their target number of tails (T) wins.
When Alice's variables are equal to Bob's ($N_{A} = N_{B}$, $T_{A} = T_{B}$), the odds of her winning are obviously 50%. However, for
$N_{A} = 2, T_{A} = 20, N_{B} = 1, T_{B} = 10$
Alice's chances of victory appear to be slightly lower than 50%. This is based on running a few hundred thousand simulations of the game in Python. This outcome is, unfortunately, unintuitive to me. What is the mathematical reason for it?
Note: This is a specific example chosen to highlight an issue I'm having in a more general problem. In the general problem, the players each have: Odds of an attempt getting them a point (O), number of attempts they get to make on their turn (N), and total number of collected points needed to win (T). If someone could also provide an equation that predicts the probability of Alice or Bob winning, given $O_{A}, N_{A}, T_{A}, O_{B}, N_{B}$, and $T_{B}$, I would be grateful.
Best Answer
You're right! This is rather non-intuitive.
Since the player who starts is chosen at random, we can ignore this in our calculations since it will average out (you can show this more formally).
On each turn let $A$ be the number of tails that Alice flips, and $B$ the number of tails for Bob.
$A \sim Binomial(2,1/2)$
$B \sim Binomial(1,1/2)$
Now let $A_j$ be the number of tails that Alice has after turn j. Define $B_j$ similarly for Bob. We can see that $A_j = A_{j-1} + A$ and $B_j = B_{j-1} + B$. So at each turn, $A_j$ is the sum of iid binomials, and $B_j$ is the sum of different iid binomials. Hence $A_j$ and $B_j$ are both still binomial. I'll omit this proof but if you're interested I can add it. Now we have:
$A_j \sim Binomial(2j, 1/2)$
$B_j \sim Binomial(j, 1/2)$
So for each turn j, we should compare the probabilities $P(A_j \geq 20)$ and $P(B_j \geq 10)$. These can be found in terms of the Binomial CDF.
For your problem I have plotted these probabilities for turns 1 through 30.
Interestingly, as the game goes on longer, it appears the Alice has a higher chance of winning! But on average, the game will end after 20 turns and Bob still has a slightly higher probability at this point (.58 vs .56). Bob has a higher chance of winning early in the game, which ends up working in his favor!
UPDATE: We can actually derive an equation for P(Alice Wins). Since it is in terms of the Binomial CDF it has to be computed numerically, as the Binomial CDF depends on the Incomplete Beta Function.
THE EQUATION:
$P(\text{Alice Wins}) = \sum_{j=1}^\infty P(\text{Alice Wins On Turn j})$
$P(\text{Alice Wins On Turn j}) = \\ P(A_j \geq T_A, \ A_{j-1} < T_A)\bigl[P(B_j < T_B) + \frac{1}{2}P(B_j \geq T_B, \ B_{j-1} < T_B)\bigr] $
Let's break it down.
$P(\text{Alice Wins on Turn j}) = P_1(P_2 + \frac{1}{2}P_3)$
$P_1$ is just the probability that Alice reaches her Target on turn j (not before). $P_2$ is the probability that Bob hasn't yet reached his target, and $P_3$ is the probability that Bob also JUST reached his target. If this happens, then Alice wins only if she went first, which was a 50-50 chance, hence the $\frac{1}{2}$.
Now we must simply calculate the $P_i$.The easiest of which is $P_2$, just the cdf $F_{B_j}(T_B-1)$. $P_1$ and $P_2$ are somewhat more involved, although there calculations are the same exact idea.
$P(A_j \geq T_A, \ A_{j-1} < T_A) = \sum_{m=1}^{N_A}\sum_{n=m}^{N_A}P(A_{j-1} = T_A - m)P(A = n) $
I skipped the details, but the above is due to the fact that we can write what we want in terms of $A_{j-1}$ and $A$ (instead of $_j$), and these variable are independent.
It's a complicated problem, but we have all the peices we need to compute the exact probability that Alice wins, given parameters $N_A, T_A, O_A, N_B, T_B, O_B$ and even $P_A$, the probability that Alice goes first.
$P(\text{Alice Wins}) = \sum_{j=1}^\infty\\ \biggl[\sum_{m=1}^{N_A}\sum_{n=m}^{N_A}P(A_{j-1} = T_A - m)P(A = n)\biggr]\biggl[1-F_{B_j}(T_B-1) + \\ P_A\sum_{m=1}^{N_B}\sum_{n=m}^{N_B}P(B_{j-1} = T_B - m)P(B = n)\biggr]$
Indeed for the problem you described above, we see that Alice has only a 46.32907 % chance of winning. If you want to see more details, or play around with different values, the R-code which calculates the equation I've just described can be found here.