- The average number of tries, to pull x specific numbers from a set of numbers.
An example: You are playing bingo by yourself and have 1 bingo-card with 15 different numbers ranging from 1 to 90.
How many times do you, on average, have to pull a number (from 1 to 90) to get all of your 15 different numbers? (We are asuming the pulled numbers don't repeat).
Now, what if you were playing with 99 friends, that is, 100 bingo-cards at once. How would the average number change? – How many turns would the average game be, and how do we calculate that.
Thanks in advance.
Best Answer
Say you have $n$ numbers (here $n=90$) and you want to draw $k$ of them (here $k=15$).
The probability to have drawn all $k$ numbers by the time the $m$-th number is drawn is
$$ \frac{\binom{n-k}{m-k}}{\binom nm}\;, $$
since there are a total of $\binom nm$ combinations of numbers that could be drawn, and your $k$ specific numbers are drawn if the remaining $m-k$ numbers drawn are any combination of the remaining $n-k$ numbers. Thus the expected value of the number $X$ of draws required until your $k$ specific numbers are drawn is
\begin{eqnarray} \mathsf E[X] &=& \sum_{m=0}^\infty\mathsf P(X\gt m) \\ &=& \sum_{m=0}^n\left(1-\frac{\binom{n-k}{m-k}}{\binom nm}\right) \\ &=& n+1-\frac{n+1}{k+1} \\ &=& (n+1)\frac k{k+1}\;. \end{eqnarray}
The result $\frac{n+1}{k+1}$ for the sum over the second term is quite a simple result for a complicated sum that’s not easy to evaluate, so we should consider whether there’s a simpler way to derive the result. Indeed there is.
Imagine the numbers you want as $k$ red balls among $n$ balls. We want to know the expected index of the last red ball if we arrange all $n$ balls in a uniformly random linear order. To find this, add a $(k+1)$-th red ball, arrange the $n+1$ balls in a uniformly random circular order, and uniformly randomly pick one of the $k+1$ red balls to remove to break the circle into a line. The resulting distribution is the same as if we had just arranged the $n$ balls in a uniformly random linear order. By the symmetry of the circle, each of the $k+1$ intervals between two red balls (including one of them) contains the same expected number of balls, so this expected number must be $\frac{n+1}{k+1}$; and that is the number of balls from the end of the line up to (and including) the last red ball.
For the case where $j$ people are playing (here $j=100$), there’s no such elegant argument (that I know of), so we have to take the hard way through the sum. The probability that none of you have had all your numbers drawn is the $j$-th power of the probability that one of you has not had all their numbers drawn, so the expected value of the number $Y$ of draws until at least one person has had all their numbers drawn is
\begin{eqnarray} \mathsf E[Y] &=& \sum_{m=0}^\infty\mathsf P(Y\gt m) \\ &=& \sum_{m=0}^n\left(1-\frac{\binom{n-k}{m-k}}{\binom nm}\right)^j\;. \end{eqnarray}
I don’t think this can be simplified. For your case, the sum evaluates to approximately $66.52$.