birthday paradox approximation formula

[Michele Politta]

Hi,

The birthday paradox formula (or collision) that give the probability
that 0 people in the same room have the birthday in the same day is:

P = T!/(n!*T^n) 1)

where T=365 (n. of possible cases) and n=(n. of people set).

If I would use bigger value of T & n (for other uses) I need an approx
of that.

I found a good one that stat:

p = e^(-n*(n-1)/(2*T)) 2)

I tried to derive it from the 1) but I failed. I used Stirling (and
similar other) formula for factorial approx. but it doesn't help :-(

Could some one help me in obtaining 2) from 1) ?

Thanks a lot ;-)

Michele

[Scott Hemphill]

Michele Politta <m_po...@bluewin.ch> writes:

> The birthday paradox formula (or collision) that give the probability
> that 0 people in the same room have the birthday in the same day is:

I assume you mean that no more than one person has a birthday on any
day :-).

> P = T!/(n!*T^n) 1)
>
> where T=365 (n. of possible cases) and n=(n. of people set).

This formula isn't correct. What happens if n = 1?

> If I would use bigger value of T & n (for other uses) I need an approx
> of that.
>
> I found a good one that stat:
>
> p = e^(-n*(n-1)/(2*T)) 2)
>
> I tried to derive it from the 1) but I failed. I used Stirling (and
> similar other) formula for factorial approx. but it doesn't help :-(

That formula is good for T>>n. Don't use Stirling's formuala, though.
Instead, write the corrected version of 1) as a product of factors.
The value of P for n=1 is 1. The value of P for n=2 is 1 times a
factor that is close to 1. The value of P for n=3 is P(n=2) times
another factor that is close to 1, etc.

Then you can write the logarithm of this product as the sum of the
logarithms of the factors. Do you know an approximation for the
logarithm of numbers that are close to 1? If so, then after making
the approximation for each of the original factors, you can simplify
the sum of the logarithms. Finally, now that you know an approximation
to the logarithm of P, you can exponentiate it to get an approximation
for P.

Scott
--
Scott Hemphill hemp...@alumni.caltech.edu
"This isn't flying. This is falling, with style." -- Buzz Lightyear

[David McAnally]

Michele Politta <m_po...@bluewin.ch> writes:

>Hi,

>The birthday paradox formula (or collision) that give the probability
>that 0 people in the same room have the birthday in the same day is:

>P = T!/(n!*T^n) 1)

>where T=365 (n. of possible cases) and n=(n. of people set).

The actual formula is T!/((T-n)!*T^n).

David McAnally

--------------