13 Conditional Random Variables, Multiple Random Variables (Joint PMF, Marginal PMF), Independence of Random Variables, Sum of Independent Random Variables, Wald's Identity, Variance and Concentration

Lecture from: 01.04.2025 | Video: Homelab

Recap: Random Variables and Their Properties

As a quick reminder:

A random variable $X$ is a function $X:\Omega \to \mathbb{R}$ mapping outcomes from a sample space $\Omega$ to real numbers.

The PMF (Probability Mass Function, or “Dichtefunktion”) $f_X(x)=Pr[X=x]$ tells us the probability that $X$ takes on a specific value $x$.

The CDF (Cumulative Distribution Function, or “Verteilungsfunktion”) $F_X(x)=Pr[X\le x]$ gives the probability that $X$ is less than or equal to $x$.

The Expected Value $E[X]={\sum }_{x\in W_X}x\cdot Pr[X=x]={\sum }_{\omega \in \Omega }X(\omega )\cdot Pr[\omega ]$ is the average value $X$ takes.

Conditional Random Variables

Sometimes, we are interested in the behavior of a random variable $X$ given that a certain event $A$ (with $Pr[A]>0$) has occurred. This leads to the concept of a conditional random variable, denoted $X|A$.

The function $X|A$ is essentially the same function as $X$, but its domain is restricted to the outcomes $\omega \in A$. We are only looking at the values $X(\omega )$ for those outcomes where $A$ happened.

Conditional PMF, CDF, and Expectation

We can define the PMF, CDF, and expectation for this conditional random variable:

• Conditional PMF: $f_{X|A}(x)=Pr[X=x\mid A]$ This is the probability that the random variable $X$ takes the value $x$, given that event $A$ has occurred.

• Conditional CDF: $F_{X|A}(x)=Pr[X\le x\mid A]$ This is the probability that $X$ is less than or equal to $x$, given that event $A$ has occurred.

• Conditional Expectation: $E[X\mid A]={\sum }_{x\in W_X}x\cdot Pr[X=x\mid A]$ Using the definition of conditional probability, $Pr[X=x\mid A]=\frac{Pr[(X=x)\cap A]}{Pr[A]}$. So, $E[X\mid A]={\sum }_{x\in W_X}x\cdot \frac{Pr[\{\omega \in A\mid X(\omega )=x\}]}{Pr[A]}=\frac{1}{Pr[A]}{\sum }_{\omega \in A}X(\omega )\cdot Pr[\omega ]$ (assuming elementary outcomes for simplicity in the last sum if it’s a Laplace space, or more generally, summing $X(\omega )Pr[\omega ]$ over $\omega \in A$).

A random variable $X$ is said to be independent of an event A if its conditional distribution given $A$ is the same as its unconditional distribution, i.e., $f_{X|A}(x)=f_X(x)$ for all $x$. This means knowing $A$ occurred doesn’t change how $X$ behaves.

Example: Sum of Two Dice Rolls Conditioned on Events

Let $X_1$ be the outcome of the first die roll, $X_2$ be the outcome of the second.

• $E[X_1]=E[X_2]=3.5$.

Let $X=X_1+X_2$ be the sum of the two dice.

• $E[X]=E[X_1]+E[X_2]=7$.

Consider two events:

• $A:=$ ”$X_2$ is even” (i.e., $X_2\in \{2,4,6\}$). $Pr[A]=1/2$.
• $B:=$ ”$X$ is even” (i.e., $X_1+X_2\in \{2,4,6,8,10,12\}$). $Pr[B]=1/2$.

Expectation of the sum given the dice 2 is even

Let’s look at $E[X\mid A]=E[X_1+X_2\mid A]$.

By linearity of conditional expectation (which holds just like regular expectation):

$E[X\mid A]=E[X_1\mid A]+E[X_2\mid A]$.

