Author 
Message 
David B. Chorlian science forum beginner
Joined: 31 Mar 2006
Posts: 2

Posted: Wed Jun 07, 2006 3:38 pm Post subject:
Combinatorial Probability Question



My apologies for reposting this.
Combinatorial Probability Question
Suppose there are M objects to be placed in N bins. What is the
probability distribution of the number of objects in the bin with the
largest number of objects? If K is the number, we say we want to find
P(K, M, N) for fixed M, N.
Clearly the number of possible ways of distributing the
objects is (M + N  1)!/(M!(N  1)!).
We have
P(M, M, N) = N/((M + N  1)!/(M!(N  1)!))
P(M  1, M, N) = N(N  1)/((M + N  1)!/(M!(N  1)!))
P(M  2, M, N) = N(N  1 + (N  1)(N  2)/2)/((M + N  1)!/(M!(N  1)!))
....
At this point I am at a loss. However, numerical simulation, taking
a small number of values for M and N, suggests that P has a
Poissonlike distribution.
Any pointers on this question?

David B. Chorlian
Neurodynamics Lab SUNY/HSCB
chorlian@cns.hscbklyn.edu
davidc@panix.com 

Back to top 


Chip Eastham science forum Guru
Joined: 01 May 2005
Posts: 412

Posted: Wed Jun 07, 2006 4:10 pm Post subject:
Re: Combinatorial Probability Question



David B. Chorlian wrote:
Quote:  My apologies for reposting this.
Combinatorial Probability Question
Suppose there are M objects to be placed in N bins. What is the
probability distribution of the number of objects in the bin with the
largest number of objects? If K is the number, we say we want to find
P(K, M, N) for fixed M, N.
Clearly the number of possible ways of distributing the
objects is (M + N  1)!/(M!(N  1)!).
We have
P(M, M, N) = N/((M + N  1)!/(M!(N  1)!))
P(M  1, M, N) = N(N  1)/((M + N  1)!/(M!(N  1)!))
P(M  2, M, N) = N(N  1 + (N  1)(N  2)/2)/((M + N  1)!/(M!(N  1)!))
...
At this point I am at a loss. However, numerical simulation, taking
a small number of values for M and N, suggests that P has a
Poissonlike distribution.
Any pointers on this question?

Hi, David:
Your counting of the ways of distributing the objects
indicates the objects are indistinguishable and the
bins are distinguishable (first bin, second, etc.)
Your probability formulas then indicates that you are
treating all such distributions as equally likely. This
seems unlikely to reflect a real world application, e.g.
where objects are assigned independently to bins.
In particular if the chance of assigning one object to
a bin is uniform, 1/N, then the chance of getting all
objects in the same bin would be:
N/N^M = N^(1M)
rather than the expression you gave for P(M,M,N).
regards, chip 

Back to top 


Stan Liou science forum addict
Joined: 27 Mar 2005
Posts: 54

Posted: Thu Jun 08, 2006 2:07 am Post subject:
Re: Combinatorial Probability Question



On Wed, 7 Jun 2006 15:38:36 +0000 (UTC), David B. Chorlian
<davidc@panix.com> wrote:
Quote:  My apologies for reposting this.
Combinatorial Probability Question
Suppose there are M objects to be placed in N bins. What is the
probability distribution of the number of objects in the bin with the
largest number of objects? If K is the number, we say we want to find
P(K, M, N) for fixed M, N.
Clearly the number of possible ways of distributing the
objects is (M + N  1)!/(M!(N  1)!).

Indeed. This is the number of nonnegative integer solutions to
x_1 + x_2 + ... + x_N = M,
indicating that you consider the bins to be distinguishable.
Quote:  We have
P(M, M, N) = N/((M + N  1)!/(M!(N  1)!))

Not so fast, as Mr. Eastham points out. The correct probability is
that of placing every object into the same bin, which is N^(1M).
Let's calculate the cumulative distribution function first. In that
case, what we're looking is the probability that in distributing M
objecting into N bins, every bin contains at most K objects. The
number of ways to do that is the coefficient of x^M in the
generating function F(x) = [1+x+...+x^K]^N = [1x^{K+1}]^N/[1x]^N.
Expanding this into a series (sums over nonnegative indeces)
F(x) = Sum_k[ C(N,k)(1)^k(x^{K+1})^k ]Sum_m[ C(N+m1,N1)x^m ],
so that the requisite coefficient should be
a_M(K) = Sum_k[ (1)^k C(N,k) C(N+Mk(K+1)1,N1) ].
(Note that the terms in the sum are zero for k > min{N,M/(K+1)}.)
And so the cumulative probability is
Q(K, M, N) = a_M(K)/[ C(M+N1,N1) ],
while the distribution is
P(K, M, N) = Q(K, M, N)  Q(K1, M, N), K > 0.
This might simplify, and there may be an easier method altogether,
but I haven't spent much time on this.

Stan Liou 

Back to top 


Patrick Coilland science forum Guru Wannabe
Joined: 29 Jan 2006
Posts: 197

Posted: Thu Jun 08, 2006 5:44 am Post subject:
Re: Combinatorial Probability Question



Stan Liou nous a récemment amicalement signifié :
Quote: 
Let's calculate the cumulative distribution function first. In that
case, what we're looking is the probability that in distributing M
objecting into N bins, every bin contains at most K objects. The
number of ways to do that is the coefficient of x^M in the
generating function F(x) = [1+x+...+x^K]^N = [1x^{K+1}]^N/[1x]^N.

Oh yes, very nice !
I did not know this method.
Quote: 
Expanding this into a series (sums over nonnegative indeces)
F(x) = Sum_k[ C(N,k)(1)^k(x^{K+1})^k ]Sum_m[ C(N+m1,N1)x^m ],
so that the requisite coefficient should be
a_M(K) = Sum_k[ (1)^k C(N,k) C(N+Mk(K+1)1,N1) ].
(Note that the terms in the sum are zero for k > min{N,M/(K+1)}.)

I do agree
Quote:  And so the cumulative probability is
Q(K, M, N) = a_M(K)/[ C(M+N1,N1) ],
while the distribution is
P(K, M, N) = Q(K, M, N)  Q(K1, M, N), K > 0.
This might simplify, and there may be an easier method altogether,
but I haven't spent much time on this.

Very nice.
Thanks

Patrick 

Back to top 


Google


Back to top 



The time now is Sun Nov 18, 2018 4:42 pm  All times are GMT

