(32S, 32SII) Birthday paradox, hash collision probability
05-02-2020, 11:15 PM (This post was last modified: 05-05-2020 12:55 AM by Albert Chan.)
Post: #8
 Albert Chan Senior Member Posts: 1,676 Joined: Jul 2018
RE: (32S, 32SII) Birthday paradox, hash collision probability
Assume x ≫ a, and let $$m = (x+{1+a\over2})$$, prove $$\large {(x+a)!\over x!} ≈ m^a$$

$$\large {(x+a)!\over x!} = {m!\,/\,x! \over m!\,/\,(x+a)!} = {perm(m, {1+a\over2}) \over perm(m, {1-a\over2})}$$

A few lines in XCas proved this ...

XCas> P_nr(n,s) := exp(-s*(s-1)/(2n)) ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ // probability of no repetition, assumed n ≫ s
XCas> my_perm(n,s) := P_nr(n,s) * n^s ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ // avoid name conflict with XCas perm()
XCas> m := x+(1+a)/2
XCas> simplify(my_perm(m,(1+a)/2) / my_perm(m,(1-a)/2) - m^a)
→ 0

XCas> subst((x+a)! / x!, [x,a]=[69,0.95])
→ 56.5843203835
XCas> subst(m^a, [x,a]=[69,0.95])
→ 56.5842757853
XCas> subst(m^a, [x,a]=[70,-0.05]) * 70 ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿// 69.95!/69! = 69.95!/70! * 70
→ 56.5843440581

Update: this ratio formula is better

XCas> ratio(x,a) := (x*x + (a+1)*(x + (a+2)/6)) ^ (a/2)
XCas> ratio(69.,0.95)
→ 56.5843203845
XCas> ratio(70., -.05) * 70 ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿ ﻿﻿ ﻿// 69.95!/69! = 69.95!/70! * 70
→ 56.5843203829
 « Next Oldest | Next Newest »