12 Randomized QuickSort, Indicator Variables, Common Probability Distributions, Coupon Collector

Lecture from: 27.03.2025 | Video: Homelab

Recap: Random Variables and Expectation

Just to quickly refresh:

A random variable $X$ is a function $X:\Omega \to \mathbb{R}$ that assigns a numerical value to each outcome in our sample space.

The expected value $E[X]$ is defined as $E[X]:={\sum }_{x\in W_X}x\cdot Pr[X=x]$ or, more fundamentally, $E[X]={\sum }_{\omega \in \Omega }X(\omega )\cdot Pr[\omega ]$.

The superstar property is linearity of expectation: For random variables $X_1,\dots ,X_n$ and constants $a_1,\dots ,a_n,b$: $E[a_1{X}_1+\dots +a_n{X}_n+b]=a_{1}E[X_1]+\dots +a_{n}E[X_n]+b$.

This holds regardless of whether the $X_i$‘s are independent!

And for an indicator variable $X_A$ for event $A$ ($X_A=1$ if $A$ occurs, 0 otherwise), we have $E[X_A]=Pr[A]$.

Analyzing Randomized QuickSort

The task is to sort $n$ elements. QuickSort is a popular algorithm for this. In the randomized version, we pick the pivot element uniformly at random from the current subarray.

Algorithm QUICKSORT(A, l, r):

1. If $l<r$ then:
2. Choose a pivot $p$ uniformly at random from the elements $A[l],\dots ,A[r]$.
3. Partition $A[l\dots r]$ around $p$ such that elements $\le p$ are to its left, and elements $>p$ are to its right. Let $p$ end up at index $t$. (So $A[l\dots t-1]\le A[t]$ and $A[t+1\dots r]>A[t]$).
4. QUICKSORT(A, l, t-1) (Recursive call on the “left block”)
5. QUICKSORT(A, t+1, r) (Recursive call on the “right block”)

The running time of QuickSort is dominated by the number of comparisons made. Let $X$ be the random variable representing the total number of comparisons made by Randomized QuickSort on an input array $A$ of length $n$. From basic algorithms courses, we know the runtime is $\Theta (X)$.

We want to find $E[X]$. The known result is $E[X]=O(n\ln n)$.

Analyzing Comparisons using Indicator Variables

Let the input array be $A$, and let $a_1<a_2<\dots <a_n$ be the elements of $A$ in sorted order. (These are the values, not necessarily their initial positions).

Let $X$ be the total number of comparisons.

We can express $X$ as a sum of indicator variables. For every pair of distinct elements $(a_i,a_j)$ from the sorted list, let $X_{i,j}$ be the indicator variable for the event ”$a_i$ is compared with $a_j$ during the execution of QuickSort”. We can assume $i<j$ without loss of generality, as comparison is symmetric.

$X={\sum }_{1\le i<j\le n}{X}_{i,j}$

By linearity of expectation: $E[X]={\sum }_{1\le i<j\le n}E[X_{i,j}]$

And since $X_{i,j}$ is an indicator variable, $E[X_{i,j}]=Pr[a_i\text{ is compared with }{a}_j]$. So, $E[X]={\sum }_{1\le i<j\le n}Pr[a_i\text{ is compared with }{a}_j]$.

Key Observations about Comparisons in QuickSort

• A pivot element is compared with all other elements currently in its own block.
• Once an element is chosen as a pivot, it is never part of any future block and is never compared again.
• Two elements $a_i$ and $a_j$ are compared if and only if one of them is the first element to be chosen as a pivot from the set $\{a_i,a_{i+1},\dots ,a_j\}$.
  • Why? Consider the set of elements $S_{i,j}=\{a_i,a_{i+1},\dots ,a_j\}$. These elements are all initially in the same block.
  • If an element $a_k$ with $i<k<j$ is chosen as the pivot before either $a_i$ or $a_j$ are chosen as pivots, then $a_i$ will go to the left sub-block (since $a_i<a_k$) and $a_j$ will go to the right sub-block (since $a_j>a_k$). Once $a_i$ and $a_j$ are in different sub-blocks, they will never be compared.
  • If $a_i$ is the first pivot chosen from $S_{i,j}$, then $a_i$ will be compared to all other elements in $S_{i,j}$ that are still in its block, including $a_j$.
  • If $a_j$ is the first pivot chosen from $S_{i,j}$, then $a_j$ will be compared to all other elements in $S_{i,j}$ that are still in its block, including $a_i$.