• $X_1$ (first die roll) is independent of $A$ (second die roll is even). So, $E[X_1\mid A]=E[X_1]=3.5$.
• $E[X_2\mid A]$: We are given $X_2$ is even. The possible values for $X_2$ are $2,4,6$, each with probability $1/3$ (within the conditioned space A). So, $E[X_2\mid A]=2(1/3)+4(1/3)+6(1/3)=(2+4+6)/3=12/3=4$. So, $E[X\mid A]=3.5+4=7.5$.

Knowing the second die is even increases the expected sum, which makes sense.

Expectation of the sum given the sum is even

Now, $E[X\mid B]=E[X_1+X_2\mid B]$. $E[X\mid B]=E[X_1\mid B]+E[X_2\mid B]$.

It turns out that $X_1$ is independent of $B$ (the sum $X_1+X_2$ being even doesn’t change probabilities for $X_1$). For any $i\in \{\mathrm{1..6}\}$, $Pr[B|X_1=i]=1/2=Pr[B]$. So $E[X_1|B]=E[X_1]=3.5$.

Similarly, $E[X_2|B]=E[X_2]=3.5$. Thus, $E[X\mid B]=3.5+3.5=7$.

Multiple Random Variables

Often, we work with several random variables simultaneously, defined on the same sample space.

For example, if we flip $n$ coins: $X_i=$ Indicator for Head on $i$-th flip. $X=X_1+X_2+\dots +X_n=$ Total number of Heads.

Here, $X,X_1,\dots ,X_n$ are all random variables on the space of $n$ coin flips.

Another example:

1. Roll a die: $X:=$ outcome of the die.
2. Flip that many coins: $Y:=$ number of Heads obtained. Here $X$ and $Y$ are two random variables related in a sequential experiment.

Joint PMF (Gemeinsame Dichte)

When we have two discrete random variables $X$ and $Y$, their joint probability mass function $f_{X,Y}(x,y)$ gives the probability that $X$ takes value $x$ AND $Y$ takes value $y$: $f_{X,Y}(x,y):=Pr[X=x,Y=y]$ (short for $Pr[(X=x)\cap (Y=y)]$)

Marginal PMF (Randdichte)

From the joint PMF, we can recover the individual PMF of $X$ (called the marginal PMF of $X$) by summing over all possible values of $Y$: $f_X(x)=Pr[X=x]={\sum }_{y\in W_Y}Pr[X=x,Y=y]={\sum }_{y\in W_Y}{f}_{X,Y}(x,y)$

This is by the law of total probability: the event $(X=x)$ is partitioned by the events $(X=x,Y=y)$ for all possible $y$. Similarly for $f_Y(y)={\sum }_{x\in W_X}{f}_{X,Y}(x,y)$.

Example: Die roll (number $X$) then $X$ coin flips (number of heads $Y$)

$X\in \{1,\dots ,6\}$, $Y\in \{0,\dots ,X\}$.

What is $Pr[X=x,Y=y]$?

$Pr[X=x,Y=y]=Pr[Y=y\mid X=x]\cdot Pr[X=x]$ $Pr[X=x]=1/6$ for $x\in \{1,\dots ,6\}$.

Given $X=x$ (we flip $x$ coins), $Y$ (number of heads) follows $\text{Bin}(x,1/2)$. So, $Pr[Y=y\mid X=x]=\left(\genfrac{}{}{0ex}{}{x}{y}\right)(1/2{)}^x$.

