Institut for Matematik og Datalogi Odense Universitet March 19, 1996

JFB

DM11 – F96 – Lecture 7

Lecture, March 13

We finished sections 4.1 through 4.3 of chapter 4.

Lecture, March 20

We will cover sections 4.4 and 4.5 of chapter 4, plus some more on probability.

Lecture, March 27

We will cover sections 4.6, 4.7, 5.4 and 5.5.

Problems to be discussed in week 13

• 28, 30, 32, 40, 46, and 48 from section 4.3.

• 4, 22, 30 and 34 from section 4.4.

• 9, 10, 11, 14, 32, 33, and 36 from section 4.5.

• An array A[1..n] contains n distinct numbers, randomly ordered so that each permutation of the n numbers is equally likely. What is the expectation of the index of the maximum element in the array?

• Let X be a nonnegative random variable. Prove Markov’s inequality: p(X ≥ t) ≤ E[X]/t.

• Show that for any random variable X that takes on only the values 0 and 1, we have Var[X] = E[X]E[1 − X].

• How many times on average must we flip 6 fair coins before we obtain 4 “heads” and 2 “tails”.

• Show that the probability of zero successes in n Bernoulli trials, each with probability p = 1/n of success is approximately 1/e. Show that the probability of one success is also approximately 1/e.

Notes on probability

The textbook has too little on probability, so this is a supplement to what it has.

Note that in section 4.5, there is no need for the restriction to finite sample spaces, even though we are restricting ourselves to discrete probability spaces. For example, consider the experiment in which a fair coin is flipped until the first time “heads” is the result. Then, the sample space is

S = {H, T H, T T H, T T T H, T T T T H, ..., T^{n}H, ...}.

This is not finite, but we can assign probabilities to each event. The probability of T^{n}H is (1/2)^{n+1} for n ≥ 0. If the coin is biased so that the probability of “heads” is p and the probability of “tails” is q = 1 − p, then the probability of T^{n}H is q^{n}p. In this case we have independent Bernoulli trials which are repeated until the first success.

If the sample space is {x_{i} | i ≥ 1}, the probabilities must satisfy:

• 0 ≤ p(x_{i}) ≤ 1 ∀i ≥ 1

• ∑_{i=1}^{∞} p(x_{i}) = 1.

• For any events A_{1}, A_{2}, ... that are pairwise mutually exclusive

(i.e. A_{i} ∩ A_{j} = ∅ for i ≠ j), p(⋃_{i} A_{i}) = ∑_{i} p(A_{i}).

Note that the last is not included in the textbook, but really should be. These probability axioms can be written more generally, so they also apply to any finite sample space S.

• 0 ≤ p(x_{i}) ≤ 1 ∀x_{i} ∈ S

• ∑_{x_{i}∈S} p(x_{i}) = 1.

• For any events A_{1}, A_{2}, ... that are pairwise mutually exclusive

(i.e. A_{i} ∩ A_{j} = ∅ for i ≠ j), p(⋃_{i} A_{i}) = ∑_{i} p(A_{i}).

When the probabilities satisfy these axioms, the mapping which is defined by p is a probability distribution. We are interested in discrete probability distributions; those defined over finite or countably infinite sample spaces. For a finite sample space S, if p(x_{i}) = 1/|S| for all x_{i} ∈ S, then we have the uniform probability distribution; each outcome is equally likely. The probability distributions defined by a fair coin and by fair dice are uniform. The probabilities defined above for the number of coin tosses required before the result is a “head” is called the geometric distribution. As mentioned on page 274, the probability distribution defined by the probability of k successes in n independent Bernoulli trials is called the binomial distribution.

The more general proofs of theorems 1 and 2 from section 4.4, given on pages 270-271 in section 4.5 clearly hold with infinite sample spaces, if one simply changes n to ∞. The definitions of conditional probability, independence, and random variables are exactly the same whether one is talking about a finite or a countably infinite sample space.

The events A_{1}, A_{2}, ..., A_{n} are pairwise independent if p(A_{i} ∩A_{j}) = p(A_{i})·p(A_{j}) for i ≠ j, and they are mutually independent if, for every subset of 2 ≤ k ≤ n events A_{i_{1}}, A_{i_{2}}, ...A_{i_{k}} where 1 ≤ i_{1} < i_{2} < ... < i_{k} ≤ n, we have p(A_{i_{1}} ∩ A_{i_{2}} ∩ ... ∩ A_{i_{k}}) = p(A_{i_{1}})p(A_{i_{2}}) ⋯ p(A_{i_{k}}).

A well-known theorem concerning conditional probabilities is Thm. [Baye’s Theorem] For two events A and B such that p(A) > 0 and p(B) > 0, p(A|B) = \frac{p(A)p(B|A)}{p(B)}. Pf. By the definition of conditional probability, p(A ∩ B) = p(B)p(A|B) and p(A∩B) = p(A)p(B|A). Thus, p(B)p(A|B) = p(A)p(B|A), and the result follows by dividing both sides by p(B). □

