Number of coin flips required to get heads for every unfair coin in a set

probabilityprobability distributions

Suppose I have $n$ unfair coins, but each is distinctly unfair: the $i$-th coin ($1 \leq i \leq n$) has probability $p_i$ of landing on heads and $1 – p_i$ of landing on tails.

I repeatedly flip the first coin until I get heads, while taking note of how many flips were required to get heads, which I call $f_1$. I repeat this process for each of the $n$ coins, taking note of each $f_i$.

Is there a standard probability distribution for the random variable $f_T = \sum_{i = 1}^n f_i$? The closest I've found is the Poisson binomial distribution, but it doesn't account for the rule of flipping the coins again until they land on heads.

In particular, I'm looking for the value of $k$ such that, for a given set of parameters ($n$ and the set $P = \{ p_1, \ldots, p_n \}$) plus a probability $q$ (say 99.999%), at most $k$ flips (across all coins) will be required to get heads from each of the $n$ coins, with probability $q$. Put it another way, the probability of needing $> k$ flips is $1 – q$.

Best Answer

I was able to numerically solve the problem in my range of interest of $n$ by the following procedure, inspired by probability-generating functions:

  1. For each coin $i$, initialize a polynomial such that the coefficient of $x^k$ is $(1 - p)^{k - 1} p$ (i.e. the probability, in the geometric distribution, of heads coming up for the first time in the $k$-th throw), except for the constant coefficient, which is initialized to zero. I cut off the polynomial when the probability becomes “sufficiently low” (heuristically).
  2. Multiply together all these polynomials.
  3. Perform a prefix sum of the coefficients.

I used SageMath with RealField coefficients of a suitable precision. I was able to compute this for $n$ in the range of hundreds very quickly (under a minute).

Related Question