estimated collision for given binary length of an ID

gistfile1.py

# collision.py

# needed for python 2.x
from __future__ import division

# permutation
def perm(x, n):
   "x balls in n buckets"
   def mult_l(acc, head):
      return acc * head
   # empty buckets
   eb = range(n, n-x, -1)
   return reduce(mult_l, eb, 1)

# no collision
def no_c(x, n):
   numerator = perm(x, n)
   denominator = n ** x
   return numerator / denominator

# expected collision
def exp_c(n):
   def add_l(acc, head):
      return acc + head
   # weighted probability
   def w_prob(i):
      return i * no_c(i-1, n) * (1/(i-1))
   poss_nums = range(2, n+2)
   #print poss_nums
   weights = map(w_prob, poss_nums)
   #print weights
   return reduce(add_l, weights, 0.0)

# estimated expected collision
def est_exp_c(n, skip=2):
   def add_l(acc, head):
      return acc + head
   # weighted probability
   def w_prob(i):
      return i * no_c(i-1, n) * (1/(i-1)) * skip
   poss_nums = range(2, n+2, skip)
   weights = map(w_prob, poss_nums)
   return reduce(add_l, weights, 0.0)

if __name__ == "__main__":
   print "expected 20:", exp_c(20)
   print "expected 365:", exp_c(365)
   print "estimated expected 365", est_exp_c(365, 4)
   print "estimated expected 64^2", est_exp_c((2**6)**2, 4)