Unformatted text preview:

CS 70 Discrete Mathematics for CSSpring 2007 Luca Trevisan Lecture 19Random Variables and ExpectationQuestion: The homeworks of 20 students are collected in, randomly shuffled and returned to the students.How many students receive their own homework?To answer this question, we first need to specify the probability space: plainly, it should consist of all 20!permutations of the homeworks, each with probability120!. [Note that this is the same as the probabilityspace for card shuffling, except that the number of items being shuffled is now 20 rather than 52.] It helpsto have a picture of a permutation. Think of 20 books lined up on a shelf, labeled from left to right with1, 2, . . . , 20. A permutationπis just a reordering of the books, which we can describe just by listing theirlabels from left to right. Let’s denote byπithe label of the book that is in position i. We are interested in thenumber of books that are still in their original position, i.e., in the number of i’s such thatπi= i. These areoften known as fixed points of the permutation.Of course, our question does not have a simple numerical answer (such as 6), because the number depends onthe particular permutation we choose (i.e., on the sample point). Let’s call the number of fixed points X. Tomake life simpler, let’s also shrink the class size down to 3 for a while. The following table gives a completelisting of the sample space (of size 3! = 6), together with the corresponding value of X for each samplepoint. [We use our bookshelf convention for writing a permutation: thus, for example, the permutation 312means that book 3 is on the left, book 1 in the center, and book 2 on the right. You should check you agreewith this table.]permutationπvalue of X123 3132 1213 1231 0312 0321 1Thus we see that X takes on values 0, 1 or 3, depending on the sample point. A quantity like this, whichtakes on some numerical value at each sample point, is called a random variable (or r.v.) on the samplespace.Definition 19.1 (random variable): A random variable X on a sample spaceΩis a function that assignsto each sample pointω∈Ωa real number X(ω).Until further notice, we’ll restrict out attention to discrete random variables: i.e., their values will be integersor rationals, rather than arbitrary real numbers.The r.v. X in our permutation example above is completely specified by its values at all sample points, asCS 70, Spring 2007, Lecture 19 1given in the above table. (Thus, for example, X(123) = 3 etc.)Rather than the value at each sample point, we are usually more interested in the set of points at which ther.v. takes on some given value. Let a be any real number. Then the set{ω∈Ω: X(ω) = a}is an event in the sample space (why?). We usually abbreviate this event to simply “X = a”. Since X = a isan event, we can talk about its probability, Pr[X = a]. The collection of these probabilities, for all possiblevalues of a, is known as the distribution of the r.v. X.Definition 19.2 (distribution): The distribution of a discrete random variable X is the collection of values{(a, Pr[X = a]) : a ∈ A }, where A is the set of all possible values taken by X. [In most of our examples, Awill be (some subset of) the integers.]Thus the distribution of the random variable X in our permutation example above isPr[X = 0] =13; Pr[X = 1] =12; Pr[X = 3] =16;and Pr[X = a] = 0 for all other values of a.Notice that the sum of the probabilities Pr[X = a] over all possible values of a is exactly 1. This must alwaysbe the case, for any random variable. Why? Because any random variable X must take on one, and onlyone, value X(ω) at every sample pointω. I.e., the events X = a partition the sample space. So when wesum up the probabilities of the events X = a, we are really summing up the probabilities of all the samplepoints.ExpectationIn most applications, the complete distribution of a r.v. is very hard to calculate: for example, suppose wego back to our original question with 20 students. In principle, we’d have to enumerate 20! ≈ 2.4 × 1018sample points, compute the value of X at each one, and count the number of points at which X takes on eachof its possible values! Moreover, even when we can compute the complete distribution of a r.v., it is oftennot very informative.For these reasons, we seek to compress the distribution into a more compact, convenient form that is alsoeasier to compute. The most widely used such form is the expectation (or mean or average) of the r.v.Definition 19.3 (expectation): The expectation of a discrete random variable X is defined asE(X) =∑a∈Aa× Pr[X = a],where the sum is over all possible values taken by the r.v.For our running permutation example, the expectation isE(X) =0×13+1×12+3×16= 0+12+12= 1.I.e., the expected number of fixed points in a permutation of three items is exactly 1.CS 70, Spring 2007, Lecture 19 2The expectation can be seen in some sense as a “typical” value of the r.v. (though note that it may notactually be a value that the r.v. ever takes on). The question of how typical the expectation is for a given r.v.is a very important one that we shall return to in a later lecture.Here are some simple examples of expectations.1. Single die. Throw one fair die. Let X be the number that comes up. Then X takes on values 1, 2, . . . , 6each with probability16, soE(X) =16(1+ 2+ 3+ 4+ 5+ 6) =216=72.Note that X never actually takes on its expected value72.2. Two dice. Throw two fair dice. Let X be the sum of their scores. Then the distribution of X isa 2 3 4 5 6 7 8 9 10 11 12Pr[X = a]136118112195361653619112118136The expectation is thereforeE(X) =2×136+3×118+4×112+ ··· +12×136= 7.3. Roulette. A roulette wheel is spun. You bet $1 on Black. If a black number comes up, you receiveyour stake plus $1; otherwise you lose your stake. Let X be your net winnings in one game. Then Xcan take on the values +1 and −1, and Pr[X = 1] =1838, Pr[X = −1] =2038. [Recall that a roulette wheelhas 38 slots: the numbers 1, 2, . . . , 36, half of which are red and half black, plus 0 and 00, which aregreen.] ThusE(X) =1×1838+−1×2038= −119;i.e., you expect to lose about a nickel per game. Notice how the zeros tip the balance in favor of thecasino!Linearity of expectationSo far, we’ve computed expectations by brute force: i.e., we have written down the whole distribution andthen added up the contributions for all possible values of


View Full Document

Berkeley COMPSCI 70 - Random Variables and Expectation

Documents in this Course
Notes 1

Notes 1

12 pages

Note 2

Note 2

6 pages

Notes

Notes

6 pages

Notes

Notes

7 pages

Note 10

Note 10

8 pages

n20

n20

10 pages

n19

n19

10 pages

n18

n18

10 pages

n17

n17

6 pages

n16

n16

9 pages

n15

n15

10 pages

n14

n14

9 pages

n13

n13

6 pages

n12

n12

7 pages

n11

n11

6 pages

n10

n10

8 pages

n9

n9

5 pages

n8

n8

7 pages

n7

n7

8 pages

n6

n6

5 pages

n5

n5

8 pages

n4

n4

7 pages

n3

n3

10 pages

n2

n2

7 pages

n1

n1

5 pages

Load more
Download Random Variables and Expectation
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Random Variables and Expectation and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Random Variables and Expectation 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?