(32S, 32SII) Birthday paradox, hash collision probability

[Albert Chan]

(04-26-2020 07:58 PM)Dave Britten Wrote:  Very clever! And also usable on calculators that don't have a built-in ln(1+x) function:

ln(1+x) = ln(1+x)*x/(1+x-1)

Thanks. Where do you get it ?

Note: watch out for divide-by-zero, if x is tiny.
Or, use Dieter's log1p and expm1 approximation.

I tried to re-use my formula, for log(probability of no repetition)

ln_P(n,s) := -s/(12*n*(n-s)) - (s + (n-s+0.5)*ln(1-s/n))

30 people birthday "collision" ≈ -expm1(ln_P(365,30)) = 0.706316242724
Using exact formula:           1 - perm(365,30)/365^30 = 0.706316242719

For big n, small x = s/n, we can drop the first term.
Second term has a problem, even if we have accurate log1p

(s + n*ln(1 - s/n)) / n = x + log(1-x) ≈ x - x = 0

There might be a better way. For now, I use:

x + log(1-x) = x - (x + x^2/2 + x^3/3 + x^4/4 + ...) = -(x^2/2 + x^3/3 + x^4/4 + ...)

Code:

m = require 'mathx'
function ln_nr(n,s) -- log(probability of no repetition)
    local x = s/n   -- assumed small s, big n
    s = s - 0.5
    return -((((1/4)*x + 1/3)*x + 1/2)*x*(s-n) + s)*x
end

function p3(n,s) return -m.expm1(ln_nr(n,s)) end

lua> p3(365,30)
0.7063895931587847
lua> p3(2^128, 5e12)
3.6734198463188465e-014
lua> p3(2^128, 2.6153e18)
0.009999839905579181