2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ the matter is that $p^n$ is the number of ways of distributing $n$ labelled objects $\endgroup$ – G Cab Mar 12 '18 at 23:24
  • $\begingroup$ you should get Prob.=1 as soon as $n$ is greater than $(k-1)p$ $\endgroup$ – G Cab Mar 12 '18 at 23:50
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Perhaps its an error on my part, but as n increases, my answer gets smaller. As n increases, the answer should approach 1. $\endgroup$ – Ryan Mar 12 '18 at 22:58
  • $\begingroup$ @Ryan: uhm, you are right, something doesn't match. I shall rethink on it $\endgroup$ – G Cab Mar 12 '18 at 23:07
  • $\begingroup$ @Ryan: what did not match in fact, is the interpretation to give to " .. distributed randomly ..": I tried and make it clear about two possible interpretations of that. Let me know if I can be more of help. $\endgroup$ – G Cab Mar 14 '18 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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