DOC PREVIEW
Berkeley COMPSCI 70 - n15

This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

EECS 70 Discrete Mathematics and Probability TheorySpring 2014 Anant Sahai Note 15Random Variables: Distributions, Independence, and ExpectationsIn the last note, we saw how useful it is to have a way of thinking about quantities that are inherently random.In this section, we will introduce the notion of a random variable, which allows us to more directly deal withquestions like "what is the number of . . . ".In our coin flipping examples, let us call the number of H’s in n coin flips X. Of course, X is not a fixednumber. It depends upon the actual sequence of coin flips that we toss. What we know is that X is an integerbetween 0 and n, and if the coin is fair. We would also like to show that if the coin is fair, then with veryhigh probability X takes on a value very close ton2. Before we formalize the notion of a random variable,let us consider another example.Question: 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.As in the coin flipping case above, our question does not have a simple numerical answer (such as 6),because the number depends on the particular permutation we choose (i.e., on the sample point). Let’s callthe number of fixed points X. To make life simpler, let’s also shrink the class size down to 3 for a while. Thefollowing table gives a complete listing of the sample space (of size 3! = 6), together with the correspondingvalue of X for each sample point. [We use our bookshelf convention for writing a permutation: thus, forexample, the permutation 312 means that book 3 is on the left, book 1 in the center, and book 2 on the right.You should check you agree with 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.EECS 70, Spring 2014, Note 15 1Figure 1: Visualization of how a random variable is defined on the sample space.Random VariablesLet us formalize the concepts discussed above.Definition 15.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 random variables that are discrete, i.e., they take values ina range that is finite or countably infinite.A random variable can be visualized in general by the picture in Figure 11. Note that the term "randomvariable" is really something of a misnomer: it is a function so there is nothing random about it and it isdefinitely not a variable! What is random is which sample point of the experiment is realized and hence thevalue that the random variable maps the sample point to.DistributionWhen we introduced the basic probability space in Note 11, we defined two things: 1) the sample space Ωconsisting of all the possible outcomes (sample points) of the experiment; 2) the probability of each of thesample points. Analogously, there are two things important about any random variable: 1) the set of valuesthat it can take ; 2) the probabilities with which it takes on the values. Since a random variable is defined ona probability space, we can calculate these probabilities given the probabilities of the sample points. Let abe any number in the range of a random variable X . 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 possible1This and other figures in this note are inspired by figures in Chapter 2 of "Introduction to Probability" by D. Bertsekas and J.Tsitsiklis.EECS 70, Spring 2014, Note 15 2Figure 2: Visualization of how the distribution of a random variable is defined.values of a, is known as the distribution of the r.v. X.Definition 15.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.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.The distribution of a random variable can be visualized as a bar diagram, shown in Figure 2. The x-axisrepresents the values that the random variable can take on. The height of the bar at a value a is the probabilityPr[X = a]. Each of these probabilities can be computed by looking at the probability of the correspondingevent in the sample space.Note that the collection of events X = a, a ∈ A , satisfy two important properties:• any two events X = a1and X = a2with a16= a2are disjoint.• the union of all these events is equal to the entire sample space Ω.The collection of events thus form a partition of the sample space (see Figure 2). Both properties followdirectly from the fact that X is a function defined on Ω, i.e., X assigns a unique value to each and everypossible sample point in Ω. As a consequence, the sum of the probabilities Pr[X = a] over all possibleEECS 70, Spring 2014, Note 15 3values of a is exactly 1. So when we sum up the probabilities of the events X = a, we are really summingup the probabilities of all the sample points.Another useful term is the Probability Mass Function (or PMF) of a random variable. This is usually denotedPX(i) and is simply defined to be Pr[X = i] = Pr[{ω ∈ Ω|X(ω ) = i}]. The probability mass function inheritscertain properties from


View Full Document

Berkeley COMPSCI 70 - n15

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

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 n15
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 n15 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 n15 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?