Discrete Mathematics for Computer Science

Variance, Standard Deviation, and the Law of Averages 535

Properties (b) and (c) imply that i.i.d. random variables share the same expectation,

variance, and standard deviation. As the next example shows, Bernoulli trials give rise to

i.i.d. random variables.

Example 4. Consider a Bernoulli trials experiment in which a fair coin is tossed n times.

The sample space QŽ consists of 2n n-tuples o), each having probability (1/2)n. Define

random variables Xi on 02 by

Xi (9) I if the coin lands heads on the ith toss

0) otherwise

Each Xi has range {(0,} and induces px(0) = px(1) = 1/2. Is this set of random variables

independent?

Solution. Observe that the Xi's are different as functions. For example, if n = 2

and to = (heads, tails), then X 1 (09) = 1 whereas X2(0)) = 0. Now, choose X1, X2. X,

where each xi = 0 or 1, and determine the probability of the event:

(XI =x 1 ,X 2 = x 2 ..... Xn =X.)

Since there is exactly one 0o that corresponds to any particular choice,

P(X1 = Xl, X2 = X2, '',Xn Xn) = --^1

2n

On the other hand,

P(Xi = xi) = pXi(xi) = 1/2

Hence,

P(XI = X1, X 2 = X2. Xn = Xn) = H P(Xi = xi)

so the Xi are independent. U

Sets of independent random variables have certain properties not shared by all sets of

random variables. Sets of i.i.d. random variables have even more such properties. In the

following discussion, do not assume that a set of random variables is independent, or i.i.d.,

unless this is explicitly stated. For example, an independent set of random variables is not

necessarily an i.i.d. set.

Theorem 3. (Expectation of the Product of Independent Random Variables) Let

X 1 and X 2 be independent random variables defined on a sample space QŽ with probability

density p. Then, E(X 1 • X 2 ) = E(XI) • E(X 2 ).

Warning. If X 1 and X 2 are not independent, this relation does not necessarily hold.

Proof. By definition,

E(X1 -X2) SxPXI.Xx • lX2X 2 (x)

XEQX 1 .X 2

where pxl.x 2 (x) is the probability of the event

(XI " X2 = x) = {[C E Q2IXI(cv) -X 2 ((O) = x) C Q2