My Math Forum bins and balls - uniform random selection problem

 August 15th, 2007, 04:49 AM #1 Newbie   Joined: Aug 2007 Posts: 3 Thanks: 0 bins and balls - uniform random selection problem I have N bins and n balls, N >> n (eg. if N = 100, n = 5). For every bin N_i (i = 0..N-1) I choose uniformly and randomly q balls n_i (i = 0..n-1), q < n (eg. q = 3). I "copy" the chosen balls into the bin, and move to the next bin, where I again randomly select q balls from the initial set of balls and copy them into the bin, etc. for all bins. In the end each bin contains exactly q balls, copied randomly from the initial set of n balls. How can I calculate statistically in how many bins N_i (i = 0..N-1), each ball n_i (i =0..n-1) was copied? Thanks!
 August 15th, 2007, 04:45 PM #2 Global Moderator   Joined: May 2007 Posts: 6,807 Thanks: 717 It looks to me like a binomial distribution. Prob (P) a given ball is in a given bin is q/n. Prob (Q) is not is 1-P. Expand (P+Q)^N. First term (P^N) is prob. a ball is in all bins, last term (Q^N) is prob. ball in no bins. Mean no. bins is NP.
August 16th, 2007, 12:35 AM   #3
Newbie

Joined: Aug 2007

Posts: 3
Thanks: 0

Quote:
 Mean no. bins is NP.
Does that mean that the answer that I am looking for is N*P = N*q/n. So eg. for N=100 bins, and q=3 balls, and n=5 balls, N*P=100*3/5=60 balls ie on the average 60 balls will be selected for each bin. Is that correct?

Quote:
 Expand (P+Q)^N
Do you mean that for P=q/n and Q=1-q/n I should do (q/n+(1-q/n))^N = 1. Something is not right. Is it because P and Q are events, so I shouldn't substitute them in the equation but rather their probabilities? Eg. should it be rather (prob(P) + prob(Q))^N?

Thanks!

August 16th, 2007, 01:40 PM   #4
Global Moderator

Joined: May 2007

Posts: 6,807
Thanks: 717

Quote:
Originally Posted by cerdan

Quote:
 Mean no. bins is NP.
Does that mean that the answer that I am looking for is N*P = N*q/n. So eg. for N=100 bins, and q=3 balls, and n=5 balls, N*P=100*3/5=60 balls ie on the average 60 balls will be selected for each bin. Is that correct?
Each of the 5 balls will be in an average of 60 bins.

Quote:
 Expand (P+Q)^N
Quote:
 Do you mean that for P=q/n and Q=1-q/n I should do (q/n+(1-q/n))^N = 1. Something is not right. Is it because P and Q are events, so I shouldn't substitute them in the equation but rather their probabilities? Eg. should it be rather (prob(P) + prob(Q))^N? Thanks!
P is the probability that a specific ball will be chosen for a specific bin.

 August 17th, 2007, 07:24 AM #5 Newbie   Joined: Aug 2007 Posts: 3 Thanks: 0 Thanks I got it! Thanks!

 Tags balls, bins, problem, random, selection, uniform

balls into bins problem

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post ozerdem Algebra 4 February 20th, 2012 11:17 PM mia6 Advanced Statistics 1 February 23rd, 2011 01:11 PM Advanced Statistics 0 February 3rd, 2011 06:24 PM begyu85 Algebra 1 March 28th, 2008 04:31 PM Mathematics19 Advanced Statistics 1 April 30th, 2007 05:06 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top