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

• Binomial -- for success probability p and n trials, the probability of k successes
• Bit Changes -- bit changes from keyed invertible substitution tables or ciphers
• Poisson -- given mean u, the probability of k successes

Related Pages

• Base Conversion
• Logs
• Powers
• Factorials
• Permutations -- n things taken k at a time, order matters
• Combinations -- n things taken k at a time, order does not matter
• Normal
• Chi Square -- compare binned distribution counts
• Kolmogorov-Smirnov -- compare distributions without using bins

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:

• Each trial is independent,
• Each outcome is random, and
• The probability of success is constant.

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 



BIT CHANGES

Poisson

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

• The number of events n is large,
• The probability of success p is small, and
• The expectation np or u is moderate.

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!

   e = 2.71828...

   u = n p

u    k 



    Exactly k 

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