Appendix E: Probability Theory - Codes: The Guide to Secrecy from Ancient to Modern Times - page 546

In order to state the next result, we need a notion related to variance.

Covariance

If X and Y are random variables, the covariance is defined by

covar( X,Y )= E [( X − E ( X )) · ( Y − E ( Y ))] .

The Variance Theorem

If X and Y are random variables, and a,b ∈ R , then

var( aX + bY )= a 2 var( X )+ b 2 · · var( Y )+2 ab · covar( X,Y ) ,

and if X and Y are independent, then

var( X + Y )=var( X )+var( Y ) .

E.3 Binomial Distribution

An important notion that links the binomial coeGcient with the notion of
expectation and variance is the following.

The Binomial Distribution Theorem

If s , p s = p , and B n ( s ) is the number of occurrences of s in n independent

trials, then

∈ S

1. B n ( s ) ∈{ 0 , 1 ,...,n } , and for any nonnegative integer k ≤ n , the proba-

bility that B n ( s )= k is given by
n
k

p k (1

p ) n − k , −

2. E ( B n ( s )) = n · p ,

E

3. ( B n ( s ) /n )= p, where

F n ( s )= B n ( s )
n
is a random variable, called the n th relative frequency of s .

3. var( B n ( s )) = n · p · (1 − p ),

4. var( F n ( s )) = p · (1 − p ) /n .