Section 2.5 - Sum Expected Values

What is the expected value of the sum $X + Y$ given $X$ and $Y$ are (not necessarily independent) random variables?

From the definition of expected value, $$E(X + Y) = \sum_x\sum_y (x + y)\,p(X = x \wedge Y = y)$$ Evaluating this sum as given requires work proportional to $n^2$; can it be evaluated more efficiently? Because $X$ and $Y$ aren’t necessarily independent, the probability $p(X = x \wedge Y = y)$ can’t be simplified in the same way it was when computing the expected value of random-value products.^?That is, without independence $p(X = x \wedge Y = y)$ is not necessarily equal to $p_X(X=x)p_Y(Y=y)$. Are there some other tricks that can simplify evaluation?

Section 2.5 - Product Expected Value

Given independent random variables $X$ and $Y$,^?That is, knowning $X = x$ provides no help in determining what value $Y$ might be, and vice versa (knowing $Y = y$ says nothing about $X$’s value. what is the expected value of the product $XY$?

From the definition of expected vlaue, $$E(XY) = \sum_x\sum_y xy\,p(XY = xy)$$ Because $X$ and $Y$ are independent, the probability of their product is the product of their probabilities $$p(XY = xy) = p_X(X = x)\,p_Y(Y = y)$$ and the expected value becomes $$E(XY) = \sum_x\sum_y xy\,p_X(X = x)\,p_Y(Y = y)$$ where $p_X$ is the probability distribution for $X$ and similarly for $p_Y$.^?Independence includes not only values, but probability distributions too.

Evaluating the expected value as given takes work proportional to $n^2$. Can the sum be evaluated with less work?

Section 2.5 - Random Variables, Mean and the Expected Value

A random variable maps outcomes from a sample space to numbers, making the outcomes easier to manipulate. For example, there isn’t much to be done with outcomes from the coin-flip sample space { H, T }, but mapping outcomes to integers with the random variable X = { (H, 0), (T,1) } allows mathematical manipulations. The mapping used depends on what’s being done. X's previous definition might be useful when counting the number of tails, while the definition X = { (H, 1), (T, -1) } is more suited for keeping track of wins and losses.

Given a random variable X over a sample space, the probability that Xequals a particular value k is the sum of the probabilities of the outcomes that X maps to k: $$Pr(X = k) = \sum_{X(o) = k} Pr(o)$$ For example, let the random variable X map the outcome i of a single die roll to i. The probability that X is even is $$Pr(even(X)) = Pr(2)+ Pr(4) + Pr(6) = 1/6 + 1/6 + 1/6 = 1/2$$ Computing the mean (or average or expected value) of a random value is a common mathematical manipulation. A random variable’s mean is the sum of the values in the range, with each value weighted by its probability: $$\sum_{k\in range(X)} kPr(X = k)$$ The mean is often represented by $\mu$. To continue the die-roll example, X's mean is
$$\begin{eqnarray} & & 1Pr(X = 1) + 2Pr(X = 2) + \cdots + 6Pr(X = 6) \\ &=& 1\cdot1/6 + 2\cdot1/6 + \cdots + 6\cdot1/6 \\ &=& (1 + 2 + \cdots + 6)1/6 \\ &=& 21\cdot1/6 \\ &=& 3.5 \end{eqnarray}$$ A random variable’s mean is not necessarily a member of its range.

Exercise 2.2-16

How many distinct three-letter combinations (“words”) can you make from the letters of Mississippi?

Exercise 2.2-3

What is the probability of cutting two cards of the same rank from a well-shuffled deck?

Section 2.4 - The Binomial Distribution—Bernoulli Trials

A Bernoulli trial produces an outcome which satisfies a criterion with probability $p$, and so fails to satisfy the criterion with compliment probability $q = 1 - p$. What is the probability that $n$ successive, independent Bernoulli trials results in exactly $k$ satisfactory outcomes?

The compound outcome is an arrangement of $k$ satisfactory outcomes and $n - k$ unsatisfactory outcomes. Because the Bernoulli-trial outcomes are independent, the outcome probabilities are multiplied to get the combined-outcome probability, and because multiplication is commutative, any individual compound outcome has probability $p^kq^{n-k}$. There are $C(n, k)$ such compound outcomes, and the probability that $n$ successive, independent Bernoulli trials results in exactly $0 \leq k \leq n$ satisfactory outcomes when satisfactory outcomes have probability $p$ is $$b(k; n, p) = C(n, k)p^kq^{n - k}$$ The compound-outcome sample space is not uniform. Even if $p = 1/2$,^?that is, $p = q$. $C(n, k)$ varies with $k$; the variation becomes more complex when $p\neq q$.

Section 2.3 - Combinations

Given $n$ distinct items, there are $P(n, k)$ permutations of $0 \leq k \leq n$ items. Each permutation of $k$ items can be re-arranged $k!$ ways. If item order doesn’t matter, there are
$$\frac{P(n, k)}{k!} = \frac{n!}{k!(n-k)!} = C(n, k)$$
orderless permutations, or combinations. Sanity check: $C(n, n) = n!/(n!(n - n)!) = 1/0! = 1$.

Combinations are fun to play with. First, $C(n, k) = C(n, n - k)$.^?And so $C(n, 0) = C(n, n - 0) = 1$. Then
$$\begin{eqnarray} C(n, k + 1) & = & \frac{n!}{(k + 1)!(n - k - 1)!} \\ & = & \frac{n!(n - k)}{(k + 1)k!(n - k)(n - k - 1)!} \\ & = & \frac{n - k}{k + 1}C(n, k) \end{eqnarray}$$
$C(n, k + 1)$ is largest when $(n - k)/(k + 1)$ is closest to 1, which occurs when $k$ is closest to $(n - 1)/2$. Similarly
$$\begin{eqnarray} C(n + 1, k) & = & \frac{(n + 1)!}{k!(n + 1 - k)!} \\ & = & \frac{(n + 1)n!}{k!(n + 1 - k)(n - k)!} \\ & = & \frac{n + 1}{n + 1 - k}C(n, k) \end{eqnarray}$$