t***r
发帖数: 3 | 1 Suppose m balls are put into n boxes (m>=n) such that each
ball is put with equal probaility (i.e. 1/n) independently
of one another into one of the boxes.
What is the probability that each box contains at least one
ball, i.e the probability of no empty boxes? If there is no
single-term expression, what is the best way to compute the
probability in terms of numerical accuracy? (For example,
use of inclusion-exclusion formula is highly undersirable in
this respect, since it contains substractions | d*z
发帖数: 150 | 2
1.The probability that the first boxes without balls is
(1-1/n)^m,
and some is the probability that the second boxes and etc.
2.The probability that the first two boxes without balls at
the same time
is (1-2/n)^m.
.....
So the result is
1-C(n,1)(1-1/n)^m + C(n,2) (1-2/n)^m-...+(-1)^k
(1-k/n)^m+...+(-1)^(n-1) (1/n)^m
【在 t***r 的大作中提到】
: Suppose m balls are put into n boxes (m>=n) such that each
: ball is put with equal probaility (i.e. 1/n) independently
: of one another into one of the boxes.
: What is the probability that each box contains at least one
: ball, i.e the probability of no empty boxes? If there is no
: single-term expression, what is the best way to compute the
: probability in terms of numerical accuracy? (For example,
: use of inclusion-exclusion formula is highly undersirable in
: this respect, since it contains substractions
| d*z
发帖数: 150 | 3 I have thought it over and could not find a better way. Then
I test it by computer. Then I found when m is much more than
n, such as more than 2 times of n, then the accuracy of this
formula is acceptable.
#include
#include
#define N 50
double c[N+1];
int n;
void Init2()
{
c[0]=1,c[1]=2,c[2]=1;
n=2;
}
void IncreaseN()
{
int i;
c[n+1]=1;
for(i=n;i>=1;i--)
{
c[i]+=c[i-1];
}
n++;
}
void main()
{
int m;
Init2();
while(n
IncreaseN();
for(m=n;m<10*n;m++)
{
int i;
double sum;
doub
【在 t***r 的大作中提到】
: Suppose m balls are put into n boxes (m>=n) such that each
: ball is put with equal probaility (i.e. 1/n) independently
: of one another into one of the boxes.
: What is the probability that each box contains at least one
: ball, i.e the probability of no empty boxes? If there is no
: single-term expression, what is the best way to compute the
: probability in terms of numerical accuracy? (For example,
: use of inclusion-exclusion formula is highly undersirable in
: this respect, since it contains substractions
| d*z
发帖数: 150 | 4 I found a formula without subtract, but the calculation may
be time costing.
Let
U(n,1)=1 when n>=1
U(m,n)=0 when m
U(n,n)=1 when n>=1
and
U(m,n)=n U(m-1,n)+U(m-1,n-1) when m>=n>=2.
Then the probability will be
U(m,n)n!/n^m.
【在 t***r 的大作中提到】
: Suppose m balls are put into n boxes (m>=n) such that each
: ball is put with equal probaility (i.e. 1/n) independently
: of one another into one of the boxes.
: What is the probability that each box contains at least one
: ball, i.e the probability of no empty boxes? If there is no
: single-term expression, what is the best way to compute the
: probability in terms of numerical accuracy? (For example,
: use of inclusion-exclusion formula is highly undersirable in
: this respect, since it contains substractions
|
|