The expected value of a random variable X(s) on the sample space {x_{i} | i ≥ 1} is E(X) = ∑_{i=1}^{∞} p(x_{i})X(x_{i}). The expected value is also called the mean. Consider the sample space S defined above, with the probability of “heads” being p and the probability of “tails” being q = 1 − p. The expected value of the number of times the coin must be flipped to get the result is “heads” once is ∑_{i=1}^{∞} iq^{i−1}p = ∑_{i=1}^{∞} iq^{i−1}−∑_{i=1}^{∞} iq^{i} = ∑_{j=0}^{∞}(j+1)q^{j}−∑_{i=1}^{∞} iq^{i} by changing the index of summation so j = i−1. Pulling out the term with i = 0 and combining, we get ∑_{i=1}^{∞} iq^{i−1}p = 1+ ∑_{j=1}^{∞}(j +1−j)q^{j} = 1+ ∑_{j=1}^{∞} q^{j} = 1+(∑_{j=0}^{∞} q^{j})−1 = lim_{j→∞} \frac{q^{j+1}−1}{q−1} since this is a geometric progression as in example 6 on page 190 of the textbook. Since q < 1, lim_{j→∞} q^{j+1} is clearly zero, so ∑_{i=1}^{∞} iq^{i−1}p = \frac{−1}{q−1} = \frac{1}{p}. Thus, with a fair coin, the expected number of tosses before the result is “heads” is 2, and with a fair die, the expected number of throws before a 4 is 6.

This result is particularly useful in the analysis of randomized algorithms. Such algorithms often involve making random choices for some object until one is found satisfying a certain property P. If 1/c of the objects satisfy that property P, we expect to have c trials before success. Often this expected running time is much faster in practice than one can get with any known deterministic algorithm for finding an object with the given property P.

The expectation of random variables has an important property, known as the linearity of expectation. A linear funtion of n random variables, X_{1}, X_{2}, ..., X_{n} has the form f(X_{1}, X_{2}, ..., X_{n}) = a_{0} + a_{1}X_{1} + a_{2}X_{2} + ... + a_{n}X_{n} where a_{i} ∈ IR for 0 ≤ i ≤ n. The expected value of a linear function of random variables has the same value as that function applied to the expectations of the random variables. Thus, E[f(X_{1}, X_{2}, ..., X_{n})] = f(E[X_{1}], E[X_{2}], ..., E[X_{n}]). This does not depend on whether or not the random variables are independent, so in a randomized algorithm which finds two objects with some property, the expected time for this is the sum of the expected times for finding each one. The linearity of expectation can be proven directly from the definition of expected values.

Thm. Let f be a linear function, S be a sample space, and X_{1}, X_{2}, ..., X_{n} be random variables defined on S. Then, E[f(X_{1}, X_{2}, ..., X_{n})] = f(E[X_{1}], E[X_{2}], ..., E[X_{n}]). Pf. Let f(X_{1}, X_{2}, ..., X_{n}) = a_{0} + a_{1}X_{1} + a_{2}X_{2} + ... + a_{n}X_{n} where a_{i} ∈ IR for 0 ≤ i ≤ n. Then,

E[f(X_{1}, X_{2}, ..., X_{n})] = ∑_{s∈S} p(s)f(X_{1}(s), X_{2}(s), ..., X_{n}(s))
= ∑_{s∈S} p(s)(a_{0} + a_{1}X_{1}(s) + a_{2}X_{2}(s) + ... + a_{n}X_{n}(s))
= ∑_{s∈S}(p(s)a_{0} + ∑_{i=1}^{n} p(s)a_{i}X_{i}(s))
= a_{0} + ∑_{i=1}^{n}(∑_{s∈S} p(s)a_{i}X_{i}(s))
= a_{0} + ∑_{i=1}^{n}(a_{i} ∑_{s∈S} p(s)X_{i}(s))
= f(E[X_{1}], E[X_{2}], ..., E[X_{n}]). □

The expectation of products of random variables does not work quite as nicely as sums of random variables. But, if two random variables X and Y are independent, then E[XY] = E[X] · E[Y].

The variance of a random variable is Var[X] = E[(X − E[X])^{2}]. Expanding this, we get Var[X] = E[X^{2} −2XE[X]+E^{2}[X]]. By the linearity of expectations, this is E[X^{2}] − 2E[XE[X]] + E[E^{2}[X]]. Since E[X] is a real number, rather than a random variable, this is E[X^{2}] − 2E^{2}[X] + E^{2}[X]. Thus Var[X] is also E[X^{2}] − E^{2}[X]. The variance is meant to tell how far from the mean one expects the value to be. If X and Y are independent random variables, then Var[X + Y] = Var[X] +Var[Y]. More generally, if X_{1}, X_{2}, ..., X_{n} are pairwise independent random variables, then Var[∑_{i=1}^{n} X_{i}] = ∑_{i=1}^{n} Var[X_{i}]. The standard deviation of a random variable is the positive square root of the variance.

The variance of a geometric distribution can be shown to q/p (recall that the expectation is 1/p).

The expected value of the binomial distribution is shown on page 278 to be np. Let X_{i} be the random variable which says how many successes there were in the ith trial. This value must be either 0 or 1, so E[X_{i}^{2}] = E[X_{i}] = p. To compute the variance of the binomial distribution, we have Var[X] = Var[∑_{i=1}^{n} X_{i}] = ∑_{i=1}^{n} Var[X_{i}] since the X_{i} are pairwise independent. But Var[X_{i}] = E[X_{i}^{2}] − E^{2}[X_{i}] = p − p^{2} = pq . Thus for the binomial distribution, Var[X] = ∑_{i=1}^{n} pq = npq.