Thus, $f_{X,Y}(x,y)=\{\begin{array}{ll}\frac{1}{6}\left(\genfrac{}{}{0ex}{}{x}{y}\right)\frac{1}{2^x}& \text{if }x\in \{\mathrm{1..6}\},y\in \{\mathrm{0..}x\}\\ 0& \text{otherwise}\end{array}$

Let’s calculate $Pr[Y=3]$ (marginal probability for $Y$): $Pr[Y=3]={\sum }_{x=1}^{6}Pr[X=x,Y=3]$

For $x=1,2$, $Pr[X=x,Y=3]=0$ since $y\le x$.

$Pr[Y=3]=Pr[X=3,Y=3]+Pr[X=4,Y=3]+Pr[X=5,Y=3]+Pr[X=6,Y=3]$ $=\frac{1}{6}\left(\genfrac{}{}{0ex}{}{3}{3}\right)\frac{1}{2^3}+\frac{1}{6}\left(\genfrac{}{}{0ex}{}{4}{3}\right)\frac{1}{2^4}+\frac{1}{6}\left(\genfrac{}{}{0ex}{}{5}{3}\right)\frac{1}{2^5}+\frac{1}{6}\left(\genfrac{}{}{0ex}{}{6}{3}\right)\frac{1}{2^6}$ $=\frac{1}{6}\left(1\cdot \frac{1}{8}+4\cdot \frac{1}{16}+10\cdot \frac{1}{32}+20\cdot \frac{1}{64}\right)$ $=\frac{1}{6}\left(\frac{1}{8}+\frac{4}{16}+\frac{10}{32}+\frac{20}{64}\right)=\frac{1}{6}\left(\frac{8+16+20+20}{64}\right)=\frac{1}{6}\frac{64}{64}=\frac{1}{6}$.

It seems $Pr[Y=3]$ is $1/6$.

Independence of Random Variables

Definition of Independence (Version 1 - using events)

TLDR: $Pr[A=a\wedge B=b\wedge \dots ]=Pr[A=a]\ast Pr[B=b]\ast \dots$

Random variables $X_1,\dots ,X_n$ are said to be independent if for all choices of values $x_1,\dots ,x_n$ (where $x_i$ is in the range of $X_i$), the events "$X_1=x_1$", "$X_2=x_2$", …, "$X_n=x_n$" are mutually independent events.

This means: $Pr[X_1=x_1,X_2=x_2,\dots ,X_n=x_n]=Pr[X_1=x_1]\cdot Pr[X_2=x_2]\cdot \dots \cdot Pr[X_n=x_n]$ And this must hold not just for the full set of $n$ variables, but for every subset of these variables as well (to ensure mutual independence of the events).

Many of these equations are redundant. For example, if $X_3$ only takes values $\{0,1\}$:

If we know:

1. $Pr[X_1=x_1,X_2=x_2,X_3=0]=Pr[X_1=x_1]Pr[X_2=x_2]Pr[X_3=0]$
2. $Pr[X_1=x_1,X_2=x_2,X_3=1]=Pr[X_1=x_1]Pr[X_2=x_2]Pr[X_3=1]$

Then $Pr[X_1=x_1,X_2=x_2]$ can be found by summing these two (by law of total probability over $X_3$): $Pr[X_1=x_1,X_2=x_2]=Pr[X_1=x_1]Pr[X_2=x_2](Pr[X_3=0]+Pr[X_3=1])$

Since $Pr[X_3=0]+Pr[X_3=1]=1$, we get $Pr[X_1=x_1,X_2=x_2]=Pr[X_1=x_1]Pr[X_2=x_2]$. This means the pairwise independence of $X_1,X_2$ follows from the conditions involving $X_3$.

Definition of Independence (Version 2 - using PMFs)

TLDR: Joint PMF can be decomposed into product of marginal PMFs.

A more concise definition: Random variables $X_1,\dots ,X_n$ are independent if their joint PMF is the product of their marginal PMFs: $f_{X_1,\dots ,X_n}(x_1,\dots ,x_n)=f_{X_1}(x_1)\cdot f_{X_2}(x_2)\cdot \dots \cdot f_{X_n}(x_n)$ for all $(x_1,\dots ,x_n)$ in the combined range $W_{X_1}\times \dots \times W_{X_n}$.

This single equation covering all combinations of values implies the subset conditions automatically.

Trick for Two Indicator Variables

For two indicator variables $X$ and $Y$: $X$ and $Y$ are independent $⟺f_{X,Y}(1,1)=f_X(1)\cdot f_Y(1)$.

This is because $f_X(1)=Pr[X=1]$, $f_Y(1)=Pr[Y=1]$, and $f_{X,Y}(1,1)=Pr[X=1,Y=1]$.

If this holds, all other combinations like $Pr[X=1,Y=0]$ also work out. For instance, $Pr[X=1,Y=0]=Pr[X=1]-Pr[X=1,Y=1]$ $=Pr[X=1]-Pr[X=1]Pr[Y=1]$ (using the condition) $=Pr[X=1](1-Pr[Y=1])=Pr[X=1]Pr[Y=0]$.

Caution: This shortcut does not generally apply for three or more indicator variables.

Example of Independence/Dependence of Indicator Variables

1. $\Omega =\{1,2,3,6\}$, $Pr[\omega ]=1/4$ for each $\omega$. $X(\omega )=1$ if $\omega$ is divisible by 2, else 0. $W_X=\{0,1\}$. $X=1$ for $\omega \in \{2,6\}$. $Pr[X=1]=2/4=1/2$. So $f_X(1)=1/2,f_X(0)=1/2$.

   $Y(\omega )=1$ if $\omega$ is divisible by 3, else 0. $W_Y=\{0,1\}$. $Y=1$ for $\omega \in \{3,6\}$. $Pr[Y=1]=2/4=1/2$. So $f_Y(1)=1/2,f_Y(0)=1/2$.

   Event $(X=1,Y=1)$ means $\omega$ is divisible by 2 AND 3, so divisible by 6. This is only $\omega =6$. $f_{X,Y}(1,1)=Pr[X=1,Y=1]=Pr[\omega =6]=1/4$. Check: $f_X(1)\cdot f_Y(1)=(1/2)\cdot (1/2)=1/4$. Since $f_{X,Y}(1,1)=f_X(1)f_Y(1)$, $X$ and $Y$ are independent.

2. $\Omega =\{2,3\}$, $Pr[\omega ]=1/2$ for each $\omega$. $X(\omega )=1$ if $\omega$ is divisible by 2, else 0. $X=1$ for $\omega =2$, $X=0$ for $\omega =3$. $Pr[X=1]=1/2$. So $f_X(1)=1/2,f_X(0)=1/2$.

   $Y(\omega )=1$ if $\omega$ is divisible by 3, else 0. $Y=1$ for $\omega =3$, $Y=0$ for $\omega =2$. $Pr[Y=1]=1/2$. So $f_Y(1)=1/2,f_Y(0)=1/2$.

   Event $(X=1,Y=1)$ means $\omega$ divisible by 2 AND 3. No such $\omega$ in $\Omega =\{2,3\}$. $f_{X,Y}(1,1)=Pr[X=1,Y=1]=0$. Check: $f_X(1)\cdot f_Y(1)=(1/2)\cdot (1/2)=1/4$. Since $0\ne 1/4$, $X$ and $Y$ are not independent.

Properties of Independent Random Variables

• If $X_1,\dots ,X_n$ are independent random variables, then for any choice of subsets $S_1,\dots ,S_n\subseteq \mathbb{R}$ (where $S_i$ are sets of values $X_i$ can take): $Pr[X_1\in S_1,\dots ,X_n\in S_n]=Pr[X_1\in S_1]\cdot \dots \cdot Pr[X_n\in S_n]$. This is a more general statement of independence. (This is “Lemma 2.53”).

• Subsets of independent variables are independent: If $X_1,\dots ,X_n$ are independent, then any subcollection, e.g., $X_{i_1},\dots ,X_{i_k}$, is also independent. (This is “Korollar 2.53”).

• Functions of independent variables: If $X_1,\dots ,X_n$ are independent random variables, and $g_1,\dots ,g_n$ are real-valued functions ($g_i:\mathbb{R}\to \mathbb{R}$), then the random variables $Y_1=g_1(X_1),\dots ,Y_n=g_n(X_n)$ are also independent. (This is “Satz 2.52”). For example, if $X,Y$ are independent, then $X^2$ and $Y^3$ are independent.

Sum of Independent Random Variables

If $X$ and $Y$ are two independent discrete random variables, and $Z=X+Y$, what is the PMF of $Z$, $f_Z(z)$?

The event $(Z=z)$ occurs if $(X=x)$ and $(Y=z-x)$ for some $x$. $f_Z(z)=Pr[Z=z]={\sum }_{x\in W_X}Pr[X=x,Y=z-x]$

Since $X$ and $Y$ are independent: $f_Z(z)={\sum }_{x\in W_X}Pr[X=x]\cdot Pr[Y=z-x]={\sum }_{x\in W_X}{f}_X(x)\cdot f_Y(z-x)$.

This is called the convolution of the PMFs of $X$ and $Y$.

Sum of Multiple Independent Random Variables

If $A$, $B$, and $C$ are independent discrete random variables, and you define $Z=A+B+C,$ then the PMF of $Z$, denoted $f_Z(z)$, is the convolution of the PMFs of $A$, $B$, and $C$.

Step-by-step:

1. First, define the PMFs:

   • $f_A(a)=\mathrm{Pr}[A=a]$
   • $f_B(b)=\mathrm{Pr}[B=b]$
   • $f_C(c)=\mathrm{Pr}[C=c]$

2. The PMF of $Z=A+B+C$ is:

   $$f_Z(z)=\sum _{a\in W_A}\sum _{b\in W_B}{f}_A(a)\cdot f_B(b)\cdot f_C(z-a-b)$$

   where $W_A,W_B$ are the supports of $A$ and $B$ respectively.

This is a double convolution.

Consequences for Common Distributions

This convolution formula leads to some nice “closure” properties for sums of independent random variables from certain families:

1. Sum of independent Poissons: If $X_1\sim \text{Po}({\lambda }_1)$ and $X_2\sim \text{Po}({\lambda }_2)$ are independent, then $X_1+X_2\sim \text{Po}({\lambda }_1+{\lambda }_2)$. The sum of independent Poisson variables is also Poisson, with parameter being the sum of parameters.

2. Sum of independent Binomials (with same p): If $X_1\sim \text{Bin}(n,p)$ and $X_2\sim \text{Bin}(m,p)$ are independent (note: same $p$), then $X_1+X_2\sim \text{Bin}(n+m,p)$. This makes intuitive sense: $X_1$ is sum of $n$ Bernoulli(p) trials, $X_2$ is sum of $m$ Bernoulli(p) trials. Their sum is like $n+m$ Bernoulli(p) trials.

Wald’s Identity (Waldsche Identität)

Wald’s Identity relates the expected value of a sum of a random number of independent and identically distributed (i.i.d.) random variables.

Setup

• Let $X_1,X_2,\dots$ be a sequence of i.i.d. random variables, each with mean $E[X_i]=\mu$.
• Let $N$ be a non-negative integer-valued random variable (a “stopping time”) that is independent of the sequence $X_i$. The value of $N$ tells us how many $X_i$‘s to sum.
• Let $Z={\sum }_{i=1}^N{X}_i$. If $N=0$, then $Z=0$.

Intuition for Setup: Imagine you’re at a casino playing a game.

• $X_i$: The amount you win or lose on the $i$-th play of the game. These are i.i.d. (each play is similar, and outcomes are independent). $E[X_i]=\mu$ is your average winning/loss per play.
• $N$: The number of times you decide to play. This number $N$ could itself be random (e.g., you play until you win a certain amount, or until you’ve played 5 times, or until you get bored).
• Crucial condition: Your decision on how many games to play ($N$) must be made independently of the actual outcomes $X_i$ of those games. For example, $N$ cannot be “I’ll stop playing as soon as I see a big win $X_i$“. If $N$ depends on the $X_i$ values, Wald’s Identity (in this simple form) doesn’t apply. (The concept of a “stopping time” is more general and can relax this independence, but for this version, independence of $N$ and the sequence $X_i$ is key).
• $Z$: Your total winnings/losses after playing $N$ games.

Wald’s Identity states

$E[Z]=E[N]\cdot E[X_1]$ (or $E[N]\cdot \mu$)

Example 1: Die Roll and Coin Flips (revisited)

1. Roll a fair die. Let $N$ be the outcome. $N\in \{1,\dots ,6\}$. $E[N]=3.5$.
2. Flip a fair coin $N$ times. Let $X_i$ be indicator for Head on $i$-th flip. $E[X_i]=1/2$.
3. Let $Z={\sum }_{i=1}^N{X}_i$ be the total number of Heads.

Here, $N$ (die roll) is independent of the outcomes of the $X_i$‘s (coin flips).

By Wald’s Identity: $E[Z]=E[N]\cdot E[X_1]=3.5\cdot (1/2)=7/4=1.75$.

Note: We use $X_1$ in the equation as all $X_i$ experiments are i.i.d and it’s expected value is the same…

Example 2: Two Phases of Coin Flips

1. Phase 1: Flip a fair coin until the first Head appears. Let $N$ be the number of flips in this phase. $N\sim \text{Geo}(1/2)$. So $E[N]=1/(1/2)=2$.
2. Phase 2: Flip the coin $N$ more times. Let $X_i$ be the indicator for Head on the $i$-th flip in this second phase. $E[X_i]=1/2$. Let $Y={\sum }_{i=1}^N{X}_i$ be the number of Heads in Phase 2.

The number of flips in Phase 2 ($N$) is determined by Phase 1, and is independent of the outcomes ($X_i$) within Phase 2.

By Wald’s Identity, $E[Y]=E[N]\cdot E[X_1]=2\cdot (1/2)=1$.

So, we expect 1 Head in Phase 2.

Let $Z$ be the total number of Heads overall (Phase 1 + Phase 2). Phase 1 contributes exactly 1 Head (the one that stopped Phase 1). So, $Z=1+Y$. $E[Z]=E[1+Y]=1+E[Y]=1+1=2$.

Variance and Concentration

The expected value $E[X]$ tells us the “center” or average of a random variable. But it doesn’t tell us how spread out the values of $X$ are.

We’d like to say that if we know $E[X]$, then $X$ is likely to be “close” to $E[X]$. That is, $Pr[|X-E[X]|\text{ is "large"}]\text{ is "small"}$.

However, this isn’t always true just based on $E[X]$.

Example:

• $Pr[X=-10^{10}]=1/2$ and $Pr[X=10^{10}]=1/2$.
• Then $E[X]=(-10^{10})(1/2)+(10^{10})(1/2)=0$.

But $X$ is never close to its expectation 0! It’s always $10^{10}$ away.

We need a measure of spread or deviation.

Variance

The variance of a random variable $X$, denoted $Var[X]$ or ${\sigma }^2\_X$, measures the expected squared deviation of $X$ from its mean $\mu =E[X]$.

Since $(X-\mu {)}^2\ge 0$, $Var[X]\ge 0$. A small variance means $X$ tends to be close to its mean. A large variance means $X$ can be far from its mean.

Note: One could also measure spread using the average absolute deviation, or even higher powers like the 4th or 6th. But squaring turns out to be mathematically convenient, it leads to cleaner algebra and works well with many powerful tools later on.

Alternative Formula for Variance

Using linearity of expectation:

Since $E[X]$ is a constant:

This is often easier to compute: calculate $E[X]$ and $E[X^2]$, then use this formula.

The standard deviation $\sigma \_X=\sqrt{Var[X]}$ is also commonly used. It has the same units as $X$.

Properties of Variance

For any random variable $X$ and real constants $a,b\in \mathbb{R}$:

This tells us two important things:

• Shifting a random variable by a constant ($b$) doesn’t affect its variance.
• Scaling a random variable by a factor ($a$) multiplies the variance by $a^2$.

Proof Sketch

Let $\mu =E[X]$. Then:

So, the constant shift $b$ cancels out—it doesn’t affect how far values are from the mean, only where that mean is located.

The key idea: shifting $X$ moves everything together, so the “spread” stays the same. But scaling stretches or compresses the deviations, so it changes the variance.

Next time, we’ll see how variance lets us quantify how tightly a random variable clusters around its mean, using tools like Markov’s and Chebyshev’s inequalities.

Continue here: 14 Rules for Moments (Expectation, Variance), Estimating Probabilities (Markov, Chebyshev), Chernoff Bounds