COMPX270 — Randomised and Advanced Algorithms
Chapter 1: Randomness, Probability, and Algorithms
An interactive study guide covering randomized algorithms, expected-time analysis, QuickSort, and essential probability tools.
The Card Deck Experiment
Question: Take a standard deck of 52 cards (13 of each suit). Shuffle it uniformly at random. How many consecutive pairs of the same suit do you expect?
Interactive Simulation
Click "Shuffle & Count" to simulate shuffling a deck and counting consecutive same-suit pairs. Run it many times to see the average converge!
Define indicator variables. Let \(X_i\) be the suit of the \(i\)-th card. Define \(Y_i = \mathbf{1}\{X_i = X_{i+1}\}\) for \(i = 1, \ldots, 51\).
The total number of consecutive same-suit pairs is \(Y = \sum_{i=1}^{51} Y_i\).
Compute each probability. For any position \(i\), once card \(i\) has some suit, there are 12 remaining cards of that suit out of 51 remaining cards total:
\[\Pr[Y_i = 1] = \Pr[X_i = X_{i+1}] = \frac{13 - 1}{52 - 1} = \frac{12}{51}\]
Apply linearity of expectation. We do not need independence of the \(Y_i\)!
\[\mathbb{E}[Y] = \sum_{i=1}^{51} \mathbb{E}[Y_i] = 51 \cdot \frac{12}{51} = 12 \quad \blacksquare\]
What is a Randomized Algorithm?
A randomized algorithm is an algorithm whose behaviour depends not only on the input \(x\), but also on random bits \(R \in \{0,1\}^*\).
Deterministic Algorithm
Same input → always same output, same running time.
Randomized Algorithm
Same input → output and/or runtime may vary.
Types of Analysis
| Analysis Type | Formula | What varies? |
|---|---|---|
| Worst-case | \(T(n) = \max_{|x|=n} \tau_A(x)\) | Nothing random |
| Expected (this course!) | \(T(n) = \max_{|x|=n} \mathbb{E}_R[\tau_A(x; R)]\) | Algorithm uses random bits \(R\) |
| Average-case | \(T(n) = \mathbb{E}_x[\tau_A(x)]\) | Input \(x\) is random |
| Amortized | \(T(n) = \lim_{k\to\infty} \frac{1}{k}\max \tau_{A^k}(\ldots)\) | Sequence of inputs |
Why Randomize?
- Avoid pathological corner cases
- Simpler, faster algorithms
- Avoid predictable outcomes
- Cryptography & privacy
- Break ties / impossibility results
Drawbacks
- Non-deterministic behaviour
- Random bits don't grow on trees!
- Bad random bits → bad outputs
Las Vegas vs Monte Carlo
Las Vegas
Output is always correct, but running time is only bounded in expectation.
Monte Carlo
Running time is always bounded, but output is only correct with high probability.
Explore: Even-Number Search
Array \(A\) of size \(n\) contains all numbers \(1\) to \(n\). Find an index holding an even number.
Worst-case: \(\Omega(n)\). An adversary can put all even numbers at the end. You must scan linearly.
for i in range(n):
if A[i] % 2 == 0:
return iExpected time: \(O(1)\). Pick random index; half the entries are even, so expected 2 attempts.
while True:
i = random.randint(0, n-1)
if A[i] % 2 == 0:
return i # Always correct!Worst-case time: \(O(1)\). Try 100 random indices. Probability of failure \(\leq (1/2)^{100}\).
for _ in range(100):
i = random.randint(0, n-1)
if A[i] % 2 == 0:
return i
return "FAIL" # Might be wrong!Randomized QuickSort
Algorithm: QuickSort
QuickSort(A):
if |A| ≤ 1: return A
Pick pivot p = A[i] for random i in {1,...,n}
Partition into A1 (< p), A2 (= p), A3 (> p) // O(n) time
Recursively sort A1 and A3
Merge sorted A1, A2, A3 // O(n) time
return ASet up the recurrence. Let \(T(n)\) be the expected running time. The pivot is the \(k\)-th largest with probability \(1/n\):
\[T(n) = cn + \frac{1}{n}\sum_{k=1}^{n}\bigl(T(k-1) + T(n-k)\bigr) = cn + \frac{2}{n}\sum_{k=0}^{n-1}T(k)\]
Convert to a differential equation. Using the fact that sums approximate integrals for non-decreasing functions, consider the continuous version:
\[T(x) = cx + \frac{2}{x}\int_0^x T(u)\,du\]
Let \(F(x) = \int_0^x T(u)\,du\), so \(F'(x) = T(x)\). This gives:
\[F'(x) = cx + \frac{2}{x}F(x)\]
Solve the ODE. Divide by \(x^2\):
\[\frac{F'(x)}{x^2} - \frac{2F(x)}{x^3} = \frac{c}{x}\]
Recognize the left side as \(\frac{d}{dx}\!\left[\frac{F(x)}{x^2}\right]\). Integrate:
\[\frac{F(x)}{x^2} = c\ln x + C \implies F(x) = cx^2 \ln x + Cx^2\]
Recover \(T\).
\[T(x) = F'(x) = 2cx\ln x + (2C+c)x = O(x\log x)\]
Therefore \(T(n) = O(n\log n)\). \(\blacksquare\)
Visualize: Randomized QuickSort
Watch how pivot selection affects partitioning. Click "Step" to advance one recursion level, or "Auto-Sort" to animate the full sort.
Counting Comparisons via Linearity of Expectation
Instead of solving a recurrence, we can elegantly count the expected number of comparisons using indicator random variables.
Set up indicator variables. Let \(a_1 < a_2 < \cdots < a_n\) be the elements in sorted order. Define \(X_{ij} \in \{0,1\}\) as the indicator of whether \(a_i\) and \(a_j\) are ever compared.
\[C(n) = \mathbb{E}\!\left[\sum_{i=1}^{n-1}\sum_{j=i+1}^{n} X_{ij}\right] = \sum_{i
Key insight: \(a_i\) and \(a_j\) are compared if and only if the first element from \(\{a_i, a_{i+1}, \ldots, a_j\}\) chosen as a pivot is \(a_i\) or \(a_j\) itself.
If any \(a_k\) with \(i < k < j\) is chosen as pivot first, then \(a_i\) and \(a_j\) are separated into different subarrays and never meet again.
\[\Pr[a_i \text{ and } a_j \text{ are compared}] = \frac{2}{j - i + 1}\]
Sum it up. Substituting \(k = j - i\):
\[C(n) = \sum_{i=1}^{n-1}\sum_{j=i+1}^{n} \frac{2}{j-i+1} = 2\sum_{i=1}^{n-1}\sum_{k=1}^{n-i}\frac{1}{k+1}\]
Using Harmonic numbers \(H_k = \sum_{j=1}^k \frac{1}{j} \leq \ln k + 1\):
\[C(n) = 2\sum_{i=1}^{n-1}(H_{n-i+1} - 1) = 2\sum_{m=2}^{n}(H_m - 1) \leq 2\sum_{m=2}^{n}\ln m \leq 2n\ln n\]
\(\blacksquare\)
Probability Toolkit
These essential facts are used throughout the course. Click each card to reveal the details.
Tail-Sum Formula
Alternative way to compute \(\mathbb{E}[X]\) for non-negative integer-valued r.v.
Click to revealIf \(X\) takes values in \(\mathbb{N} = \{0,1,2,\ldots\}\):
\[\mathbb{E}[X] = \sum_{n=1}^{\infty} \Pr[X \geq n]\]
Remember: starts at \(n=1\), not \(n=0\). (Check: if \(X=0\) always, \(\mathbb{E}[X]=0\) but \(\Pr[X\geq 0]=1\).)
Linearity of Expectation
The single most important tool in this chapter.
Click to reveal\[\mathbb{E}[aX + bY] = a\,\mathbb{E}[X] + b\,\mathbb{E}[Y]\]
Extends to any sum: \(\mathbb{E}\!\left[\sum_i X_i\right] = \sum_i \mathbb{E}[X_i]\).
No independence needed!
Variance Formulas
How spread out is a random variable?
Click to reveal\[\text{Var}[X] = \mathbb{E}[X^2] - \mathbb{E}[X]^2\]
\[\text{Var}[aX] = a^2 \text{Var}[X]\]
If \(X_1,\ldots,X_n\) are pairwise independent:
\[\text{Var}\!\left[\sum_i X_i\right] = \sum_i \text{Var}[X_i]\]
Jensen's Inequality
Convex functions and expectations.
Click to revealIf \(f\) is convex:
\[f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)]\]
Memory trick: Check with \(f(x)=x^2\). We know \(\text{Var}[X]\geq 0\), i.e., \(\mathbb{E}[X^2]\geq \mathbb{E}[X]^2\). ✔
Bernoulli & Binomial
The building blocks of discrete probability.
Click to revealBernoulli(\(p\)): \(X\in\{0,1\}\), \(\Pr[X=1]=p\).
- \(\mathbb{E}[X]=p\), \(\text{Var}[X]=p(1-p)\leq 1/4\)
Binomial(\(n,p\)): Sum of \(n\) i.i.d. Bernoulli(\(p\)).
- \(\mathbb{E}[X]=np\), \(\text{Var}[X]=np(1-p)\)
Indicator Variables
The technique behind most proofs in this chapter.
Click to revealFor an event \(E\), define \(\mathbf{1}_E\):
\[\mathbf{1}_E = \begin{cases} 1 & \text{if } E \text{ occurs} \\ 0 & \text{otherwise}\end{cases}\]
\(\mathbb{E}[\mathbf{1}_E] = \Pr[E]\). Combine with linearity of expectation to count expected number of "good" events!
Tutorial Problems
Work through each problem, then reveal the solution. Try before you look!
Consider a deck of \(4n\) cards, with \(n\) of each suit. After it is shuffled uniformly at random, what is the expected number of consecutive pairs of the same suit?
Answer: \(n - 1\)
Let \(Y_i = \mathbf{1}\{X_i = X_{i+1}\}\). For any position \(i\):
\[\Pr[X_i = X_{i+1}] = \frac{n-1}{4n-1}\]
By linearity of expectation:
\[\mathbb{E}[Y] = (4n-1)\cdot\frac{n-1}{4n-1} = n - 1\]
Sanity check: \(n=13 \Rightarrow 12\). ✔
A computer randomly generates a 2024-bit long binary string. What is the expected number of consecutive runs of 3 ones?
Answer: 252.75
Define \(Y_i = \mathbf{1}\{X_i = X_{i+1} = X_{i+2} = 1\}\) for \(i=1,\ldots,2022\). By independence of each bit:
\[\mathbb{E}[Y_i] = \left(\frac{1}{2}\right)^3 = \frac{1}{8}\]
By linearity: \(\mathbb{E}[Y] = \frac{2022}{8} = 252.75\).
Show that the expected number of fixed points of a uniformly random permutation of \(\{1,\ldots,n\}\) is 1. What is the variance?
Expectation = 1, Variance = 1
Let \(X_i = \mathbf{1}\{\pi(i)=i\}\). Then \(\Pr[X_i=1]=\frac{1}{n}\), so \(\mathbb{E}[X]=\sum_{i=1}^n \frac{1}{n} = 1\).
For variance: \(\text{Var}[X] = \mathbb{E}[X^2] - 1\). Expanding \(X^2 = (\sum_i X_i)^2\):
\[\mathbb{E}[X^2] = \sum_i \mathbb{E}[X_i] + \sum_{i\neq j}\Pr[\pi(i)=i \text{ and } \pi(j)=j]\]
\[= 1 + n(n-1)\cdot\frac{1}{n(n-1)} = 1 + 1 = 2\]
So \(\text{Var}[X] = 2 - 1 = 1\).
(1) Give a random variable \(X\) over \([0, \infty)\) such that \(\mathbb{E}[X] = \infty\). (2) Give a random variable \(X\) over \(\mathbb{N}\) such that \(\mathbb{E}[X] = \infty\).
(1) Continuous case: A random variable with probability density function \(f(x) = \frac{2}{\pi} \cdot \frac{1}{x^2 + 1}\) (the Cauchy distribution). Since \(\int_0^\infty \frac{2x}{\pi(x^2+1)}\,dx\) diverges, \(\mathbb{E}[X] = \infty\).
(2) Discrete case: A random variable with probability mass function \(p(n) = \frac{6}{\pi^2} \cdot \frac{1}{(n+1)^2}\). Since \(\sum_{n=0}^{\infty} \frac{n}{(n+1)^2}\) diverges, \(\mathbb{E}[X] = \infty\).
Prove the fact from the lecture: if \(X\) has a finite variance, then \(\text{Var}[X] = \mathbb{E}[X^2] - \mathbb{E}[X]^2\).
Proof: Let \(\mu = \mathbb{E}[X]\). By definition:
\[\text{Var}[X] = \mathbb{E}[(X - \mu)^2] = \mathbb{E}[X^2 - 2\mu X + \mu^2]\]
Applying linearity of expectation:
\[= \mathbb{E}[X^2] - 2\mu\,\mathbb{E}[X] + \mu^2 = \mathbb{E}[X^2] - 2\mu^2 + \mu^2 = \mathbb{E}[X^2] - \mu^2\]
\[= \mathbb{E}[X^2] - \mathbb{E}[X]^2 \quad \blacksquare\]
Prove the fact from the lecture: if \(X\) takes values in \(\mathbb{N} = \{0, 1, 2, \ldots\}\) and \(\mathbb{E}[X]\) is finite, then \(\mathbb{E}[X] = \sum_{n=1}^{\infty} \Pr[X \geq n]\).
Proof (swap the sums):
\[\sum_{n=1}^{\infty} \Pr[X \geq n] = \sum_{n=1}^{\infty} \sum_{k=n}^{\infty} \Pr[X = k] = \sum_{k=1}^{\infty} \sum_{n=1}^{k} \Pr[X = k]\]
The inner sum has \(k\) identical terms:
\[= \sum_{k=1}^{\infty} k \cdot \Pr[X = k] = \mathbb{E}[X] \quad \blacksquare\]
The swap of summation is justified because all terms are non-negative and \(\mathbb{E}[X]\) is finite.
You have a biased coin with unknown \(p = \Pr[\text{Heads}] \in (0,1)\). Using only this coin, generate a fair coin toss. How many biased tosses do you need in expectation?
Von Neumann's Trick:
- Toss the biased coin twice.
- If HT → output Heads. If TH → output Tails.
- If HH or TT → discard and repeat.
This works because \(\Pr[\text{HT}] = p(1-p) = (1-p)p = \Pr[\text{TH}]\), so both are equally likely.
Expected tosses: Each attempt succeeds with probability \(2p(1-p)\). Expected attempts = \(\frac{1}{2p(1-p)}\), and each attempt uses 2 tosses, so:
\[\text{Expected tosses} = \frac{2}{2p(1-p)} = \frac{1}{p(1-p)}\]
A mouse (M) wants to reach cheese (C). There are 3 paths: top (2 edges), middle (3 edges), bottom (4 edges). Each edge has a cat with probability \(p\), independently. What is the probability the mouse can still reach the cheese?
A path is open iff all its edges are cat-free. The mouse succeeds iff at least one path is open.
\[\Pr[\text{path}] = 1 - \Pr[\text{no path}]\]
\[= 1 - \Pr[\text{top blocked}]\cdot\Pr[\text{mid blocked}]\cdot\Pr[\text{bot blocked}]\]
\[= 1 - \bigl(1-(1-p)^2\bigr)\bigl(1-(1-p)^3\bigr)\bigl(1-(1-p)^4\bigr)\]
Part (b): Paths of length \(\leq 3\): only top and middle. Answer: \(1 - (1-(1-p)^2)(1-(1-p)^3)\).
Part (c): Expected cats = \(9p\) (9 edges, each has a cat with probability \(p\), by linearity).
An index \(i\) is a "prefix-maximum" of array \(A\) if \(A[i]\) is the largest among \(A[1],\ldots,A[i]\). If we permute \(A\) uniformly at random, show that the expected number of prefix-maxima is \(H_n = O(\log n)\).
(a) If \(A\) is sorted (increasing), every element is a prefix-max, so \(\text{pf}(A) = n\).
(b) Let \(X_i = \mathbf{1}\{B[i]\text{ is prefix-max}\}\). The \(i\)-th element is a prefix-max iff it is the largest among the first \(i\) elements. By symmetry:
\[\Pr[X_i = 1] = \frac{1}{i}\]
By linearity of expectation:
\[\mathbb{E}[\text{pf}(B)] = \sum_{i=1}^n \frac{1}{i} = H_n = O(\log n) \quad \blacksquare\]
Let \(X_1,X_2,\ldots\) be i.i.d. Bernoulli(\(p\)) and \(Y_n = X_1 \oplus X_2 \oplus \cdots \oplus X_n\). Find \(p_n = \Pr[Y_n = 1]\) and show it converges to \(1/2\).
Recurrence: \(p_{n+1} = (1-p)\,p_n + p\,(1-p_n) = (1-2p)\,p_n + p\)
Solution: Let \(q_n = p_n - 1/2\). Then \(q_{n+1} = (1-2p)\,q_n\), so \(q_n = (1-2p)^n \cdot q_0\) with \(q_0 = -1/2\).
\[\boxed{p_n = \frac{1}{2}\bigl(1 - (1-2p)^n\bigr)}\]
Since \(|1-2p| < 1\) for \(p\in(0,1)\), this converges exponentially fast to \(1/2\).
Chapter quizzes
Self-test and math questions for this chapter are in the Quiz Hub (practice or exam mode).