Binomial and Poisson Statistics Functions in JavaScript (original) (raw)

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.

ACiphers 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 patronizingRitter'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

Thebinomial distributionrepresents 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 orc.d.f.

For the binomial to be an appropriate model, it must describeBernoulli trials. This issampling with replacement in which:

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

Since it is common incryptographyto createrandom-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 givenprobability p of success on each trial:

           n    k      n-k

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

Bit Changes

The binomial is the appropriate distribution forbit-changes from aninvertible substitution tableorcipher. This is the source of bitdiffusionwithin a substitution table, and is related toavalanche.

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.

Poisson

ThePoisson distributionis a simplified model for thebinomial distributionunder 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 thec.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

Terry Ritter, hiscurrent address, and histop page.