More Random Variables and Expectation

Videos

Bernoulli and Binomial Distributions (8:40)
Indicator Random Variables (8:25)
Conditional Expectation (7:35)
Variance of a Random Variable (7:20)

Reading

(Again): Connecting Discrete Mathematics and Computer Science by David Liben-Nowell, Chapter 10, pages 54-71

Warmup

Problem 1

Suppose that I sample a random variable \(N\) from a binomial distribution with number of trials \(n\) and success probability \(p\). Then, I flip \(N\) coins, each of which has probability \(q\) of coming up heads. Use the law of total expectation to compute the expected number of heads from this process.

Hint: The expectation of a random variable \(Y\) with binomial distribution and parameters \(m\) (number of trials) and \(r\) (success probability) is \(\mathbb{E}[Y] = mr\).

Note: The law of total expectation says that the expectation of a random variable \(X\) can be computed from a series of conditional expectations involving another random variable \(Y\) using the formula:

\[ \begin{aligned} \mathbb{E}[X] &= \sum_{y \in \mathcal{Y}} \mathbb{E}[X|Y = y]\mathbb{P}(Y = y)\;. \end{aligned} \]

Problem 2

A permutation of the integers \(\{1, 2, \ldots, n\}\) is a reordering of these integers. For example, \((3, 1, 2)\) is a permutation of \(\{1, 2, 3\}\). An inversion in a permutation is a pair of integers \(i < j\) such that \(i\) appears after \(j\) in the permutation. For example, the permutation \((3, 1, 2)\) has two inversions: \((3, 1)\) and \((3, 2)\).

If \((i, j)\) is an inversion in a permutation, we say that \(i\) and \(j\) are inverted.

Part A

Suppose that we choose a permutation uniformly at random from the set of all possible permutations on \(\{1,2,3\}\). What is the probability that the elements \(2\) and \(3\) are inverted in this permutation?

Part B

Suppose that we choose a permutation uniformly at random from the set of all possible permutations on \(\{1,2,3\}\). What is the expected number of inversions in this permutation?

Part C

Suppose that we choose a permutation uniformly at random from the set of all possible permutations on \(\{1,2,\ldots,n-1,n\}\). What is the expected number of inversions in this permutation?

Problem 3

Write a proof of the following theorem:

If \(X\) and \(Y\) are independent random variables, then \(\text{var}(X + Y) = \text{var}(X) + \text{var}(Y)\).