by R. Grothmann
Compute the probability to get a choice with different objects, if m of out of n are chosen randomly. The formula is of course
We use the prod formula of Euler for this.
>function map f(m,n) := prod((n:-1:n-m+1)/n)
The following is the chance to get 5 different numbers, if 5 are chosen from 10 numbers.
It is an almost safe bet, that there are at least two out of 60 persons with same birthday.
The bet on this event becomes favorable with more than 23 people.
Let us investigate Lotto in a small town like Eichstätt, Germany (assuming 10000 Lotto players). Chances are 1:36 against all Lotto sheets being different.
For large n and m, it is better to use an approximation using Sterling's formula.
>function map fa(m,n) := sqrt(n/(n-m))*(n/(n-m))^(n-m)*exp(-m) >fa(60,365)
When does the probability pass 0.5 in our birthday problem?
In Euler, the bisection method works for discrete functions.
Indeed, the switch is between 22 and 23.
[0.556312, 0.524305, 0.492703, 0.461656, 0.4313, 0.401759, 0.373141, 0.345539, 0.319031, 0.293684]
We simulate the choice with a Monte Carlo simulation. The following function returns the percentage of j equal entries when choosing m out of n.
>function simulate (m,n,k=100000) ... res=zeros(1,m); loop 1 to k h=floor(random(1,m)*n); j=max(count(h[1:m],n)); res[j]=res[j]+1; end; j=max(nonzeros(res<>0)); return res[1:j]/k; endfunction
We select 200 people 100000 times. It is very likely to find three or more with same birthday.
The simulated result is close to the theoretical result.
>res=simulate(40,365); res, f(40,365),
When selecting 5 out of 10, finding 2 equal numbers has the largest chance.
The simulation result is close to the theoretical result.
What is the average waiting time until two persons with same birthday are found? We observe that the chance to find the first same birthday at the i-th person is f(i-1,n)*(i-1)/n, since the first i-1 must be different from each other and the next one must be one of the first i-1.
>n=365; i=2:n; sum(fmap(i-1,n)*(i-1)/n*i)
Here is a distribution of the waiting time.