2

Consider the following problem.

Problem
Take two fair coins, A and B. A "round" is when both coins are tossed at the same time. What is the expected number of rounds until both coins have independently been heads at some point?

For example, the sequences $((H, T), (H, H))$ and $((H, T), (T, T), (T, H))$ would satisfy the condition. The coins don't have to be heads at the same time and coins can be heads multiple times; all that matters is that they have both been heads at some point.

I already know how to solve this problem: the answer is $\frac{8}{3}$. (See below if you're interested.)

Solution
Let $f(a, b)$ be the expected number of tosses that still need to be done, where $a$ is $T$ ("true") if A has been heads at some point and $a$ is $F$ ("false") otherwise; and similarly so for $b$. The challenge is to find out what $f(F, F)$ is.

Trivially $f(T, T) = 0$ because at that point we have achieved the goal. More interestingly, however, \begin{align*} f(T, F) &= 1 + \frac{1}{2} f(T, F) + \frac{1}{2} f(T, T) \\ &= 1 + \frac{1}{2} f(T, F) \end{align*} because we always take one round, and on top of that there is a 50% chance that B is heads in which case we're done, and a 50% chance that we did not make progress. Solve for $f(T, F)$ to find $f(T, F) = 2$. Similarly, because A and B are identical coins, $f(F, T) = 2$.

Next, observe that \begin{align*} f(F, F) &= 1 + \frac{1}{4} f(F, F) + \frac{1}{4} f(F, T) + \frac{1}{4} f(T, F) + \frac{1}{4} f(T, T) \\ &= 1 + \frac{1}{4} f(F, F) + \frac{2}{4} + \frac{2}{4} + \frac{0}{4} \\ &= 2 + \frac{1}{4} f(F, F). \end{align*} Solve for $f(F, F)$ to find $f(F, F) = \frac{8}{3}$.

Question

My question, instead, is what kind of distribution is this? In particular, what distribution is this if we generalise the number of coins to any positive integer $n$? I'm writing my thesis and because I'm not working in the field of statistics I want to refer to an existing body of work instead of introducing the maths myself. I looked at the multinomial distribution, multivariate hypergeometric distribution, and many more, but none seem to describe my problem here.

Is there any distribution that describes the expected number of multi-variate categorical Bernoulli trials until all categories (each with one instance) have been satisfied, without replacement?

FWDekker
  • 152

1 Answers1

2

We can model this distribution as the maximum of $n$ geometric distributions. Let $X$ be the random variable that counts the number of coin flips until a coin comes up heads, and say the coin comes up heads with probability $p$. Then

$$\Bbb P(X=k)=(1-p^{k-1})p$$

You'd want to look for the distribution of

$$Y_n = \max_{i=1,\dots,n} X_i,$$

where $X_i\sim X$. I'm not sure if this already has a name, but at least you can speak of it in terms of already known constructs (geometric distributions).

We have

$$\begin{align} \Bbb P(Y_n \leqslant k) &= \Bbb P(X_1 \leqslant k)^n \\&= {\left(1-(1-p)^k\right)}^n \end{align}$$

Fimpellizzeri
  • 23,126