CSE 312 – Section 4

Review of Main Concepts

• Random Variable (rv): A numeric function \(X:\Omega \to \mathbb {R}\) of the outcome.
• Range/Support: The support/range of a random variable \(X\), denoted \(\Omega _{X}\), is the set of all possible values that \(X\) can take on.
• Discrete Random Variable (drv): A random variable taking on a countable (either finite or countably infinite) number of possible values.
• Probability Mass Function (pmf) for a discrete random variable \(X\): a function \(p_{X}:\Omega _{X} \rightarrow \lbrack 0,1\rbrack \) with \(p_{X}\left ( x \right ) = \Pr (X = x)\) that maps possible values of a discrete random variable to the probability of that value happening, such that \(\sum _{x}^{}{p_{X}(x)} = 1\).
• Cumulative Distribution Function (CDF) for a random variable \(X\): a function \(F_{X}:R \rightarrow R\) with \(F_{X}\left ( x \right ) = \Pr (X \le x)\)
• Expectation (expected value or mean): The expectation of a discrete random variable is defined to be \(\Exp [X ] = \sum _{x}^{}{xp_{X}(x)} = \sum _{x}{x\Pr (X = x)}\).
• Law of the unconscious statistician (LOTUS): The expectation of a function of a discrete random variable \(g(X)\) is \(\Exp [ g(X)] = \sum _{x}{g(x)p_{X}(x)}\).
• Linearity of Expectation (LoE): Let \(X\) and \(Y\) be random variables, and \(a,b,c\mathbb {\in R}\). Then, \(\Exp [aX + bY + c] = a \Exp [X] + b\Exp [Y]+c\). Also, for any random variables \(X_1, \ldots , X_n\), \[\Exp [X_1 + X_2 + \ldots + X_n] =\Exp [X_1] + \Exp [X_2] + \ldots + \Exp [X_n].\]
• Variance: Let \(X\) be a random variable and \(\mu = \Exp [X]\). The variance of \(X\) is defined to be \(\Var (X)=\Exp [(X-\mu )^2] \). Notice that since this is an expectation of a non-negative random variable (\(\left ( X - \mu \right )^{2}\)), variance is always non-negative. With some algebra, we can simplify this to \(\Var ( X) = \Exp [ X^{2}] - \Exp [X]^2\).
• Standard Deviation: Let \(X\) be a random variable. We define the standard deviation of \(X\) to be the square root of the variance, and denote it \(\sigma =\sqrt {\Var (X)}\).
• Property of Variance: Let \(a,b \ \mathbb {\in R}\) and let \(X\) be a random variable. Then, \(\Var (aX+b)=a^2\Var (X)\).
• Independence: Random variables \(X\) and \(Y\) are independent iff \[\forall x \forall y,\quad \Pr ( X = x \cap Y = y) = \Pr ( X = x)\Pr (Y = y)\] In this case, we have \(\Exp [XY]= \Exp [X]\Exp [Y]\) (the converse is not necessarily true).
• i.i.d. (independent and identically distributed): Random variables \(X_{1},\ldots ,X_{n}\) are i.i.d. (or iid) iff they are independent and have the same probability mass function.
• Variance of Independent Variables: If \(X\) is independent of \(Y\), \(\Var \left ( X + Y \right ) = \Var \left ( X \right ) + \Var (Y)\). This depends on independence, whereas linearity of expectation always holds. Note that this combined with the above shows that \(\forall a,b,c\ \mathbb {\in R}\) and if \(X\) is independent of \(Y\), \(\Var (aX + bY + c) =a^{2}\Var (X) + b^{2}\Var (Y)\).

Announcements & Plan for Section

Announcements

• PSet 2 grades were released and can be viewed on Gradescope. Regrade requests will close on 4/25. We highly recommend taking a look through feedback on the psets, the common errors on Ed and the solutions that were posted (link on Ed).
• PSet 3 was due earlier this week.
• PSet 4 is released — start early.
• This week’s focus: Linearity of Expectation, LOTUS, and Variance, leading into discrete random variables.

Plan for Section

• Content Review (Problem 1)
  Quick check of core definitions: PMF vs CDF, expectation, and variance.
• Problem 3 (3-sided die)
  Build intuition for PMFs and practice computing expectation both directly and using linearity.
• Problem 8 (Hungry washing machine)
  Key application of indicator variables and linearity of expectation — avoiding messy counting.
