(32S, 32SII) Birthday paradox, hash collision probability
04-27-2020, 07:54 PM (This post was last modified: 05-01-2020 07:29 PM by Albert Chan.)
Post: #4
 Albert Chan Senior Member Posts: 1,676 Joined: Jul 2018
RE: (32S, 32SII) Birthday paradox, hash collision probability
(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
 « Next Oldest | Next Newest »