ผลต่างระหว่างรุ่นของ "Probstat/notes/balls and bins"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 3: แถว 3:
 
We consider a balls-and-bins experiment where we throw ''n'' balls independently into ''n'' bins uniformly at random.
 
We consider a balls-and-bins experiment where we throw ''n'' balls independently into ''n'' bins uniformly at random.
  
'''Question 1:''' ''How many possible outcomes are there?''
+
{{กล่องฟ้า|'''Question 1:''' ''How many possible outcomes are there?''
  
 
Since each ball has ''n'' choices and their choices are independent, there are <math>n^n</math> outcomes.
 
Since each ball has ''n'' choices and their choices are independent, there are <math>n^n</math> outcomes.
 +
}}
  
'''Question 2:''' ''What is the probability that bin 1 is empty?''
+
{{กล่องฟ้า|'''Question 2:''' ''What is the probability that bin 1 is empty?''
  
 
In this case, each ball only have ''n'' - 1 choices (because they have to avoid bin 1); therefore there are <math>(n - 1)^n</math> outcomes where bin 1 is empty.  Since each outcome is equally likely, the probability that bin 1 is empty is <math>\frac{(n-1)^n}{n^n} = \left(\frac{n-1}{n}\right)^n = \left(1-\frac{1}{n}\right)^n</math>.
 
In this case, each ball only have ''n'' - 1 choices (because they have to avoid bin 1); therefore there are <math>(n - 1)^n</math> outcomes where bin 1 is empty.  Since each outcome is equally likely, the probability that bin 1 is empty is <math>\frac{(n-1)^n}{n^n} = \left(\frac{n-1}{n}\right)^n = \left(1-\frac{1}{n}\right)^n</math>.
 +
}}
  
 
== Number of empty bins ==
 
== Number of empty bins ==
 
Let random variable ''X'' be the number of empty bins.
 
Let random variable ''X'' be the number of empty bins.
  
'''Question 1:''' ''What is P{X = 0}?''
+
{{กล่องฟ้า|'''Question 1:''' ''What is P{X <math>=</math> 0}?''
  
 
If there is no empty bin, every ball must land into different bin.  In this case, the first ball has n choices, the second ball has n-1 choices, and in general the ''i''-th ball has ''n - i +1'' choices.  Therefore, there are <math>n\cdot (n-1)\cdot(n-2)\cdots(2)(1) = n!</math> outcomes.  The probability is <math>\frac{n!}{n^n}</math>.
 
If there is no empty bin, every ball must land into different bin.  In this case, the first ball has n choices, the second ball has n-1 choices, and in general the ''i''-th ball has ''n - i +1'' choices.  Therefore, there are <math>n\cdot (n-1)\cdot(n-2)\cdots(2)(1) = n!</math> outcomes.  The probability is <math>\frac{n!}{n^n}</math>.
 +
}}
  
 
It will be very hard to compute E[''X''] directly.  (Just computing ''P''{ ''X'' = 3 } seems to be exceedingly hard.)
 
It will be very hard to compute E[''X''] directly.  (Just computing ''P''{ ''X'' = 3 } seems to be exceedingly hard.)
  
 
== Fullest bins ==
 
== Fullest bins ==

รุ่นแก้ไขเมื่อ 03:52, 18 กันยายน 2557

This is part of probstat. The materials on this part is from this course at Berkeley.

We consider a balls-and-bins experiment where we throw n balls independently into n bins uniformly at random.

Question 1: How many possible outcomes are there?

Since each ball has n choices and their choices are independent, there are outcomes.

Question 2: What is the probability that bin 1 is empty?

In this case, each ball only have n - 1 choices (because they have to avoid bin 1); therefore there are outcomes where bin 1 is empty. Since each outcome is equally likely, the probability that bin 1 is empty is .

Number of empty bins

Let random variable X be the number of empty bins.

Question 1: What is P{X 0}?

If there is no empty bin, every ball must land into different bin. In this case, the first ball has n choices, the second ball has n-1 choices, and in general the i-th ball has n - i +1 choices. Therefore, there are outcomes. The probability is .

It will be very hard to compute E[X] directly. (Just computing P{ X = 3 } seems to be exceedingly hard.)

Fullest bins