• Problem 11 (Hat check)
  Classic example showing linearity of expectation works even without independence.
• Problem 5 (if time)
  Reinforces thinking about ranges/support of random variables.
• Problem 6 (if time)
  Additional practice connecting PMFs, expectations, and variance.

1  Content Review

a)

True or false: the range of a random variable \(X\) is the set of probabilities corresponding to the possible values \(X\) can take on.

b)

What is the relationship between standard deviation and variance of a random variable \(X\)?

• \(\sigma = (\Var (X))^2\)
• \(\sigma = \Var (X^2)\)
• \(\Var (X) = \sigma ^2\)

c)

Let \(X\) be the random variable representing the the sum of a 3-dice roll of 6-sided dice. Which function would you use to determine the probability that \(X=7\)?

• CDF (cumulative distribution function)
• PMF (probability mass function)

d)

Let \(X\) be the random variable representing the outcome of taking the sum of a 3-dice roll of 6-sided dice. Which function would you use to determine the probability that \(X \leq 7\)?

• CDF (cumulative distribution function)
• PMF (probability mass function)

e)

A random variable \(X\) has the PMF \[p_X(x) = \begin {cases} 1/4 & x=-1 \\ 1/4 & x=0 \\ 1/2 & x=2 \\ 0 & \text {otherwise} \end {cases}\] What is \(\Exp [X]\)?

• -1/4
• 3/4
• 1
• 2

f)

A random variable \(X\) has the PMF \[p_X(x) = \begin {cases} 1/4 & x=-1 \\ 1/4 & x=0 \\ 1/2 & x=2 \\ 0 & \text {otherwise} \end {cases}\] What is \(\Var (X)\)?

• \(3/4\)
• \(1\)
• \(((1/4)+2)-((\frac {3}{4})^2) = 27/16\)
• \(((1/4)+2)+((\frac {3}{4})^2) = 45/16\)

g)

A random variable \(X\) has the CDF \[ F_X(x) = \begin {cases} 0 & x < 1 \\ \frac {1}{5} & 1 \le x < 2 \\ \frac {1}{2} & 2 \le x < 3 \\ \frac {3}{5} & 3 \le x < 4 \\ 1 & x \ge 4 \end {cases} \] What is \(p_X(2)\)?

• \(3/10\)
• \(1/2\)
• \(7/10\)
• \(1/5\)

2  Identify that Range!

Identify the support/range \(\Omega _X\) of the random variable \(X\), if \(X\) is...

a)

The sum of two rolls of a six-sided die.

b)

The number of lottery tickets I buy until I win it (assuming I buy at least one lottery ticket).

c)

The number of heads in \(n\) flips of a coin with \(0<\Pr (\text {head})<1\).

d)

The number of heads in \(n\) flips of a coin with \(\Pr (\text {head})=1\).

e)

The number of whole minutes I wait at the bus stop for the next bus.

3  3-sided Die

Let the random variable \(X\) be the sum of two independent rolls of a fair 3-sided die. (If you are having trouble imagining what that looks like, you can use a 6-sided die and change the numbers on 3 of its faces.)

a)

What is the probability mass function of \(X\)?

b)

Find \(\Exp [X]\) directly from the definition of expectation.

c)

Find \(\Exp [X]\) again, but this time using Linearity of Expectation.

d)

What is \(\Var (X)\)?

4  Kit Kats Again

Suppose we have \(N\) candies in a jar, \(K\) of which are Kit-Kats. Suppose we draw (without replacement) until we have (exactly) \(k\) Kit-Kats, where \(k \leq K \leq N\). Let \(X\) be the number of draws until the \(k^{\text {th}}\) Kit-Kat. What is \(\Omega _{X}\), the range of \(X\)? What is \(p_{X}\left ( n \right ) = \Pr (X = n)\)? (\(X\) is called a “negative hypergeometric” random variable).

5  Hungry Washing Machine

You have 10 pairs of socks (so 20 socks in total), with each pair being a different color. You put them in the washing machine, but the washing machine eats 4 of the socks chosen at random. Every subset of 4 socks is equally probable to be the subset that gets eaten. Let \(X\) be the number of complete pairs of socks that you have left.

a)

What is the range of \(X\), \(\Omega _X\) (the set of possible values it can take on)? What is the probability mass function of \(X\)?

b)

Find \(\Exp [X]\) from the definition of expectation.

c)

Find \(\Exp [X]\) using Linearity of Expectation. (see this video for a walkthrough of this problem!)

