If there are $n$ total objects that are distributed randomly to $p$ people, what is the probability of any one person getting at least $k$ objects? If I take the case of $p = 7$, $n = 3$, and $k = 3$, Its the simple case of
$$ \frac17 \dot{} \frac17 \dot{} \frac17 \dot{} \frac71 = \frac17^{2} = p \cdot \frac1p^{k}$$ Which is the chance of getting all three objects, multiplied by 7 because there are 7 people. In the case of $p = 7$, $n=4$, and $k=3$, there is one additional object, but still finding the chance of getting at least 3 objects. I would think it looks like:
$$7 \cdot \left( \frac17^3 \frac67^1 \frac{4!}{3! 1!} + \frac17 ^4 \right)= p \cdot \left( \frac1p^{k} \frac{p-1}p^{n-k}\frac{n!}{k! (n-k)!} + \frac1p ^n \right)$$
The first term is the chance of getting three objects times the probability of not getting the fourth multiplied by the number of ways you can achieve that combination of outcomes. the second term is the chance of getting all 4 objects and there is only one way to get that outcome. Finally it's all multiplied by 7 because there are 7 people. If $n$ is increased yet again to 5, I can see a pattern emerge.
$$ 7 \cdot \left(\frac17^3 \frac67^2 \frac{5!}{3!2!}+ \frac17^4\frac67 \ \frac{5!}{4!1!} + \frac17^5\right) = \\ p \cdot \left( \frac1p^{k} \frac{p-1}p^{n-k} \frac{n!}{k! (n-k)!} + \frac1p^{k+1}\frac{p-1}p^{n-k-1} \frac{n!}{(k+1)! (n-k-1)!} + \frac1p ^n \right) $$
I can redefine this equation with:
$$p \sum_{i=0}^{n-k} \left(\frac1p \right)^{k+i} \left(\frac{p-1}{p} \right)^{n-k-i} \left( \frac{n!}{(k+i)!(n-k-i)!} \right)$$
I ran a simple simulation with 10$^8$ trials for various values of n. Keeping the same $k$ and $p$ values, my calculation matches my simulation for $n=3,4,$ and $5$. But after 5, it diverges from my simulation. If I remove the $p$ from the beginning, I get incorrect values, but as $n \rightarrow \infty$, my solution approaches 1, which indicates I'm on the right track.
Can anyone help me fix my broken formula to find a general solution for the probability of getting at least $k$ put of $n$ objects distributed $p$ ways?
a) Premise
Let's clear first of all a source of possible (and frequent) misunderstanding in this combinatorics field.
When we speak of
Distributing (randomly) $n$ equal objects among $p$ people
in the same sense as
throwing at random $n$ (un-distinguishable) balls into $p$ (distinguishable) bins, we individuate a process that - although the objects are un-distinct - nonetheless it attaches a label to them, which is the position in the launching sequence.
Having $p$ equi-probable choices as where to put the first object, and same for the other following, means that the equiprobable space is given by :
- all the $n$-uples with integer values ranging in $1,\cdots,p$, or
- all the points with integer coordinates in the $n$-D cube with side length $p$, or
- the number of words of length $n$ with character from the alphabet $\{1,\cdots,p\}$, ....
and that the number of equi-probable results is $$ \bbox[lightyellow] { p^n}$$ See also this related post.
Taking the "words" exemplification which is more "visible", let's then associate to each word a histogram of the frequency of each character.
One such histogram is just the representation of a random "deposition " of (i.e. pouring alltogether) $n$ un-distinguishable balls into $p$ distinguishable boxes. Depositions (don't know a better or standard word) being considered different if the corresponding frequency arrays are different. So each "deposition" corresponds to an integer point in the $p$-D space, lying on the diagonal plane $x_1+x_2+\cdots+x_p=n$.
The difference with the "random throwing" is thereby geometrically evident.
Also, each histogram will be a weak composition of $n$ into $p$ parts. The number of different histograms is therefore and $$ \bbox[lightyellow] { \binom{n+p-1}{n}= {{p^{\,\overline {\,n\,} } } \over {n!}}}$$ and for $1 < n,p$ this is less than $p^n$.
Finally, it is clear that one histogram corresponds to all the various different words in which the characters are permuted.
b) "throwing" interpretation
If we expand $$ \left( {x_{\,1} + x_{\,2} + \cdots x_{\,p} } \right)^{\,n} $$ we get a representation of all the possible ways to distribute the $n$ objects to $p$ people.
Therefore, the number of distributions where at least one person receives at least $k$ objects is $$ \bbox[lightyellow] { N(n,p,k) = p^{\,n} - \sum\limits_{\left\{ {\matrix{ {\,v_{\,j} \, < \;k} \cr {\sum\limits_j {v_{\,j} } = n} \cr } \;} \right.} {\;\left( \matrix{ n \cr v_{\,1} ,v_{\,2} , \cdots ,v_{\,p} \cr} \right)} }$$ and it doesn't look that further process might lead to a simpler formulation.
But from that we can retrieve an interesting recurrence relation.
Let's indicate with $M(n,p,m)$ the number of ways to
distribute $n$ objects among $p$ persons so that nobody receives more than $m$ objects,
that is $$ \eqalign{ & M(n,p,m) = \sum\limits_{\left\{ {\matrix{ {\,v_{\,j} \, \le \;m} \cr {\,\sum\limits_{1\, \le \,j\, \le \,p} {v_{\,j} } \; = \;n} \cr } \;} \right.} {\;\left( \matrix{ n \cr v_{\,1} ,v_{\,2} , \cdots ,v_{\,p} \cr} \right)} = \cr & = \sum\limits_{0\, \le \,\,k\, \le \;m} {\;\sum\limits_{\left\{ {\matrix{ {\,v_{\,j} \, \le \;m} \cr {\;\sum\limits_{1\, \le \,j\, \le \,p} {v_{\,j} } \; = \;n - k} \cr } \;} \right.} {\;\left( \matrix{ n \cr v_{\,1} ,v_{\,2} , \cdots ,v_{\,p - 1} ,k \cr} \right)} } = \cr & = \sum\limits_{0\, \le \,\,k\, \le \;m} {\;\left( \matrix{ n \cr k \cr} \right)\sum\limits_{\left\{ {\matrix{ {\,v_{\,j} \, \le \;m} \cr {\;\sum\limits_{1\, \le \,j\, \le \,p - 1} {v_{\,j} } \; = \;n - k} \cr } \;} \right.} {\;\left( \matrix{ n - k \cr v_{\,1} ,v_{\,2} , \cdots ,v_{\,p - 1} \cr} \right)} } = \cr & = \sum\limits_{0\, \le \,\,k\, \le \;m} {\;\left( \matrix{ n \cr k \cr} \right)M(n - k,p - 1,m)} \cr} $$ with the understanding that $M(n,p,m)$ is null when any of the parametrs is negative.
So we can conclude that $$ \bbox[lightyellow] { \left\{ \matrix{ M(n,p,k) = 0\quad \left| {\;n < 0\; \vee \;p < 0\; \vee \;k < 0} \right. \hfill \cr M(n,p,k) = \left[ {0 = n} \right]\left[ {0 = p} \right] + \sum\limits_{0\, \le \,\,j\, \le \;k} {\;\left( \matrix{ n \cr j \cr} \right)M(n - j,p - 1,k)} \hfill \cr N(n,p,k) = p^{\,n} - M(n,p,k - 1) = M(n,p,n) - M(n,p,k - 1) \hfill \cr} \right. }$$ where $[P]$ denotes the Iverson bracket $$ \left[ P \right] = \left\{ {\begin{array}{*{20}c} 1 & {P = TRUE} \\ 0 & {P = FALSE} \\ \end{array} } \right. $$