Discrete Mathematics for Computer Science

Exercises 539

does not depend on n. Suppose we choose some small positive value for C. No matter what
we choose, we can make the bound

U^2

n , E2

in Theorem 5 as small as we like by making n sufficiently large. Hence, according to the
theorem, the probability is small that Y = (XI + X 2 + -- + Xn)/n will differ by E or
more from its expected value E(Y) = g provided that we run a large enough number n of
trials. Therefore, in this special case, the expected value of the random variable Y does tell
us what to expect the value of the variable to be. Repeating an experiment a large number
of times increases the accuracy of estimating the average. We highlight this important
interpretation below.

Interpretation of the Law of Averages

If we interpret probability as an estimate for frequency of occurrence, then the Law

of Averages says that only rarely will

Y=xx+..xY X1 + X2 + "..+ X,

n

differ greatly from the expected value of Y, so the actual values of Y do cluster around

the expected value of Y (provided that n is large).

Exercises

1. Compute the variance Var(X) of the random variable X that counts the number of
   heads in four flips of a fair coin.


2. Compute the variance Var(X) of the random variable X that counts the number of
   heads in four flips of a coin that lands heads with a frequency of 1/3.


3. Define a random variable X on the sample space QŽ by setting X (w) = 3 for all w0 E 2.
   What is E(X)? Var(X)?


4. Suppose we flip a fair coin 100 times. Define a random variable X on the underlying
   sample space 02 that counts the number of heads that turn up.
   (a) What are the mean it and the variance o-^2 of X?
   (b) Use Theorem 2 to give an upper bound for the probability that X differs from [t
   by 10 or more.


5. Suppose we flip a fair coin n times. Let Q2 consist of n-tuples to of H's and T's. Let
   Xi (w) = 1 if the ith component of o is an H; otherwise, let Xi (O) = 0.
   (a) Do the Xi form an i.i.d. set of random variables?
   (b) Let Y = (Xl + -• -+ Xn)/n. What is the mean and the variance of Y?
   (c) Suppose n = 100. Use Theorem 5 to give an upper bound for the probability that
   Y differs from its mean by 0.1 or more.