Duelling Idiots and Other Probability Puzzlers

When human flesh begins to fail

Consider $N$ people, all independently flipping their own fair coins. If each flips his or her coin $n$ times, then what is the probability that all $N$ people get the same number of heads?

Solution

Probability of one person getting $k$ heads in $n$ flips = ${n \choose k} \left(\frac{1}{2}\right)^n$. Probability of all the $N$ people getting $k$ heads = $\left({n \choose k} \left(\frac{1}{2}\right)^n\right)^N$. Therefore, the probability of all the $N$ people getting the same number of heads is $\mathbb{P}(N,n) = \sum_{k=0}^n \left({n \choose k} \left(\frac{1}{2}\right)^n\right)^N$.

Who pays for the coffee?

If each of $N$ people desires a cup of coffee, then each one individually flips, a fair coin simultaneously with the others, to determine the one person who will pay for all $N$ cups. If all the coins but one show the same face, then the odd person out is the one who pays. If any other combination of heads and tails shows on the coins, then all $N$ people flip again. On average, how many flips are required to get an odd person out when $N$ people play with fair coins? Suppose $N — 1$ people have fair coins and the Nth person has a biased coin, i.e., a coin that shows heads with probability $q$ and tails with probability $1 — q$. How does this change the theoretical result?

Solution

The probability of identifying the odd one out in a turn is the probability of getting $N-1$ tails or $N-1$ heads out of $N$ flips = $2\frac{N}{2^n} = \frac{N}{2^{N-1}}$. The number of turns is a random variable with a Geometric Distribution where $p = \frac{N}{2^{N-1}}$. Therefore, the average number of turns required to identify the odd one out is given by $\frac{2^{N-1}}{N}$. It can be easily shown that the presence of a biased coin has no effect. The average duration of a game, therefore, will also be unchanged.

Solution with one biased coin

We have $N — 1$ people, each with a fair coin, and an $N^{th}$ person with a coin biased such that $\mathbb{P}(heads) = q$ and $\mathbb{P}(tails) = 1 — q$. To get an odd person out on a given simultaneous flipping, $N — 1$ of them must get one result and one get the other result. This can happen in the following ways:

1. The $N — 1$ people with fair coins all get heads and the person with the biased coin gets tails; the probability of this is $\frac{1}{2^{N-1}}(1-q)$.

2. The $N — 1$ people with fair coins all get tails and the person with the biased coin gets heads; the probability of this is $\frac{1}{2^{N-1}}q$.

3. The person with the biased coin gets heads, as do $N — 2$ of the $N — 1$ people with fair coins, and the remaining person with a fair coin gets tails. Since there are $N — 1$ ways to pick the person with a fair coin who is the odd person out, then the probability of this is $q\frac{1}{2^{N-2}}(N-1)\frac{1}{2}$.

4. The person with the biased coin gets tails, as do $N — 2$ of the $N — 1$ people with fair coins, and the remaining person with a fair coin gets heads. Since there are $N — 1$ ways to pick the person with a fair coin who is the odd person out, then the probability of this is $(1-q)\frac{1}{2^{N-2}}(N-1)\frac{1}{2}$.

So, the total probability of an odd person out is the sum of the above probabilities = $\frac{N}{2^{N-1}}$.

Computational Verification

from scipy.stats import bernoulli
from numpy import hstack
runs = 1000
N = 6
p, q = 0.5, 0.9
tl = 0
for _ in range(runs):
    l = 0
    while True:
        l += 1
        flips = hstack((bernoulli.rvs(p, size=N-1), bernoulli.rvs(q, size=1)))
        if sum(flips)==1 or sum(flips)==(N-1):
            break
    tl += l
print(tl/runs)

Ball Madness

Problem 1

Two urns (let’s call them $I$ and $II$) each contain $n$ balls. Initially, at time $t = 0$, all of the balls in I are black and all of the balls in II are white. Then, at time $t=1$ (in arbitrary units), a ball is selected at random from each urn and instantaneously placed in the other urn. This select-and-transfer, or exchange process, is repeated at times $t = 2, 3, \dots.$ At any given time each urn always contains $n$ balls, but only at $t = 0$ are the colours of the balls in a given urn necessarily identical. The words “selected at random” mean that the probability of selecting a black ball from an urn containing $b$ black balls is $b/n$. At any given time, the state of both urns is completely determined by specifying the number of black balls in $I$ (or the number of white balls in $II$).What are the state transition probabilities?

Simulation

import altair as alt
alt.renderers.enable('default')
from random import random
import pandas as pd

n = 1000
t = 4999
b1, b2 = n, 0
history = [(b1/n,b2/n)]
for _ in range(t):
    tb1, tb2 = 0, 0
    if random() < b1/n:
        tb1 = 1
    if random() < b2/n:
        tb2 = 1
    b2 += (tb1-tb2)
    b1 += (tb2-tb1)
    history.append((b1/n, b2/n))

source = pd.DataFrame({
  't': range(t+1),
  'fb1': [fb1 for fb1,_ in history]
})

alt.Chart(source).mark_line().encode(
    x='t',
    y='fb1'
)