d)

Which way was easier? Doing both (a) and (b), or just (c)?

6  Hat Check

At a reception, \(n\) people give their hats to a hat-check person. When they leave, the hat-check person gives each of them a hat chosen at random from the hats that remain. What is the expected number of people who get their own hats back? (Notice that the hats returned to two people are not independent events: if a certain hat is returned to one person, it cannot also be returned to the other person.)

Note: See this video for a walkthrough of this problem!

7  Frogger

A frog starts on a 1-dimensional number line at \(0\). At each second, independently, the frog takes a unit step right with probability \(p_{1}\), to the left with probability \(p_{2}\), and doesn’t move with probability \(p_{3}\), where \(p_{1} + p_{2} + p_{3} = 1\). After 2 seconds, let \(X\) be the location of the frog.

a)

Find \(p_{X}(k)\), the probability mass function for \(X\).

b)

Compute \(\Exp [X]\) from the definition.

c)

Compute \(\Exp [X]\) again, but using Linearity of Expectation.

8  Balls in Bins

Let \(X\) be the number of bins that remain empty when \(m\) balls are distributed into \(n\) bins randomly and independently. For each ball, each bin has an equal probability of being chosen. (Notice that two bins being empty are not independent events: if one bin is empty, that decreases the probability that the second bin will also be empty. This is particularly obvious when \(n=2\) and \(m>0\).) Find \(\Exp [X]\).

9  Fair Game?

You flip a fair coin independently and count the number of flips until the first tail, including that tail flip in the count. If the count is \(n\), you receive \(2^n\) dollars. What is the expected amount you will receive? How much would you be willing to pay at the start to play this game?

10  Symmetric Difference

Suppose \(A\) and \(B\) are random, independent (possibly empty) subsets of \(\{1,2,\ldots ,n\}\), where each subset is equally likely to be chosen as \(A\) or \(B\). Consider \(A \Delta B=(A\cap B^C)\cup (B\cap A^C)=(A\cup B)\cap (A^C\cup B^C)\), i.e., the set containing elements that are in exactly one of \(A\) and \(B\). Let \(X\) be the random variable that is the size of \(A \Delta B\). What is \(\Exp [X]\)?

11  Practice

a)

Let \(X\) be a random variable with \(p_X(k)=ck\) for \(k\in \{1,\dots ,5\}=\Omega _X\), and \(0\) otherwise. Find the value of \(c\) that makes \(X\) follow a valid probability distribution and compute its mean and variance (\(\Exp [X]\) and \(\Var (X)\)).

b)

Let \(X\) be any random variable with mean \(\Exp [X]=\mu \) and variance \(\Var (X)=\sigma ^2\). Find the mean and variance of \(Z=\dfrac {X-\mu }{\sigma }\). (When you’re done, you’ll see why we call this a “standardized” version of \(X\)!)

c)

Let \(X,Y\) be independent random variables. Find the mean and variance of \(X-3Y-5\) in terms of \(\Exp [X],\Exp [Y],\Var (X)\), and \(\Var (Y)\).

d)

Let \(X_1,\dots ,X_n\) be independent and identically distributed (iid) random variables each with mean \(\mu \) and variance \(\sigma ^2\). The sample mean is \(\bar {X}=\frac {1}{n}\sum _{i=1}^n{X_i}\). Find the mean and variance of \(\bar {X}\). If you use the independence assumption anywhere, explicitly label at which step(s) it is necessary for your equalities to be true.

12  Coin Flipping

Suppose we have a coin with probability \(p\) of heads. Suppose we flip this coin until we flip a head for the first time. Let \(X\) be the number of times we flip the coin up to and including the first head. What is \(\Pr ( X = k ) \), for \(k = 1,2,\ldots \)? Verify that \(\sum _{k = 1}^{\infty }{\Pr (X = k)} = 1\), as it should. (You may use the fact that \(\sum _{j = 0}^{\infty }a^{j} = \frac {1}{1 - a}\) for \(| a | < 1\)). (This is called a geometric random variable.)

13  More Coin Flipping ...

Suppose we have a coin with probability \(p\) of heads. Suppose we flip this coin \(n\) times independently. Let \(X\) be the number of heads that we observe. What is \(\Pr ( X = k ) \), for \(k = 0,\ldots n\)? Verify that \(\sum _{k = 0}^{n}{\Pr (X = k)} = 1\), as it should. (This is called a "binomial" random variable.)