3
$\begingroup$

There are $n$ players with distinct labels from $\{1, ..., n\}$. There are also $m$ baskets. For each basket, each player has an independent probability $p$ of putting a small piece of paper with their label into the basket. Each non-empty basket is won by the player who placed the lowest label into the basket. A player who wins at least one basket is a winner.

What is the expected number of winners?

  • 1
    @AJed: I tried to make the question reflect the intended meaning that your comments seem to suggest. Please check whether I got it right. Note that the randomization of the labels was superfluous, since in any case the $n$ players will have each of the labels exactly once, and a permutation among the players doesn't bear upon the result.2012-11-01

1 Answers 1

2

The probability of player $1$ being a winner is the probability that player $1$ places a label into some basket, which is $1-(1-p)^m$.

The probability of player $2$ being a winner is the probability that player $2$ places a label into some basket into which player $1$ doesn't place a label, which is $1-(1-p(1-p))^m$.

The probability of player $k$ being a winner is the probability that player $k$ places a label into some basket into which players $1$ through $k-1$ don't place a label, which is $1-\left(1-p(1-p)^{k-1}\right)^m$.

Thus the expected number of winners is

$ \sum_{k=1}^n\left(1-\left(1-p(1-p)^{k-1}\right)^m\right)\;. $

I don't see how to get a closed form without summation for this. If $n\gg m$, you can transform it into a sum up to $m$ so you have fewer to terms to sum:

$ \begin{align} \sum_{k=1}^n\left(1-\left(1-p(1-p)^{k-1}\right)^m\right) &= n-\sum_{k=1}^n\sum_{j=0}^m\binom mj(-p)^j(1-p)^{j(k-1)} \\ &= n-\sum_{j=0}^m\binom mj(-p)^j\frac{1-(1-p)^{jn}}{1-(1-p)^{j\hphantom n}}\;. \end{align} $

  • 0
    Good question, but why does adding the individual probabilities give the expected value? I'm a little confused...2012-11-02