Search   Memberlist   Usergroups
 Page 1 of 1 [4 Posts]
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
Poisson-like distribution.
Any pointers on this question?

--
David B. Chorlian
Neurodynamics Lab SUNY/HSCB
chorlian@cns.hscbklyn.edu
davidc@panix.com
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 Poisson-like 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^(1-M)

rather than the expression you gave for P(M,M,N).

regards, chip
Stan Liou

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^(1-M).

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 = [1-x^{K+1}]^N/[1-x]^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+m-1,N-1)x^m ],
so that the requisite coefficient should be
a_M(K) = Sum_k[ (-1)^k C(N,k) C(N+M-k(K+1)-1,N-1) ].
(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+N-1,N-1) ],
while the distribution is
P(K, M, N) = Q(K, M, N) - Q(K-1, 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
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 = [1-x^{K+1}]^N/[1-x]^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+m-1,N-1)x^m ], so that the requisite coefficient should be a_M(K) = Sum_k[ (-1)^k C(N,k) C(N+M-k(K+1)-1,N-1) ]. (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+N-1,N-1) ], while the distribution is P(K, M, N) = Q(K, M, N) - Q(K-1, 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

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [4 Posts]
 The time now is Thu Feb 21, 2019 8:05 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics Question about Life. socratus Probability 0 Sun Jan 06, 2008 10:01 pm Probability Question dumont Probability 0 Mon Oct 23, 2006 3:38 pm probability gorbag Probability 0 Mon Aug 14, 2006 11:06 pm Question about exponention WingDragon@gmail.com Math 2 Fri Jul 21, 2006 8:13 am question on solartron 1260 carrie_yao@hotmail.com Electrochem 0 Fri Jul 21, 2006 7:11 am