Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
If $p$ is a constant that does not depend on the player or the basket, it must be $\frac1m$; is it? Also, note that there is exactly one winner for each non-empty basket, so the question is really just asking for the expected number of non-empty baskets. This certainly must depend on $n$ as well as on $m$, so $\frac{m}4$ cannot be right. – Brian M. Scott Nov 1 '12 at 2:10
... but a player can be winner in more than one basket. At the end, every basket will be won - but not every player will be winner. I think this is the misunderstanding. – AJed Nov 1 '12 at 2:14
Your description isn’t clear; as I read it, each player deposits only one label in only one basket. It now appears that you mean that each player goes down the line of baskets, and at each basket there is a probability of $p$ that he deposits a label; is that right? – Brian M. Scott Nov 1 '12 at 2:17
The correct answer can't possibly be $m/4$, because it might be that $m/4 > n$. – mjqxxxx Nov 1 '12 at 4:41
@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. – joriki Nov 1 '12 at 21:00
up vote 2 down vote accepted

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

share|cite|improve this answer
I reached the same answer using another way. Well, prob of winning at least one is $1 - B(m,0) = 1 - (1-w)^m$ where $B$ is binomial dist, and $w$ is the prob of winning. $w$ for player $i$ is $p.q^{i-1}$ ($i \in \{1, .., n\}$). The sum of all probabilities of winning at least one is exactly what you had ! -- thanks for the simplification ! – AJed Nov 1 '12 at 21:54
That was thanks to… – AJed Nov 1 '12 at 22:01
@AJed: Cross-posting without linking the questions to each other is very bad style. It wastes people's time by duplicating their efforts. – joriki Nov 1 '12 at 22:56
next time i will take that into consideration – AJed Nov 1 '12 at 23:27
@AJed : Thanks! – joriki Nov 1 '12 at 23:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.