Discrete Random Variables and Their Expectations

MASSACHUSETTS INSTITUTE OF TECHNOLOGY 6.436J/15.085J Lecture 5 Fall 2018 DISCRETE RANDOM VARIABLES AND THEIR EXPECTATIONS Contents 1. Combinatorial probability 2. A few useful discrete random variables 3. Joint, marginal, and conditional PMFs 4. Independence of random variables 5. Expected values 1 COMBINATORIAL PROBABILITY In this section we will briefly review some combinatorial concepts, which come in handy when performing actual computations with discrete random variables. We start with two results from analysis: 1. Exponential function as a limit, for all x ∈ R,  x n lim 1 + = ex . n!1 n 2. Stirling bounds on factorial  n n  n n 1 √ √ 2ˇn ≤ n! ≤ 2ˇn e 12n . e e Definition 1. Let Ω be a finite sample space. The discrete uniform probability space is (Ω, 2 , P), where P({!}) = 1 |Ω| 1 ∀ ! ∈ Ω. Moreover, for any event A ⊂ Ω , by finite additivity, P(A) = |A| . |Ω| Such assignments form the foundation of combinatorial probability wherein one is usually interested in counting the number of elements satisfying a particular criterion. This counting is often done following an iterative procedure. We collect some specific examples. Example 1 (Permutations). A permutation of the numbers 1, . . . , n is an isomorphism ˇ : {1, . . . , n} → {1, . . . , n}. Proceeding iteratively, there are n choices for ˇ(1), n − 1 choices for ˇ(2), · · · , and 1 choice for ˇ(n). Therefore, there are n · (n − 1) · · · 2 · 1 = n! possible permutations. Example 2 (Choices). Given a collection of n distinct objects there are n · (n − 1) · · · (n − (k − 2)) · (n − (k − 1)) = n!/(n − k)! ways to select k of those objects in a particular order. Moreover, there are n!/((n − k)!k!) ways to select k of those objects ignoring order, as k! represents all possible �
ways to arrange k objects. This last expression n!/((n − k)!k!) is denoted nk and referred to as n choose k. Example 3 (Birthday Paradox). Given n individuals, what is the probability that no two have the same birthday? Let A = “All individuals in a group of size n have unique birthdays”. Assume that an individual’s birthday is independent of all other birthdays and occurs equally likely on any calendar day (non leap year), i.e. birthdays are independent and identically distribution uniformly on {1, . . . , 365}. A is the number of ways to uniquely select n birthdays, with |A| = 365 · 364 · · · (365 − (n − 1)), and the sample space is {1, . . . , 365}n . Therefore, the resulting probability is P(A) = |A| 365! = . |Ω | 365n (365 − n)! For n = 23, P(A) = .4927, so it is more likely than two individuals will have the same birthday. Example 4 (Mafia Game). Suppose that n members of the mafia are in one room and simultaneously shoot another mafia member uniformly at random (possibly themselves). Let A = “Every member is shot”. Let Ω = {(!1 , . . . , !n )} be the set of assignments of mafia members to the people they shoot, i.e. !i ∈ 2 {1, . . . , n} is the target of the i-th mafia member. The event A occurs for all ! ∈ that are permutations. Therefore, the corresponding probability is |A| n! P(A) = = n ≤ |Ω| n √ 2ˇn � n
n e nn 1 e 12n ≤ √  2ˇne e−n . Hence, for large n, the event A is very unlikely. Example 5 (Mafia Survival). Under the setting of the Mafia Game, let B = ”The first mafia member survives”. This time each shooter has (n − 1) admissible targets for event B to occur. Therefore, the corresponding probability is   1 (n − 1)n n = 1 − −→ e−1 . Pr(B) = n nn This result can be further generalized (see Section 2.1) to show that probability of the first mafia member dying from exactly 3 bullets is     n 111 1 n−3 e−1 1− −→ . 3 nnn n 3! �
Example 6 (Multinomial Coefficients). Similar to the binomial coefficient nk , Pr given n elements and r numbers ni , i = 1, . . . , r, with i=1 ni = n, the multinomial coefficient expresses the number of ways those n elements �
can be separated into r groups of size ni . Proceeding iteratively, there are nn1 choices for �
�
1 the first group, n−n choices for the second group, · · · , and nnrr choices for n2 the r-th group. In total this provides        n n − n1 nr n! n ··· = , n1 !n2 ! · · · nr ! n1 , . . . , nr n1 n2 nr possible choices, where this last expression is the multinomial coefficient. 2 A FEW USEFUL RANDOM VARIABLES Recall that a random variable X : Ω → R is called discrete if its range (i.e., the set of values that it can take) is a countable set. The PMF of X is a function pX : R → [0, 1], defined by pX (x) = P(X = x), and completely determines the probability law of X. The following are some important PMFs. 3 (a) Discrete uniform with parameters a and b, where a and b are integers with a < b. Here, pX (k) = 1/(b − a + 1), k = a, a + 1, . . . , b, and pX (k) = 0, otherwise.1 (b) Bernoulli with parameter p, where 0 ≤ p ≤ 1. Here, pX (0) = p, pX (1) = 1 − p. (c) Binomial with parameters n and p, where n ∈ N and p ∈ [0, 1]. Here,   n k p (1 − p)n−k , k = 0, 1, . . . , n. pX (k) = k A binomial random variable with parameters n and p represents the number of heads observed in n independent tosses of a coin if the probability of heads at each toss is p. (d) Geometric with parameter p, where 0 < p ≤ 1. Here, pX (k) = (1 − p)k−1 p, k = 1, 2, . . . , . A geometric random variable with parameter p represents the number of independent tosses of a coin until heads are observed for the first time, if the probability of heads at each toss is p. (e) Poisson with parameter , where  > 0. Here, pX (k) = e− k , k! k = 0, 1, . . . . As will be seen shortly, a Poisson random variable can be thought of as a limiting case of a binomial random variable. Note that this is a legitimate PMF (i.e., it sums because of the series expansion of the exponential P to one), k /k!. function, e = 1  k=0 (f) Power law with parameter , where pX (k) = > 0. Here, 1 1 − , k (k + 1) k = 1, 2, . . . . An equivalent but more intuitive way of specifying this PMF is in terms of the formula 1 P(X ≥ k) = , k = 1, 2, . . . . k 1 In the remaining examples, the qualification “pX (k) = 0, otherwise,” will be omitted for brevity. 4 Note that when α is small, the “tail” P(X ≥ k) of the distribution decays slowly (slower than an exponential) as k increases, and in some sense such a distribution has “heavy” tails. Notation: Let us use the abbreviations dU(a, b), Ber(p), Bin(n, p), Geo(p), Pois(), and Pow(α ) to refer the above defined PMFs. We will use notation d such as X = dU(a, b) or X ∼ dU(a, b) as a shorthand for the statement that X is a discrete random variable whose PMF is uniform on (a, b), and similarly for d the other PMFs we defined. We will also use the notation X = Y to indicate that two random variables have the same PMFs. 2.1 Poisson distribution as a limit of the binomial To get a feel for the Poisson random variable, think of a binomial random variable with very small p and very large n. For example, consider the number of typos in a book with a total of n words, when the probability p that any one word is misspelled is very small (associate a word with a coin toss that results in a head when the word is misspelled), or the number of cars involved in accidents in a city on a given day (associate a car with a coin toss that results in a head when the car has an accident). Such random variables can be well modeled with a Poisson PMF. More precisely, the Poisson PMF with parameter  is a good approximation for a binomial PMF with parameters n and p, i.e., e− n! k ≈ pk (1 − p)n−k , k! k! (n − k)! k = 0, 1, . . . , n, provided  = np, n is large, and p is small. In this case, using the Poisson PMF may result in simpler models and calculations. For example, let n = 100 and p = 0.01. Then the probability of k = 5 successes in n = 100 trials is calculated using the binomial PMF as 100! · 0.015 (1 − 0.01)95 = 0.00290. 95! 5! Using the Poisson PMF with  = np = 100 · 0.01 = 1, this probability is approximated by 1 e−1 = 0.00306. 5! 5 Proposition 1. (Binomial convergence to Poisson) Let us fix some  > 0, d d and suppose that Xn = Bin(n, /n), for every n. Let X = = Pois(). Then, as n → ∞, the PMF of Xn converges to the PMF of X , in the sense that limn!1 P(Xn = k) = P(X = k), for any k ≥ 0. Proof: We have P(Xn = k) = n(n − 1) · · · (n − k + 1) k   n−k · · 1 − . nk k! n Fix k and let n → ∞. We have, for j = 1, . . . , k, n−k+j → 1, n  1−  −k → 1, n   n 1− → e− . n Thus, for any fixed k, we obtain lim P(Xn = k) = e− n!1 k = P(X = k), k! as claimed. 3 JOINT, MARGINAL, AND CONDITIONAL PMFS In most applications, one typically deals with several random variables at once. In this section, we introduce a few concepts that are useful in such a context. 3.1 Marginal PMFs Consider two discrete random variables X and Y associated with the same experiment. The probability law of each one of them is described by the corresponding PMF, pX or pY , called a marginal PMF. However, the marginal PMFs do not provide any information on possible relations between these two random variables. For example, suppose that the PMF of X is symmetric around the origin. If we have either Y = X or Y = −X, the PMF of Y remains the same, and fails to capture the specifics of the dependence between X and Y . d As another example let X = Bin(n, 1/2). Notice that then Y = n − X also has Bin(n, 1/2) as a PMF. At the same time X + Y = n and this is something that cannot be inferred from PMF alone. 6 3.2 Joint PMFs The statistical properties of two random variables X and Y are captured by a function pX,Y : R2 → [0, 1], defined by pX,Y (x, y) = P(X = x, Y = y), called the joint PMF of X and Y . We think of X and Y defined on the same probability space (Ω, F, P). Namely, X, Y : Ω → R. Then the event A = {! ∈ Ω : X(!) = x, Y (!) = y} is well defined. Then P(X = x, Y = y) is simply P(A). So that we can talk about the probability of this event we also need to ensure that the event is measurable. Exercise 1. Suppose X and Y are two discrete random variables on the same probability space (Ω , F, P). Is it the case that for every x, y ∈ R the event A = {! ∈ : X(!) = x, Y (!) = y} is measurable with respect to F? Either prove this or construct a counterexample. From this point on we assume that the events A described above are measurable and will omit the measurability issues. Here and in the sequel, we will use the abbreviated notation P(X = x, Y = y) instead of the more precise notations P({X = x} ∩ {Y = y}) or P(X = x and Y = x). More generally, the PMF of finitely many discrete random variables, X1 , . . . , Xn on the same probability space is defined by pX1 ,...,Xn (x1 , . . . , xn ) = P(X1 = x1 , . . . , Xn = xn ). Sometimes, we define a vector random variable X, by letting X = (X1 , . . . , Xn ), in which case the joint PMF will be denoted simply as pX (x), where now the argument x is an n-dimensional vector. The joint PMF of X and Y determines the probability of any event that can be specified in terms of the random variables X and Y . For example if A is the set of all pairs (x, y) that have a certain property, then X �
P (X, Y ) ∈ A = pX,Y (x, y). (x,y)2A In fact, we can calculate the marginal PMFs of X and Y by using the formulas X X pX (x) = pX,Y (x, y), pY (y) = pX,Y (x, y). y x The formula for pX (x) can be verified using the calculation X X pX (x) = P(X = x) = P(X = x, Y = y) = pX,Y (x, y), y y 7 where the second equality follows by noting that the event {X = x} is the union of the countably many disjoint events {X = x, Y = y}, as y ranges over all the different values of Y . The formula for pY (y) is verified similarly. 3.3 Conditional PMFs Let X and Y be two discrete random variables, defined on the same probability space, with joint PMF pX,Y . The conditional PMF of X given Y is a function pX|Y , defined by pX|Y (x | y) = P(X = x | Y = y), if P(Y = y) > 0; if P(Y = y) = 0, the value of pX|Y (y | x) is left undefined. Using the definition of conditional probabilities, we obtain pX|Y (x | y) = pX,Y (x, y) , pY (y) whenever pY (y) > 0. More generally, if we have random variables X1 , . . . , Xn ad Y1 , . . . , Ym , defined on the same probability space, we define a conditional PMF by letting pX1 ,...,Xn | Y1 ,...,Ym (x1 , . . . , xn | y1 , . . . , ym ) = P(X1 = x1 , . . . , Xn = xn | Y1 = y1 , . . . , Ym = ym ) pX1 ,...,Xn ,Y1 ,...,Ym (x1 , . . . , xn , y1 , . . . , ym ) = , pY1 ,...,Ym (y1 , . . . , ym ) whenever pY1 ,...,Ym (y1 , . . . , ym ) > 0. Again, if we define X = (X1 , . . . , Xn ) and Y = (Y1 , . . . , Ym ), the shorthand P notation pX|Y (x | y) can be used. Note that if pY (y) > 0, then x pX|Y (x | y) = 1, where the sum is over all x in the range of the random variable X. Thus, the conditional PMF is essentially the same as an ordinary PMF, but with redefined probabilities that take into account the conditioning event Y = y. Visually, if we fix y, the conditional PMF pX|Y (x | y), viewed as a function of x is a “slice” of the joint PMF pX,Y , renormalized so that its entries sum to one. 4 INDEPENDENCE OF RANDOM VARIABLES We now define the important notion of independence of random variables. We start with a general definition that applies to all types of random variables, including discrete and continuous ones. We then specialize to the case of discrete random variables. 8 4.1 Independence of general random variables Intuitively, two random variables are independent if any partial information on the realized value of one random variable does not change the distribution of the other. This notion is formalized in the following definition. Definition 2. (Independence of random variables) (a) Let X1 , . . . , Xn be random variables defined on the same probability space. We say that these random variables are independent if the events X1 ∈ B1 , . . . , Xn ∈ Bn are independent for any Borel subsets B1 , . . . , Bn of the real line. Namely, P(X1 ∈ B1 , . . . , Xn ∈ Bn ) = P(X1 ∈ B1 ) · · · P(Xn ∈ Bn ), for any Borel subsets B1 , . . . , Bn . (b) Let {Xs | s ∈ S} be a collection of random variables indexed by the elements of a (possibly infinite) index set S . We say that these random variables are independent if for every finite subset {s1 , . . . , sn } of S , the random variables Xs1 , . . . , Xsn are independent. Verifying the independence of random variables using the above definition (which involves arbitrary Borel sets) is rather difficult. It turns out that one only needs to examine Borel sets of the form (−∞, x]. Proposition 2. Suppose that for every n, every x1 , . . . , xn , and every finite subset {s1 , . . . , sn } of S , the events {Xsi ≤ xi }, i = 1, . . . , n, are independent. Then, the random variables Xs , s ∈ S , are independent. The proof is a simple application of Theorem 2 from Lecture 3 applied to a generating p-system (−∞, x]. Let us define the joint CDF of of the random variables X1 , . . . , Xn by FX1 ,...,Xn (x1 , . . . , xn ) = P(X1 ≤ x1 , . . . , Xn ≤ xn ). In view of Proposition 2, independence of X1 , . . . , Xn is equivalent to the condition FX1 ,...,Xn (x1 , . . . , xn ) = FX1 (x1 ) · · · FXn (xn ), 9 ∀ x1 , . . . , xn . Exercise 2. Consider a collection {As | s ∈ S} of events, where S is a (possibly infinite) index set. Prove that the events As are independent if and only if the corresponding indicator functions IAs , s ∈ S, are independent random variables. 4.2 Independence of discrete random variables For a finite number of discrete random variables, independence is equivalent to having a joint PMF which factors into a product of marginal PMFs. Theorem 1. Let X and Y be discrete random variables defined on the same probability space. The following are equivalent. (a) The random variables X and Y are independent. (b) For any x, y ∈ R, the events {X = x} and {Y = y} are independent. (c) For any x, y ∈ R, we have pX,Y (x, y) = pX (x)pY (y). (d) For any x, y ∈ R such that pY (y) > 0, we have pX|Y (x | y) = pX (x). Proof: The fact that (a) implies (b) is immediate from the definition of independence, since recall that the sets consisting of one point {x}, {y} are Borel sets. That (b) implies (c), and (c) implies (d) is also an immediate consequence of our definitions. Let us show that (d) implies (c). For the case when pY (y) > 0, we have pX,Y (x, y) = pX|Y (x | y)pY (y) = pX (x)pY (y). When pY (y) = 0, we have also pX (x)pY (y) = 0. So in order to show the identity we need pX,Y (x, y) = 0. But pX,Y (x, y) = P(X = x, Y = y) ≤ P(Y = y) = 0, and we have verified that both parts equal zero. We complete the proof by verifying that (c) implies (a). Suppose that X and Y are independent, and let A, B, be two Borel subsets of the real line. We then 10 have X P(X = x, Y = y) X pX,Y (x, y) = X pX (x)pY (x) = X P(X ∈ A, Y ∈ B) = = x2A, y2B x2A, y2B x2A, y2B x2A  X  pY (y) pX (x) y2B = P(X ∈ A) P(Y ∈ B). Since this is true for any Borel sets A and B, we conclude that X and Y are independent. We note that Theorem 1 generalizes to the case of multiple, but finitely many, random variables. The generalization of conditions (a)-(c) should be obvious. As for condition (d), it can be generalized to a few different forms, one of which is the following: given any subset S0 of the random variables under consideration, the conditional joint PMF of the random variables Xs , s ∈ S0 , given the values of the remaining random variables, is the same as the unconditional joint PMF of the random variables Xs , s ∈ S0 , as long as we are conditioning on an event with positive probability. We finally note that functions g(X) and h(Y ) of two independent random variables X and Y must themselves be independent. This should be expected on intuitive grounds: If X is independent from Y , then the information provided by the value of g(X) should not affect the distribution of Y , and consequently should not affect the distribution of h(Y ). Observe that when X and Y are discrete, then g(X) and h(Y ) are random variables (the required measurability conditions are satisfied) even if the functions g and h are not measurable (why?). Theorem 2. Let X and Y be independent discrete random variables. Let g and h be some functions from R into itself. Then, the random variables g(X) and h(Y ) are independent. The proof is left as an exercise. 4.3 Examples Example. Let X1 , . . . , Xn be independent Bernoulli random variables with the same 11 parameter p. Then, the random variable X defined by X = X1 + · · · + Xn is binomial with parameters n and p. To see this, consider n independent tosses of a coin in which every toss has probability p of resulting in a one, and let Xi be the result of the ith coin toss. Then, X is the number of ones observed in n independent tosses, and is therefore a binomial random variable. Example. Let X and Y be independent binomial random variables with parameters (n, p) and (m, p), respectively. Then, the random variable Z, defined by Z = X + Y is binomial with parameters (n + m, p). To see this, consider n + m independent tosses of a coin in which every toss has probability p of resulting in a one. Let X be the number of ones in the first n tosses, and let Y be the number of ones in the last m tosses. Then, Z is the number of ones in n+m independent tosses, which is binomial with parameters (n + m, p). Example. Consider n independent tosses of a coin in which every toss has probability p of resulting in a one. Let X be the number of ones obtained, and let Y = n − X, which is the number of zeros. The random variables X and Y are not independent. For example, P(X = 0) = (1 − p)n and P(Y = 0) = pn , but P(X = 0, Y = 0) = 0 6= P(X = 0)P(Y = 0). Intuitively, knowing that there was a small number of heads gives us information that the number of tails must be large. However, in sharp contrast to the intuition from the preceding example, we obtain independence when the number of coin tosses is itself random, with a Poisson distribution. More precisely, let N be a Poisson random variable with parameter . We assume that X has conditional PMF pX|N (· | n) is binomial with parameters n and p (representing the number of ones observed in n coin tosses), and define Y = N − X, which represents the number of zeros obtained. We have the following surprising result. An intuitive justification will have to wait until we consider the Poisson process, later in this course. The proof is left as an exercise. Theorem 3. (Splitting of a Poisson random variable) The random d d variables � X and
Y are independent. Moreover, X = Pois(p) and Y = Pois (1 − p) . 12 5 EXPECTED VALUES 5.1 Preliminaries: infinite sums Consider a sequence {an } of nonnegative Pn real numbers and the infinite sum P1 a , defined as the limit, lim i n!1 i=1 i=1 ai , of the partial sums. The infinite sum can be finite or infinite; in either case, it is well defined, as long as we allow the limit to be an extended real number. Furthermore, it can be verified that the value of the infinite sum is the same even if we reorder the elements of the sequence {an } and carry out the summation according to this different order. Because the order of the summation does not matter, we can use the P notation n2N an for the infinite sum. More generally, if C is a countable set and g : C → [0, ∞) is a nonnegative function, we can use the notation P x2C g(x), which is unambiguous even without specifying a particular order in which the values g(x) are to be summed. When we consider a sequence of nonpositive real numbers, the discussion remains the same, and infinite sums can be unambiguously defined. However, when we consider sequences that involve both positive and negative numbers, the situation is more complicated. In particular, the order at which the elements of the sequence are added can make a difference. Pn Example. Let an = (−1)n /n. It can be verified that the limit limn!1 i=1 an exists, and is finite, but that the elements of the sequence {an } can be reordered to form a new Pn sequence {bn } for which the limit of i=1 bn does not exist. In order to deal with the general case, we proceed as follows. Let S be a countable set, and consider a collection of real numbers as , s ∈ S. Let S+ (respectively, P S− ) be the set of indices P s for which as ≥ 0 (respectively, as < 0). Let S+ = s2S+ as and S− = s2S− |as |. We distinguish four cases. P (a) If both S+ and P S− are finite (or equivalently, if s2S |as | < ∞), we say that the sum s2S as is absolutely convergent, and is equal to S+ −S− . In this case, for every possible arrangement of the elements of S in a sequence {sn }, we have n X lim asi = S + − S− . n!1 i=1 P (b) If S+ = ∞ and S− < ∞, the sum s2S as is not absolutely convergent; we define it to be equal to ∞. In this case, for every possible arrangement of the elements of S in a sequence {sn }, we have lim n!1 n X i=1 13 asi = ∞. P (c) If S+ < ∞ and S− = ∞, the sum s2S as is not absolutely convergent; we define it to be equal to −∞. In this case, for every possible arrangement of the elements of S in a sequence {sn }, we have lim n!1 n X i=1 asi = −∞. P (d) If S+ = ∞ and S− = ∞, the sum s2S an is left undefined. In fact, in this case, different arrangements of the elements of S in a sequence {sn } will result into different or even nonexistent values of the limit lim n!1 n X as i . i=1 To summarize, we consider a countable sum to be well defined in cases (a)(c), and call it absolutely convergent only in case (a). We close by recording a related useful fact. If we have a doubly indexed family of nonnegative numbers P aij , i, j ∈ N, and if either (i) the numbers are nonnegative, or (ii) the sum (i,j) aij is absolutely convergent, then 1 X 1 X i=1 j=1 aij = 1 X 1 X j=1 i=1 aij = X aij . (1) (i,j)2N2 More important, we stress that the first equality need not hold in the absence of conditions (i) or (ii) above. 5.2 Definition of the expectation The PMF of a random variable X provides us with several numbers, the probabilities of all the possible values of X. It is often desirable to summarize this information in a single representative number. This is accomplished by the expectation of X, which is a weighted (in proportion to probabilities) average of the possible values of X. As motivation, suppose you spin a wheel of fortune many times. At each spin, one of the numbers m1 , m2 , . . . , mn comes up with corresponding probability p1 , p2 , . . . , pn , and this is your monetary reward from that spin. What is the amount of money that you “expect” to get “per spin”? The terms “expect” and “per spin” are a little ambiguous, but here is a reasonable interpretation. 14 Suppose that you spin the wheel k times, and that ki is the number of times that the outcome is mi . Then, the total amount received is m1 k1 + m2 k2 + · · · + mn kn . The amount received per spin is M= m1 k1 + m2 k2 + · · · + mn kn . k If the number of spins k is very large, and if we are willing to interpret probabilities as relative frequencies, it is reasonable to anticipate that mi comes up a fraction of times that is roughly equal to pi : ki ≈ pi , k i = 1, . . . , n. Thus, the amount of money per spin that you “expect” to receive is M= m1 k1 + m2 k2 + · · · + mn kn ≈ m1 p 1 + m2 p 2 + · · · + mn p n . k Motivated by this example, we introduce the following definition. Definition 3. (Expectation) We define the expected value (also called the expectation or the mean) of a discrete random variable X , with PMF pX , as X E[X] = xpX (x), x whenever the sum is well defined, and where the sum is taken over the countable set of values in the range of X . Observe that E[X] is non-negative if X only takes non-negative values with positive probability. (Namely, pX (x) > 0 implies x ≥ 0). 5.3 Properties of the expectation We start by pointing out an alternative formula for the expectation, and leave its proof as an exercise. In particular, if X can only take nonnegative integer values, then X E[X] = P(X > n). (2) n0 Example. Using this formula, it is easy to give an example of a random variable for d which the expected value is infinite. Consider X = Pow( α ), where α ≤ 1. Then, it can 15 P1 P be verified, using the fact n=1 1/n = ∞, that E[X] = n0 hand, if α > 1, then E[X] < ∞. 1 n = ∞. On the other Here is another useful fact, whose proof is again left as an exercise. Proposition 3. Given a discrete random variable X and a function g : R → R, we have X E[g(X)] = g(x)pX (x). (3) {x | pX (x)>0} More generally, this formula remains valid given a vector X = (X1 , . . . , Xn ) of random variables with joint PMF pX = pX1 ,...,Xn , and a function g : Rn → R. For example, suppose that X is a discrete random variable and consider the function g : R → R defined by g(x) = x2 . Let Y = g(X). In order to calculate the expectation E[Y ] according to Definition P 2, we need to first find the PMF of Y , and then use the formula E[Y ] = y ypY (y). However, according to Proposition 3, we can work directly with the PMF of X, and write P E[Y ] = E[X 2 ] = x x2 pX (x). The quantity E[X 2 ] is called the second moment of X. More generally, if � r ∈ N, the
quantity E[X r ] is called the rth moment of X. Furthermore, r E X − E[X] is called the rth central moment of X. The second central moment, E[(X −E[X])2 ] is called the variance of X, and is denoted by var(X). The square root of the variance is called the standard deviation of X, and is often denoted by ˙X , or just ˙. Note, that for every even r, the rth moment and the rth central moment are always nonnegative; in particular, the standard deviation is always well defined. We continue with a few more important properties of expectations. In the sequel, notations such as X ≥ 0 or X = c mean that X(!) ≥ 0 or X(!) = c, respectively, for all ! ∈ Ω . Similarly, a statement such as “X ≥ 0, almost surely” or “X ≥ 0, a.s.,” means that P(X ≥ 0) = 1. 16 Proposition 4. Let X and Y be discrete random variables defined on the same probability space. (a) If X ≥ 0, a.s., then E[X] ≥ 0. (b) If X = c, a.s., for some constant c ∈ R, then E[X] = c. (c) Linearity of expectation. For any a, b ∈ R, we have E[aX + bY ] = aE[X] + bE[Y ] (as long as the sum aE[X] + bE[Y ] is well-defined). (d) If E[X] is finite, then var(X) = E[X 2 ] − (E[X])2 . (e) For every a ∈ R, we have var(aX) = a2 var(X). (f) If X and Y are independent and have finite expectations, then E[XY ] = E[X]E[Y ] and var(X + Y ) = var(X) + var(Y ). (g) More generally, if X1 , . . . , Xn are independent and have finite expectations, then E n hY i=1 n i Y E[Xi ], Xi = i=1 and var n X i=1 n  X Xi = var(Xi ). i=1 Remark: We emphasize that property (c) does not require independence. Proof: We only give the proof for the case where all expectations involved are well defined and finite, and leave it to the reader to verify that the results extend to the case where all expectations involved are well defined but possibly infinite. Parts (a) and (b) are immediate consequences of the definitions. For part (c), we use the second part of Proposition 3, and then Eq. (1), we obtain X E[aX + bY ] = (ax + by)pX,Y (x, y) x,y = X x = a X ax X y  X X  by pX,Y (x, y) pX,Y (x, y) + y xpX (x) + b x X y = aE[X] + bE[Y ]. 17 ypY (y) x For part (d), we have   var(X) = E X 2 − 2XE[X] + (E[X])2   = E[X 2 ] − 2E XE[X] + (E[X])2 = E[X 2 ] − 2(E[X])2 + (E[X])2 = E[X 2 ] − (E[X])2 . where the second equality made use of property (c). Part (e) follows easily from (d) and (c). For part (f), we apply Proposition 3 and then use independence to obtain X E[XY ] = xypX,Y (x, y) x,y = X xypX (x)pY (y) x,y = X x  X  ypY (y) xpX (x) y = E[X] E[Y ]. Furthermore, using property (d), we have var(X + Y ) = E[(X + Y )2 ] − (E[X + Y ])2 = E[X 2 ] + E[Y 2 ] + 2E[XY ] − (E[X])2 − (E[Y ])2 − 2E[X]E[Y ]. Using the equality E[XY ] = E[X]E[Y ], the above expression becomes var(X)+ var(Y ). The proof of part (g) is similar and is omitted. Remark: The equalities in part (f) need not hold in the absence of independence. For example, consider a random variable X that takes either value 1 or −1, with probability 1/2. Then, E[X] = 0, but E[X 2 ] = 1. If we let Y = X, we see �
2 that E[XY ] = E[X 2 ] = 1 6= 0 = E[X] . Furthermore, var(X + Y ) = var(2X) = 4var(X), while var(X) + var(Y ) = 2. Exercise 3. Show that var(X) = 0 if and only if there exists a constant c such that P(X = c) = 1. 18