Binomial and Poisson Statistics Functions in JavaScript

Numerical Computations for Cryptography

Computations of combinatoric and statistics functions and inverses which deliver good accuracy over a wide range of values. Accuracy tests allow the functions to be checked in any computing environment.

A Ciphers By Ritter Page


Terry Ritter

Last Update: 1998 June 24


Please send comments and suggestions for improvement to: ritter@ciphersbyritter.com. You may wish to help support this work by patronizing Ritter's Crypto Bookshop.


Contents

Related Pages


Binomial

The binomial distribution represents the probability that a particular type of event will occur a given number of times. When each "success" has probability p, and there are n trials, we can compute the probability of getting exactly k successes. We can also compute the cumulative probability of getting k or fewer successes; this is the cumulative distribution function or c.d.f.

For the binomial to be an appropriate model, it must describe Bernoulli trials. This is sampling with replacement in which:

Since it is common in cryptography to create random-like events, these conditions are often met, although the values involved may be far larger than could be easily handled with a normal calculator.

The binomial distribution gives the probability of finding exactly k successes (or at least k successes in the c.d.f.) over n trials given probability p of success on each trial:

               n    k      n-k
   B(k,n,p) = ( )  p  (1-p)
               k

p n k

Exactly k

cdf = P(0..k) Q = 1-P


Bit Changes

The binomial is the appropriate distribution for bit-changes from an invertible substitution table or cipher. This is the source of bit diffusion within a substitution table, and is related to avalanche.

Suppose we have some input value to a substitution table or cipher. Now suppose we change that input value. This will select a different value from the table. We can expect about half of the output bits to change on average, but we could get as few as one, or as many as all of them. The distribution is binomial.

table width, bits samples


Poisson

The Poisson distribution is a simplified model for the binomial distribution under certain conditions:

The Poisson distribution gives the probability of finding exactly k successes (or at least k successes in the c.d.f.) given success expectation u:

             k  -u
   P(k,u) = u  e    /  k!
where e is the base of natural logarithms:
   e = 2.71828...
and u is:
   u = n p

u k

Exactly k

cdf = P(0..k) Q = 1-P


Terry Ritter, his current address, and his top page.