3
$\begingroup$

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$.

$\endgroup$
2
  • 1
    $\begingroup$ It seems like each $f_i$ is a geometric RV with success probability $p_i$. (There’s two conventions for such RVs, depending on whether you only count the tails flips.) So what you’d be studying is a sum of independent geometric RVs. Since the RVs are not identically-distributed, one can’t appeal to the central limit theorem. But one can use the usual tricks with characteristic functions to hopefully get something useful. $\endgroup$ Feb 26, 2023 at 20:11
  • 1
    $\begingroup$ Thank you for the suggestion. I used the probability-generation function (PGF) from the linked Wikipedia article, and then the sum of the RVs is given by the product of the PGFs -- call it $G(x)$. Finally, one can recover the probability that $n$ heads will come up after exactly $k$ flips by computing $G^{(k)}(0)/k!$, where $^{(k)}$ indicates the $k$-th derivative. Too bad the problem appears impossible to solve numerically for not-small $n$, due to exponential growth in the polynomial degree while computing derivatives. Thus, a closed-form solution would still be appreciated. $\endgroup$
    – swineone
    Feb 26, 2023 at 22:56

1 Answer 1

2
$\begingroup$

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).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .