Skip to main content

MA 415G course notes

Benjamin Braun

Section 4.4 Expected Values: Binary Strings and Subsets

We next apply the tools we have developed to investigate expected values of random variables defined on subsets of a finite set, which as we have seen is equivalent to binary strings.
🔗

Proof.

Note that if \(X_i\) is the random variable defined by
\begin{equation*} X_i(x)=\begin{cases}1 \amp \text{if the }i\text{-th entry of }x\text{ is }1 \\ 0 \amp \text{otherwise} \end{cases} \, , \end{equation*}
then we have that
\begin{equation*} X=\sum_{i=1}^n X_i \, . \end{equation*}
Observe that
\begin{equation*} E[X_i]= \sum_{x\in \Bin_n} P(x)X_i(x) = \sum_{x\in \Bin_n: x_i=1} \frac{1}{2^n}\cdot 1 = \frac{2^{n-1}}{2^n} = \frac{1}{2} \, . \end{equation*}
Equivalently, since \(X_i\) is an indicator random variable for the event that the \(i\)-th entry of \(x\) is \(1\text{,}\) and since half of all binary strings have a \(1\) in the \(i\)-th position, we have that \(P(X_i=1)=1/2\text{,}\) so
\begin{equation*} E[X_i]=1\cdot P(X_i=1)+0\cdot P(X_i=0)=1/2\text{.} \end{equation*}
🔗
Using linearity of expectation, we have that
\begin{align*} E[X] \amp = E\left[\sum_{i=1}^n X_i\right] \\ \amp = \sum_{i=1}^n E[X_i] \\ \amp = \sum_{i=1}^n \frac{1}{2} \\ \amp = \frac{n}{2} \, . \end{align*}
🔗
🔗
Using our bijection between binary strings and subsets of \([n]\text{,}\) we can interpret this as saying that if we choose a subset of an \(n\)-element set uniformly at random, we expect the subset to have size \(n/2\text{.}\)
🔗

Checkpoint 4.4.2.

Discuss the proof above. Does it make sense? Why or why not?
🔗
🔗
Note that the uniform distribution on binary strings of length \(n\) is a special case of the binomial distribution where \(p=1/2\text{.}\) Thus, we can generalize the previous result by considering the binomial distribution with arbitrary parameter \(p\in(0,1)\text{.}\)
🔗

Proof.

Let \(X_i\) be the same random variable as in the previous proof. Using linearity of expectation directly from the definition, we have that
\begin{align*} E[X] \amp = E\left[\sum_{i=1}^n X_i\right] \\ \amp = \sum_{i=1}^n E[X_i] \\ \amp = \sum_{i=1}^n \sum_{x\in \Bin_n} P(x)X_i(x) \\ \amp = \sum_{i=1}^n \sum_{x\in \Bin_n: x_i=1} p^{|x|}(1-p)^{n-|x|} \\ \amp = \sum_{i=1}^n \left( p \sum_{y\in \Bin_{n-1}} p^{|y|}(1-p)^{n-1-|y|}\right) \\ \amp = \sum_{i=1}^n \left( p \cdot (p+(1-p))^{n-1}\right) \\ \amp = p n \, . \end{align*}
We can obtain the same result in a simpler manner when we recognize that \(X_i\) is an indicator random variable for the event that the \(i\)-th entry of \(x\) is \(1\text{,}\) and since the probability that the \(i\)-th entry of \(x\) is \(1\) is \(p\text{,}\) we have that
\begin{equation*} E[X_i]=1\cdot P(X_i=1)+0\cdot P(X_i=0)=p\text{.} \end{equation*}
This avoids the need to sum over all binary strings of length \(n-1\) in the above calculation.
🔗
🔗

Checkpoint 4.4.4.

Discuss the proof above. Does it make sense? Why or why not?
🔗
🔗
In these notes, we will frequently use the definition of expected value to compute expected values directly. However, it is important to note that the use of probabilities for indicator random variables and linearity of expectation can often simplify calculations significantly, as we have seen in the proofs above.
🔗
There are many other interesting random variables that can be defined on binary strings and subsets. Next we will look at one such example.
🔗

Checkpoint 4.4.5.

Let \(X\) be the random variable on \(2^{[n]}\) with the uniform distribution that counts the number of pairs \(\{i,i+1\}\) that are contained in a set. In other words, for \(S\subseteq [n]\text{,}\) let
\begin{equation*} X(S)=|\{i\in [n-1] : \{i,i+1\}\subseteq S\}| \, . \end{equation*}
Here is a plot (note the different scales on the axes!!!) where for each \(n\) from \(1\) to \(39\text{,}\) we randomly select \(1000\) subsets of \([n]\) and compute the average value of \(X\) on those subsets. Do you have a guess for what \(E[X]\) might be? What is your reasoning?
🔗
Plot of experimental expected value of X versus n.
Figure 4.4.6. Plot of experimental expected value of \(X\) versus \(n\text{.}\)
🔗
🔗

Proof.

Let \(X_i\) be the random variable defined by
\begin{equation*} X_i(S)=\begin{cases}1 \amp \text{if }\{i,i+1\}\subseteq S \\ 0 \amp \text{otherwise} \end{cases} \, . \end{equation*}
Using linearity of expectation, we have that
\begin{align*} E[X] \amp = E\left[\sum_{i=1}^{n-1} X_i\right] \\ \amp = \sum_{i=1}^{n-1} E[X_i] \\ \amp = \sum_{i=1}^{n-1} \sum_{S\subseteq [n]} P(S)X_i(S) \\ \amp = \sum_{i=1}^{n-1} \sum_{S\subseteq [n]: \{i,i+1\}\subseteq S} \frac{1}{2^n}\cdot 1 \\ \amp = \sum_{i=1}^{n-1} \frac{2^{n-2}}{2^n} \\ \amp = \frac{n-1}{4} \, . \end{align*}
🔗
🔗

Checkpoint 4.4.8.

Discuss the proof above. Does it make sense? Why or why not?
🔗
🔗

Checkpoint 4.4.9.

What is the interpretation of the theorem above in terms of binary strings?
🔗
🔗

Checkpoint 4.4.10.

What does the theorem above mean to you? In other words, how would you explain it to someone who is not familiar with expected values or random variables?
🔗
🔗
🔗
PrevTopNext