Skip to main content
Logo image

Applied Combinatorics

Section 10.4 Discrete Random Variables

Let \((S,P)\) be a probability space and let \(X:S\longrightarrow\reals\) be any function that maps the outcomes in \(S\) to real numbers (all values allowed, positive, negative and zero). We call 1  \(X\) a random variable. The quantity \(\sum_{x\in S} X(x)P(x)\text{,}\) denoted \(E(X)\text{,}\) is called the expectation (also called the mean or expected value) of the random variable \(X\text{.}\) As the suggestive name reflects, this is what one should expect to be the average behavior of the result of repeated Bernoulli trials.
Note that since we are dealing only with probability spaces \((S,P)\) where \(S\) is a finite set, the range of the probability measure \(P\) is actually a finite set. Accordingly, we can rewrite the formula for \(E(X)\) as \(\sum_y y\cdot \prob(X(x)=y)\text{,}\) where the summation extends over a finite range of values for \(y\text{.}\)

Example 10.15.

For the spinner shown in Figure 10.1, let \(X(i)=i^2\) where \(i\) is the number of the region. Then
\begin{equation*} E(X)=\sum_{i\in S} i^2P(i)=1^2\frac{1}{8}+2^2\frac{2}{8}+3^2\frac{1}{8}+ 4^2\frac{1}{8}+5^2\frac{3}{8}=\frac{109}{8}. \end{equation*}
Note that \(109/8=13.625\text{.}\) The significance of this quantity is captured in the following statement. If we record the result from the spinner \(n\) times in succession as \((i_1,i_2,\dots,i_n)\) and Xing receives a prize worth \(i_j^2\) for each \(j=1,2,\dots,n)\text{,}\) then Xing should “expect” to receive a total prize worth \(109n/8=13.625n\text{.}\) Bob asks how this statement can possibly be correct, since \(13.625n\) may not even be an integer, and any prize Xing receives will have integral value. Carlos goes on to explain that the concept of expected value provides a formal definition for what is meant by a fair game. If Xing pays \(13.625\) cents to play the game and is then paid \(i^2\) pennies where \(i\) is the number of the region where the spinner stops, then the game is fair. If he pays less, he has an unfair advantage, and if he pays more, the game is biased against him. Bob says “How can Xing pay \(13.625\) pennies?” Brushing aside Bob’s question, Carlos says that one can prove that for every \(\epsilon >0\text{,}\) there is some \(n_0\) (which depends on \(\epsilon\)) so that if \(n>n_0\text{,}\) then the probability that Xing’s total winnings minus \(13.625n\text{,}\) divided by \(n\) is within \(\epsilon\) of \(13.625\) is at least \(1-\epsilon\text{.}\) Carlos turns to Dave and explains politely that this statement gives a precise meaning of what is meant by “close” and “large”.

Example 10.16.

For Alice’s game from the start of the chapter, \(S=\{0,1,2,3,4,5\}\text{,}\) we could take \(X\) to be the function defined by \(X(d)= 2-d\text{.}\) Then \(X(d)\) records the amount that Bob wins when the difference is \(d\) (a negative win for Bob is just a win for Alice in the same amount). We calculate the expectation of \(X\) as follows:
\begin{equation*} E(X)=\sum_{d=0}^{5}X(d)p(d)= -2\frac{1}{6} -1\frac{10}{36}+0 \frac{8}{36}+1\frac{6}{36}+2\frac{4}{36}+3{2}{36}=\frac{-2}{36}. \end{equation*}
Note that \(-2/36=-.055555\dots\text{.}\) So if points were dollars, each time the game is played, Bob should expect to lose slightly more than a nickel. Needless to say, Alice likes to play this game and the more times Bob can be tricked into playing, the more she likes it. On the other hand, by this time in the chapter, Bob should be getting the message and telling Alice to go suck a lemon.

Subsection 10.4.1 The Linearity of Expectation

The following fundamental property of expectation is an immediate consequence of the definition, but we state it formally because it is so important to discussions to follow.

Subsection 10.4.2 Implications for Bernoulli Trials

Example 10.18.

Consider a series of \(n\) Bernoulli trials with \(p\text{,}\) the probability of success, and let \(X\) count the number of successes. Then, we claim that
\begin{equation*} E(X)=\sum_{i=0}^n i\binom{n}{i}p^i(1-p)^{n-i}=np \end{equation*}
To see this, consider the function \(f(x)=[px+(1-p)]^n\text{.}\) Taking the derivative by the chain rule, we find that \(f'(x)=np[px+(1-p)]^{n-1}\text{.}\) Now when \(x=1\text{,}\) the derivative has value \(np\text{.}\)
On the other hand, we can use the binomial theorem to expand the function \(f\text{.}\)
\begin{equation*} f(x)=\sum_{i=0}^n \binom{n}{i}x^ip^i(1-p)^{n-i} \end{equation*}
It follows that
\begin{equation*} f'(x)=\sum_{i=0}^n i \binom{n}{i}x^{i-}p^i(1-p)^{n-i} \end{equation*}
And now the claim follows by again setting \(x=1\text{.}\) Who says calculus isn’t useful!

Example 10.19.

Many states have lotteries to finance college scholarships or other public enterprises judged to have value to the public at large. Although far from a scientific investigation, it seems on the basis of our investigation that many of the games have an expected value of approximately fifty cents when one dollar is invested. So the games are far from fair, and no one should play them unless they have an intrinsic desire to support the various causes for which the lottery profits are targeted.
By contrast, various games of chance played in gambling centers have an expected return of slightly less than ninety cents for every dollar wagered. In this setting, we can only say that one has to place a dollar value on the enjoyment derived from the casino environment. From a mathematical standpoint, you are going to lose. That’s how they get the money to build those exotic buildings.
For historical reasons, capital letters, like \(X\) and \(Y\) are used to denote random variables. They are just functions, so letters like \(f\text{,}\) \(g\) and \(h\) might more seem more natural—but maybe not.