So, $Pr[a_i\text{ is compared with }{a}_j]$ is the probability that out of the set $S_{i,j}=\{a_i,a_{i+1},\dots ,a_j\}$, either $a_i$ or $a_j$ is chosen as the pivot when that set (or a superset containing it) is first partitioned by one of its members.

The elements in $S_{i,j}$ are $a_i,a_{i+1},\dots ,a_j$. There are $j-i+1$ such elements.

When the block containing all of $S_{i,j}$ is partitioned for the first time by choosing a pivot from $S_{i,j}$, each of these $j-i+1$ elements has an equal chance of being chosen as that first pivot from this set. $a_i$ and $a_j$ will be compared if and only if $a_i$ is picked first from $S_{i,j}$ or $a_j$ is picked first from $S_{i,j}$. There are 2 “favorable” choices (either $a_i$ or $a_j$) out of $j-i+1$ possibilities for being the first pivot from this set.

Therefore, $Pr[a_i\text{ is compared with }{a}_j]=\frac{2}{j-i+1}$.

Now we can calculate $E[X]$: $E[X]={\sum }_{1\le i<j\le n}\frac{2}{j-i+1}$

More on Indicator Variables

We’ve seen $I_A(\omega )=1$ if $\omega \in A$, $0$ otherwise. How do indicator variables behave with set operations?

• Intersection: $A\cap B$. An outcome $\omega$ is in $A\cap B$ if it’s in $A$ AND it’s in $B$. $I_{A\cap B}(\omega )=1$ iff $I_A(\omega )=1$ AND $I_B(\omega )=1$. So, $I_{A\cap B}=I_A\cdot I_B$. (Product of indicator variables)
• Complement: $\bar{A}=\Omega \setminus A$. $I_{\bar{A}}(\omega )=1$ iff $I_A(\omega )=0$. So, $I_{\bar{A}}=1-I_A$.
• Union: $A\cup B$. What is $I_{A\cup B}$? We know $A\cup B$ means $\omega \in A$ OR $\omega \in B$ (or both). Using De Morgan’s laws and complement: $A\cup B=\overline{\bar{A}\cap \bar{B}}$. So, $I_{A\cup B}=I_{\overline{\bar{A}\cap \bar{B}}}=1-I_{\bar{A}\cap \bar{B}}$ $=1-(I_{\bar{A}}\cdot I_{\bar{B}})$ $=1-((1-I_A)(1-I_B))$ $=1-(1-I_A-I_B+I_A{I}_B)$ $=I_A+I_B-I_A{I}_B$. Alternatively, directly from inclusion-exclusion principle for probabilities and $E[I_E]=Pr[E]$: $Pr[A\cup B]=Pr[A]+Pr[B]-Pr[A\cap B]$ $E[I_{A\cup B}]=E[I_A]+E[I_B]-E[I_{A\cap B}]=E[I_A]+E[I_B]-E[I_A{I}_B]$. Since this holds for all probability distributions, it suggests $I_{A\cup B}=I_A+I_B-I_A{I}_B$. Let’s check: if $\omega \in A,\omega \notin B$: $1=1+0-0$. If $\omega \in A,\omega \in B$: $1=1+1-1$. Correct.

Principle of Inclusion-Exclusion via Indicator Variables

Let $B=A_1\cup A_2\cup \dots \cup A_n$. We want $Pr[B]=E[I_B]$.

