ผลต่างระหว่างรุ่นของ "Probstat/notes/balls and bins"
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 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.)
