iconEuler Examples

Selecting m out of n

by R. Grothmann

Compute the probability to get a choice with different objects,
if m of out of n are chosen randomly.
>function 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.
>f(5,10)
             0.3024 
It is an almost safe bet, that there are at least two out of 60
persons with same birthday.
>f(60,365)
  0.005877339134652 
The bet on this event becomes good with more than 23 people.
>m=1:100; plot2d(m,fmap(m,365)); insimg;

Selecting m out of n

Let us investigate Lotto in a small town like Eichstätt (10000
Lotto players). Chances are 1:36 against all Lotto sheets being
different.
>n=bin(49,6)
           13983816 
>1/f(10000,n)
     35.73236466445 
For large n and m, it is better to use an approximation using
Sterling's formula.
>function fa(m,n) := sqrt(n/(n-m))*(n/(n-m))^(n-m)*exp(-m)
>fa(60,365)
  0.005877603112455 
>f(60,365)
  0.005877339134652 
When does the probability pass 0.5 in our biirthday problem?
>bisect("fa(x,365)-0.5",20,30)
     22.76793161096 
In Euler, the bisection method works for discrete functions.
>bisect("f(x,365)-0.5",20,30)
     23.00000000001 
Indeed, the switch is between 22 and 23.
>fmap(21:30,365)
Column 1 to 3:
    0.5563116648348     0.5243046923374      0.492702765676 
Column 4 to 6:
    0.4616557420855     0.4313002960305     0.4017591798641 
Column 7 to 9:
    0.3731407177368     0.3455385276576     0.3190314625222 
Column 10:
    0.2936837572807 
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. It is very likely to find three or more
with same birthday.
>res=simulate(200,365); plot2d(res,bar=1); insimg;

Selecting m out of n

The simulated result is close to the theoretical result.
>res=simulate(40,365); res[1], f(40,365),
             0.1099 
    0.1087681901821 
When selecting 5 out of 10, finding 2 equal numbers has the largest
chance.
>res=simulate(5,10); plot2d(res,bar=1); insimg;

Selecting m out of n

The simulation result is close to the theoretical result.
>res[1], f(5,10),
            0.30068 
             0.3024 
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)
      24.6165858946 
Here is a distribution of the waiting time.
>plot2d(fmap(i-1,n)*(i-1)/n); insimg;

Selecting m out of n

>

Examples Homepage