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

[Albert Chan]

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