(32S, 32SII) Birthday paradox, hash collision probability
04-28-2020, 03:23 PM (This post was last modified: 05-04-2020 12:29 AM by Albert Chan.)
Post: #7
 Albert Chan Senior Member Posts: 1,676 Joined: Jul 2018
RE: (32S, 32SII) Birthday paradox, hash collision probability
(04-27-2020 07:54 PM)Albert Chan Wrote:  ln_P(n,s) := -s/(12*n*(n-s)) - (s + (n-s+0.5)*ln(1-s/n))
(04-27-2020 10:43 PM)Albert Chan Wrote:  ln(P(n,s)) ≈ -s/(12*n*(n-s)) + 2*(n-s+0.5)(y^3/3 + y^5/5 + ...) - (s-1)y

This version use the 2nd form, to avoid numerical cancellation problem of original formula.
It assumed IEEE double, ln(2^-52) ≈ -36.0, and sum y^n terms in reverse order

With all this work, we might as well add more corrections.

XCas> series(1/(e^D-1),D)
→ 1/D -1/2 +D/12 -D^3/720 +D^5/30240 +D^6*order_size(D)

Let u=n-x, f(x) = ln(n-x) = ln(u) → df = ln(n-x) dx = -ln(u) du
With x limit from 0 to s, we have u = n-x = from n to n-s

XCas> diff(-ln(u),u,3) / -720 ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿→ 1/(u^3*360)
XCas> diff(-ln(u),u,5) / 30240 ﻿ ﻿ ﻿ ﻿﻿→ -1/(u^5*1260)

Code:
function ln_nr(n,s)         -- log(probability of no repetition)     local c = n-s     local y = s/(c+n)     local y2 = y*y     local k = floor(-36/log(y2))*2 + 3     local t = 1/k     for k = k-2,3,-2 do t = y2*t + 1/k end     y2 = (c+c+1)*t*y2*y     -- = (s-1)*y - (s+(n-s+0.5)*ln(1-s/n))     k = 1/(c*n)     t = s*k                 -- =  1/(n-s)   - 1/n     c = t*t + 3*k           -- = (1/(n-s)^3 - 1/n^3) / t     k = c*(c-k) - k*k       -- = (1/(n-s)^5 - 1/n^5) / t     return (k - 3.5*c + 105)*t*(-1/1260) + y2 - (s-1)*y end

lua> m = require'mathx'
lua> function fac(n) return m.tgamma(n+1) end
lua> fac(69.95)/fac(69)
56.58432038352886

lua> function perm(n,s) return exp(ln_nr(n,s)) * n^s end
lua> perm(69.95, 0.95)
56.58432038352816
lua> 70*perm(69.95,-0.05) -- 69.95!/69! = 70*(69.95!/70!)
56.58432038352817
lua> 70/perm(70,0.05) ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿-- 69.95!/69! = 70/(70!/69.95!)
56.58432038352817

lua> ((69.95+70)/2)^0.95﻿ ﻿ -- inspired from Approximating Gamma Ratios
56.58427578530249
 « Next Oldest | Next Newest »