The complement is $\bar{B}=\overline{A_1\cup \dots \cup A_n}=\overline{A_1}\cap \overline{A_2}\cap \dots \cap \overline{A_n}$.

So, $I_{\bar{B}}=I_{\overline{A_1}\cap \dots \cap \overline{A_n}}=I_{\overline{A_1}}\cdot I_{\overline{A_2}}\cdot \dots \cdot I_{\overline{A_n}}$ $I_{\bar{B}}=(1-I_{A_1})(1-I_{A_2})\dots (1-I_{A_n})$.

Expanding this product: $I_{\bar{B}}=1-{\sum }_i{I}_{A_i}+{\sum }_{i<j}{I}_{A_i}{I}_{A_j}-{\sum }_{i<j<k}{I}_{A_i}{I}_{A_j}{I}_{A_k}+\dots +(-1{)}^n{I}_{A_1}\dots I_{A_n}$.

Now, $I_B=1-I_{\bar{B}}$. $I_B={\sum }_i{I}_{A_i}-{\sum }_{i<j}{I}_{A_i}{I}_{A_j}+{\sum }_{i<j<k}{I}_{A_i}{I}_{A_j}{I}_{A_k}-\dots -(-1{)}^n{I}_{A_1}\dots I_{A_n}$. Taking the expectation of both sides and using $E[I_E{I}_F\dots ]=E[I_{E\cap F\cap \dots }]=Pr[E\cap F\cap \dots ]$ and linearity: $Pr[B]={\sum }_{i}Pr[A_i]-{\sum }_{i<j}Pr[A_i\cap A_j]+{\sum }_{i<j<k}Pr[A_i\cap A_j\cap A_k]-\dots +(-1{)}^{n-1}Pr[A_1\cap \dots \cap A_n]$. This is exactly the Principle of Inclusion-Exclusion!

Common Discrete Probability Distributions

We’ll now look at a few named discrete distributions that appear frequently.

Bernoulli Distribution

TLDR: success or failure + independence

An indicator variable $I_A$ follows a Bernoulli distribution, if an experiment has only two outcomes, “success” (with probability $p$) and “failure” (with probability $1-p$), a random variable $X$ that is 1 for success and 0 for failure is a Bernoulli random variable.

We write $X\sim \text{Bernoulli}(p)$.

The event $A$ is “success”, so $p=Pr[A]=E[I_A]$.

