FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math
Combinatorial Probability Question
Post new topic   Reply to topic Page 1 of 1 [4 Posts] View previous topic :: View next topic
Author Message
David B. Chorlian
science forum beginner


Joined: 31 Mar 2006
Posts: 2

PostPosted: Wed Jun 07, 2006 3:38 pm    Post subject: Combinatorial Probability Question Reply with 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?

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

PostPosted: Wed Jun 07, 2006 4:10 pm    Post subject: Re: Combinatorial Probability Question Reply with quote

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
Back to top
Stan Liou
science forum addict


Joined: 27 Mar 2005
Posts: 54

PostPosted: Thu Jun 08, 2006 2:07 am    Post subject: Re: Combinatorial Probability Question Reply with quote

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
Back to top
Patrick Coilland
science forum Guru Wannabe


Joined: 29 Jan 2006
Posts: 197

PostPosted: Thu Jun 08, 2006 5:44 am    Post subject: Re: Combinatorial Probability Question Reply with quote

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
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [4 Posts] View previous topic :: View next topic
The time now is Thu Sep 20, 2018 2:53 am | All times are GMT
Forum index » Science and Technology » Math
Jump to:  

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

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0160s ][ Queries: 16 (0.0044s) ][ GZIP on - Debug on ]