[freehaven-cvs] commit the script i used to calc actual entropy vs a...

[arma@seul.org (Roger Dingledine)]

Update of /home/freehaven/cvsroot/doc/sync-batching
In directory moria.mit.edu:/home2/arma/work/freehaven/doc/sync-batching

Added Files:
	calc.py 
Log Message:
commit the script i used to calc actual entropy vs average entropy


--- NEW FILE: calc.py ---
#!/usr/bin/python2

u = 4 # the number of nodes (buckets)
invu = 1./u

m=128 # the number of messages (balls)
p=16  # find the chance that some node gets less than p messages

#n=64
#p=16

def fact(n):
    if n == 0:
        return 1
    result = n
    while n > 1:
        n -= 1
        result *= n
    return result

def choose(n, *vars):
    den = 1
    tot = n
    for i in vars:
      den *= fact(i)
      tot -= i
    den *= fact(tot)
    return fact(n) / den

PA = 0
for i in range(p): # 0..p-1 inclusive
    PA += (invu ** i) *        \
          ((1.-invu) ** (m - i)) *  \
           choose(m, i)

PB = 0
for i in range(p):
    for j in range(p):
        PB += (invu ** i) *       \
              (invu ** j) *       \
              ((1.-2.*invu)  ** (m-i-j)) * \
               choose(m, i, j)

PC = 0
for i in range(p):
    for j in range(p):
        for k in range(p):
            PC += (invu ** i) *          \
                  (invu ** j) *          \
                  (invu ** k) *          \
                  ((1.-3.*invu) ** (m-i-j-k)) *  \
                   choose(m, i, j, k)

print choose(u,1) * PA
print -choose(u,2) * PB
print choose(u,3) * PC
print choose(u,1) * PA - choose(u,2) * PB + choose(u,3) * PC


***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs       in the body. http://freehaven.net/