PMF (Dichtefunktion): $f_X(x)=\{\begin{array}{ll}p& \text{if }x=1\\ 1-p& \text{if }x=0\\ 0& \text{otherwise}\end{array}$

Expected Value: $E[X]=1\cdot p+0\cdot (1-p)=p$.

Binomial Distribution

TLDR: n independent bernoulli with n choose k wins

Suppose we perform $n$ independent Bernoulli trials, each with the same success probability $p$. Let $X$ be the total number of successes in these $n$ trials. Then $X$ follows a Binomial distribution, written $X\sim \text{Bin}(n,p)$.

To find $Pr[X=k]$ (probability of exactly $k$ successes in $n$ trials):

1. Choose $k$ positions out of $n$ for the successes: $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways.
2. The probability of one specific sequence of $k$ successes and $n-k$ failures is $p^k(1-p{)}^{n-k}$ (due to independence).

PMF: $Pr[X=k]=f_X(k)=\{\begin{array}{ll}\left(\genfrac{}{}{0ex}{}{n}{k}\right)p^k(1-p{)}^{n-k}& \text{for }k\in \{0,1,\dots ,n\}\\ 0& \text{otherwise}\end{array}$

Expected Value: If $X=X_1+\dots +X_n$ where $X_i\sim \text{Bernoulli}(p)$ are independent indicator variables for success on trial $i$, then by linearity of expectation: $E[X]=E[X_1]+\dots +E[X_n]=p+\dots +p=np$. So, $E[X]=np$.

Poisson Distribution (Balls and Bins)

TLDR: Limit of Binomial

Consider throwing $n$ balls randomly and independently into $n$ bins.

Let $X$ be the number of balls in the first bin. Each ball lands in the first bin with probability $p=1/n$. So, $X\sim \text{Bin}(n,1/n)$.

$E[X]=n\cdot (1/n)=1$.

What happens to $Pr[X=i]$ as $n\to \infty$?

$Pr[X=i]=\left(\genfrac{}{}{0ex}{}{n}{i}\right)(1/n{)}^i(1-1/n{)}^{n-i}$ $=\frac{n(n-1)\dots (n-i+1)}{i!}\frac{1}{n^i}(1-1/n{)}^{n-i}$ $=\frac{n}{n}\frac{n-1}{n}\dots \frac{n-i+1}{n}\cdot \frac{1}{i!}\cdot (1-1/n{)}^{n-i}$

As $n\to \infty$:

• $\frac{n-k}{n}\to 1$ for fixed $k$. So the product $\frac{n}{n}\dots \frac{n-i+1}{n}\to 1$.
• $(1-1/n{)}^{n-i}=(1-1/n{)}^n(1-1/n{)}^{-i}$. We know $(1-1/n{)}^n\to e^{-1}$. And $(1-1/n{)}^{-i}\to 1^{-i}=1$.

So, ${\lim }_{n\to \infty }Pr[X=i]=\frac{1}{i!}{e}^{-1}=\frac{e^{-1}}{i!}$.

More generally, if $X\sim \text{Bin}(n,\lambda /n)$ (so $E[X]=\lambda$), then as $n\to \infty$: ${\lim }_{n\to \infty }Pr[X=i]=\frac{{\lambda }^i{e}^{-\lambda }}{i!}$.

This is the PMF of a Poisson distribution with parameter $\lambda$. We write $X\sim \text{Po}(\lambda )$. $E[X]=\lambda$.

The Poisson distribution models the number of rare events occurring in a fixed interval of time or space, if these events occur with a known constant mean rate and independently of the time since the last event.

Example: Number of heart attacks in Switzerland in the next hour.

Geometric Distribution

TLDR: bernoulli until first success + memoryless

Suppose we perform independent Bernoulli trials, each with success probability $p$. Let $X$ be the number of trials until the first success occurs.

Then $X$ follows a Geometric distribution, written $X\sim \text{Geo}(p)$.

Example: Keep flipping a coin (success = Head, prob $p$) until the first Head appears. $X$ is the number of flips.

For $X=k$ (first success on $k$-th trial), we must have $k-1$ failures followed by one success: Sequence: F F … F S (k-1 F’s)

Probability: $(1-p)(1-p)\dots (1-p)\cdot p=(1-p{)}^{k-1}p$.

PMF: $f_X(k)=\{\begin{array}{ll}(1-p{)}^{k-1}p& \text{for }k\in \{1,2,3,\dots \}\\ 0& \text{otherwise}\end{array}$

Expected Value: $E[X]=1/p$.

Intuitively, if success prob is $p=1/10$, you expect to wait 10 trials.

CDF: $F_X(n)=Pr[X\le n]=1-Pr[X>n]$. $Pr[X>n]$ means the first $n$ trials were all failures. So, $Pr[X>n]=(1-p{)}^n$. Thus, $F_X(n)=1-(1-p{)}^n$ for $n=1,2,\dots$.

Memorylessness Property

A key property of the Geometric distribution is memorylessness.

It states that for $s,t\in \mathbb{N}$: $Pr[X>s+t\mid X>s]=Pr[X>t]$

(The slide has $Pr[X\ge s+t\mid X>s]=Pr[X\ge t]$ which is slightly different but similar in spirit if $s$ is large, or can be rewritten using $Pr[X=k]$ directly for $Pr[X>s+t|X>s]$).

Let’s use the standard definition: If you’ve already waited $s$ trials without success, the probability that you have to wait at least $t$ additional trials for the first success is the same as the probability that you had to wait at least $t$ trials from the very beginning. The process “forgets” how long it has already waited.

Example: If you’ve flipped 1000 tails in a row, the probability of getting a Head on the 1001st flip is still $p$, same as on the 1st flip.

Negative Binomial Distribution

TLDR: n-th successful bernoulli (i.e. generalize geometric)

This generalizes the Geometric distribution.

Let $X$ be the number of trials until the $n$-th success occurs in a sequence of independent Bernoulli trials (success prob $p$).

Then $X$ follows a Negative Binomial distribution. (The slide calls it NegativeBinomial(n), but often it’s parameterized by $n$ and $p$, like NB(n,p)).

To have the $n$-th success on the $k$-th trial:

1. The $k$-th trial must be a success.
2. In the first $k-1$ trials, there must have been exactly $n-1$ successes.

The number of ways to arrange $n-1$ successes in $k-1$ trials is $\left(\genfrac{}{}{0ex}{}{k-1}{n-1}\right)$. The probability of any such specific sequence of $n-1$ successes (and $(k-1)-(n-1)=k-n$ failures) in the first $k-1$ trials is $p^{n-1}(1-p{)}^{k-n}$. Then multiply by $p$ for the success on the $k$-th trial.

PMF: $f_X(k)=\{\begin{array}{ll}\left(\genfrac{}{}{0ex}{}{k-1}{n-1}\right)p^n(1-p{)}^{k-n}& \text{for }k\in \{n,n+1,\dots \}\\ 0& \text{otherwise}\end{array}$

Expected Value: $E[X]=n/p$. If $X_i\sim \text{Geo}(p)$ is time to $i$-th success after $(i-1)$-th success, then $X=X_1+\dots +X_n$, so $E[X]=n\cdot (1/p)$.

Coupon Collector’s Problem

There are $n$ different types of coupons (e.g., pictures in cereal boxes). In each round (e.g., buying a box), you get one coupon chosen uniformly at random from the $n$ types (with replacement).

Let $X$ be the number of rounds until you have collected at least one of each of the $n$ types of coupons. Question: What is $E[X]$?

Solution Approach

We divide the process into $n$ phases.

Phase $i$: The time (number of rounds) spent while you already have $i-1$ distinct coupon types and are waiting to collect the $i$-th new distinct type.

Let $X_i$ be the number of rounds in Phase $i$.

The total number of rounds is $X=X_1+X_2+\dots +X_n$. By linearity of expectation, $E[X]=E[X_1]+E[X_2]+\dots +E[X_n]$.

Consider Phase $i$: You currently have $i-1$ distinct coupon types. In any round, the probability of getting any specific coupon is $1/n$. There are $n-(i-1)=n-i+1$ coupon types that you don’t yet have.

So, the probability of getting a new coupon type (a success for this phase) in any given round is $p_i=\frac{n-i+1}{n}$.

The number of rounds $X_i$ to get this $i$-th new type is therefore Geometrically distributed: $X_i\sim \text{Geo}(p_i)$. So, $E[X_i]=1/p_i=\frac{n}{n-i+1}$.

Expectation

Now, sum the expectations:

$E[X]={\sum }_{i=1}^{n}E[X_i]={\sum }_{i=1}^n\frac{n}{n-i+1}$.

Let $k=n-i+1$. As $i$ goes from $1$ to $n$, $k$ goes from $n$ down to $1$.

$E[X]={\sum }_{k=1}^n\frac{n}{k}=n{\sum }_{k=1}^n\frac{1}{k}=n{H}_n$.

Since $H_n\approx \ln n+\gamma$ (where $\gamma \approx 0.577$ is the Euler-Mascheroni constant),

$E[X]=n{H}_n\approx n\ln n+O(n)$.

So, on average, you need about $n\ln n$ rounds to collect all $n$ coupons. For example, if $n=50$, $E[X]\approx 50\ln 50\approx 50\times 3.91\approx 195.6$.

Continue here: 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