Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
We have n actors. Each actor chooses from n*2 actions. How can I calculate the probability that at least one actor will choose a unique outcome?
For example, say we have 5 pickup artists in a town with 10 bars. Each PUA chooses a bar at random. What are the odds that at least one PUA will have a bar to himself/herself?
This is relevant to some work I'm doing on scheduling in a distributed system. I know that the relevant equation should probably start with $\binom{n + 2n -1}{n}$, but then what?
This is not a simple calculation in general, though the probability will be almost 1 if $n$ is any substantial size.
To take your example of five people and 10 bars, there are $10^5$, i.e 100,000 possible equally-likely distributions. All of these will have at least one person alone, except the 10 cases where all five are in a single bar or the 900 cases where three are in a particular bar and two in another. That leaves 99090 distributions which satisfy your condition, more than 99%.
Note that 99090 is not divisible by $\binom{5 + 10 - 1}{5} = 2002$.
For $n=1$ to $6$, the fractions seem to be $\frac{2}{2},$ $\frac{12}{16},$ $\frac{210}{216},$ $\frac{3920}{4096},$ $\frac{99090}{100000}$ and $\frac{2962872}{2985984}$, where the denominator in each case is $(2n)^n$. I would expect the probabilities then to keep rising as $n$ increases beyond 6.
Below, I briefly sketch out one "back of the envelope" calculation, which is in no way optimal, but does at least show that the probability converges to one exponentially fast. Before getting into the (gory) details, we give the answer.
$$ \Pr(\text{at least one actor chooses a unique outcome}) \geq 1 - (e/4)^{n/2} . $$
As mentioned before, comparing this result to the above for small $n$ shows that the result is not super sharp. But, it does provide a guarantee for all $n$ and shows that as $n$ grows, the probability goes to 1 at least exponentially fast. (The actual rate is probability more like $e^{b n \log n + o(n)}$).
The idea is to turn the problem into an occupancy or coupon-collecting problem. If you want a more precise answer, you can refer to the (extensive) literature on these subjects, but to prove a faster rate takes messier analysis.
Let $U_n$ be the proportion of actors that choose a unique outcome (when we have $n$ total actors), which we use below. (Technically, the analysis below is for even $n$, but that's a minor point. The same result holds for odd $n$; just replace $n/2$ by $(n-1)/2$ and $3n/2$ by $(3n+1)/2$ in the relevant places.)
Restating the problem in terms of balls and bins. We have $n$ balls and $2n$ bins. The "balls" are the "actors" and the "bins" are the possible outcomes. We want to know the probability that at least one bin has only a single ball in it. The probability that any particular bin has only one ball is $\left(1 - \frac{1}{2n}\right)^n$. So, the expected proportion of balls in a bin by themselves (i.e., actors that choose a unique outcome) is
$$ \mathbb{E}(U_n) = \left(1 - \frac{1}{2n}\right)^n \to e^{-1/2} \approx 60.65\% $$
This gives us pretty good hope that the probability of at least one ball being in a bin by itself is (very) high.
To get a bound on this probability, note that if each of the occupied bins has at least two balls in it, then at most $n/2$ bins can be occupied. So
$$ \Pr(\text{no bin has exactly 1 ball}) \leq \Pr(\text{no more than n/2 bins are occupied}) $$
Now, if no more than $n/2$ bins are occupied, then there must be some subset of $3n/2$ bins that are all empty. There are ${2n \choose 3n/2} = {2n \choose n/2}$ such subsets, and so by the union bound, we get
$$ \Pr(\text{some subset of 3n/2 bins is empty}) \leq {2n \choose n/2} \left(1 - \frac{3n/2}{2n}\right)^{n} = {2n \choose n/2} 4^{-n} $$
To finish up, we use the elementary inequality
$$ {2n \choose n/2} \leq \left(\frac{2n e}{n/2}\right)^{n/2} = (4e)^{n/2} . $$
Putting it all together, we get
$$ \Pr(\text{no bin has exactly 1 ball}) \leq (4 e)^{n/2} 4^{-n} = (e/4)^{n/2} . $$
Hence,
$$ \Pr(\text{at least one actor chooses a unique outcome}) \geq 1 - (e/4)^{n/2} . $$
