The Asymmetric Coin Toss Problem

As promised I am back with a new problem from the collection. For new readers, I have recently started a new series where I bring interesting probability puzzles and their solutions to present some revealing aspect of our thought process — something which I really wanted when I learnt about Probability (someone who can walk me through each step and guide why some way of thinking was wrong). You can also contribute your problems or solutions to this series, by reaching me out on LinkedIn, Twitter, Instagram or Email.

The problem goes like this…
Two gamblers are playing a coin toss game. Gambler A has (n + 1) fair coins; B has n fair coins. What is the probability that A will have more heads than B if both flip all their coins?

Gambler A has an edge with having one extra coin than B. Both tosses their coin. There are two complementary cases [A has more heads than B] or [A does not have more heads than B].

Isn’t it obvious? If A has more coins, the chances of him/her getting more heads is more than B is more. But the question is exactly how much more.

Let’s cast the problem from a seemingly unstructured one into the formal probabilistic framework by using random variables and events.

We define two basic random variables

Now, that we have these random variables to our disposal the question asks us to find the following probability,

The probability we want to find of the number of heads of A being more than that of B

This required probability can be evaluated using two ways. One being the lazy one and the other being the calculative one. Being a lazy person, I will try circumventing the calculative approach.

Let’s start with the lazy proof, which relies on a key aspect of the problem i.e. B is in someway a subset of A (not in a strict mathematical sense). What I mean by this? The first n coins of A are iid with the n coins of B. To delineate it, we define some extra random variables.

We have formally established how B’s coins are related probabilistically to A’s coins except the last coin

We will see how this sort of decomposition of N_A greatly simplifies the problem, allows us to use the symmetry between N_A’ and N_B and lazily solve the problem, which would otherwise be a calculation massacre.

We use the Law of Total Probability and split the required probability into cases

We are now in a position to reason out the values of each of these smaller chunks of probabilities.

All these probabilities are in fact trivial, although they might look bit complex at the first glance. What I have done is, assuming the given condition, tried to evaluate the conditional probabilities. You can either do this computation using the definition of conditional probability or orally with logic (try)

Substituting these back in the original expression we get,

Looks quiet simplified with a major benefit being N_A’ and N_B being iid r.v.s

You may feel like is that all we can simplify lazily before getting our hands dirty with combinatorial expressions? It seems not. Thanks to the sum of probability to 1 rule.

The second step is because N_A’ and N_B are identically distributed by symmetry or due to iid argument we mentioned before

But, wait a second! How can it be 1/2? Shouldn’t A with more coins than B have higher probability of having more heads? Hmm. Let me point out a flaw in this way of thinking. Suppose A and B both have 1 coins. What’s the probability that [A has more heads that B]? If you answered 1/2, that’s exactly where you are committing a mistake thinking it is obvious. Being a little pedantic would help us here in understanding.

The probability of A having more heads than B is indeed <1/2.

But the reason for such idiosyncrasy is that we are not dealing with continuous random variables where equality of random variables has 0 probability. You can see above that if we somehow didn’t have the (HH) and (TT) case then our intuition would match. But as they take up non-zero probabilities it shatters our intuition (You can verify easily that this holds for A and B having n coins each, using the sum of probability of all possible events is equal to 1). Therefore, it is clear that to have 1/2 probability we would require uneven number of coins.

The simplest case of uneven coins is having a difference of 1 coin. Why not add the extra coin to B? Because we are looking to increasing P[N_A>N_B] to 1/2. Adding to B, would decrease 1/4 obtained earlier.

So, let’s take A and B with n coins each and calculate the probability of the possible cases to hint us the direction to go into to try making the probabilities equal (The above example definitely gives us a hint).

Take n coins with each A and B

Start with the sum of all the possible cases equal to 1. Then try splitting into two equal parts using our idea of symmetry between N_A > N_B and N_A < N_B (With clear argument, try showing that they are symmetrical)

Cool, so we have split all our case into 2 equal parts. But what practical change, in the setup of both A and B having n coins, give us one of these parts as its probability? Okay, learning time now. There is an idea called randomization in Statistics, where in order to split a bigger event into parts of some desired probability (smaller than the bigger event) we use a biased or unbiased coin (or some randomization device) and based on the outcome of that device we make a stochastic (non-deterministic) decision. The randomization we use in this case is:

If the number of heads between A and B are different, do nothing. But if the number of heads of A equals that of B, then toss a fair coin and count this case under the event [A has more heads than B] if turns up head otherwise count this case under the event [A does not have more heads than B].

What does this do? If number of heads differ we leave A and B untouched. But if there is a ambiguity whether to count the current case as [A has more heads than B] or [A does not have more heads than B] (which happens when the number of heads in A and B are equal), then simply toss a fair coin to decide between the two. This tantamount to achieving split we discussed above physically (Calculate the probability to verify).

The randomization which we used though being correct can be simplified to:

Add one extra (n+1 th) coin to A before tossing the coins of A and B.

Why does this work? Because that extra final coin of A does not change the decision of initial n heads between A and B are different. If initial n coins have same number of heads, the head outcome of the final coin adds this case under the event [A has more heads than B] and tail outcome of the final coin adds this case under the event [A does not have more heads than B]. Thus, being the same as before said randomization but being simpler. Let’s verify whether our thought process was correct by running a simulation in the next section.

The Python code for simulation of the above scenario

# necessary imports
import numpy as np

# a function which results in `1` if A has more heads than B otherwise 0 given the value of n
def toss_outcome(n):
  # A has n+1 coins
  num_heads_A = np.sum((np.random.random(n+1) >= 0.5))
  # B has n coins
  num_heads_B = np.sum((np.random.random(n) >= 0.5))
  
  # outcome return
  return int(num_heads_A > num_heads_B)

# Running simulation with A having 11 coins and B having 10 coins
n = 100
N = 100000
print(f'The proportion of {N} times when [A has more heads than B]:', np.mean([toss_outcome(n) for _ in range(N)]))

The outcome of the above simulation is:

The proportion of 100000 times when [A has more heads than B]: 0.50224

Wola! Correct! What we did to solve this problem gave us a new perspective of looking at it, which initially looked like a simple asymmetric coin toss case. We then dissected to figure out artfully why the problem doesn’t align with our initial thoughts and while doing so, with a slight digression to randomization, we figured out how the problem might have been framed :)