5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Just so I'm clear on what's going on here: In the posited problem, Alice repeatedly (on her turn) flips two coins, and adds the number of tails to her tally, while Bob repeatedly (on his turn) flips a single coin, and adds the number of tails to his tally. If Alice reaches $20$ before Bob reaches $10$, she wins; otherwise, Bob wins. Is that right? $\endgroup$ – Brian Tung Nov 30 '16 at 0:28
  • $\begingroup$ @Brian Tung: Yes, that's right. $\endgroup$ – Teller Nov 30 '16 at 0:31
  • $\begingroup$ This isn't a complete answer, but note that if we let $X_A$ and $X_B$ be random variables representing the number of turns required for Alice and Bob to reach their totals, respectively, then $X_A$ is the half the sum (rounded up) of $20$ geometrically distributed random variables with parameter $1/2$, and $X_B$ is the sum of $10$ such random variables. Two observations: One, such small counts are not enough for the distributions of $X_A$ and $X_B$ to become indistinguishable from normal, and $X_B$ will retain more of a heavy (right-side) tail than $X_A$. (cont'd) $\endgroup$ – Brian Tung Nov 30 '16 at 0:47
  • $\begingroup$ And two, $X_A$ has to be rounded up. I think that half a turn is probably not negligible either. $\endgroup$ – Brian Tung Nov 30 '16 at 0:47
  • $\begingroup$ Part of the intuition is that when Alice wins she may have 20 or 21 tails, therefore one tail may be wasted. Bob, on the contrary, will never waste a flip. $\endgroup$ – A.G. Nov 30 '16 at 0:53
6
$\begingroup$

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.

enter image description here

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.