COMPX270 — Chapter 4 Supplement
Mathematical Foundations: Derandomisation
Graph theory, pairwise independence, universal hashing, conditional expectation, the probabilistic method, and approximation guarantees.
Graph Theory Basics
An undirected graph is a pair \(G = (V, E)\) where \(V\) is a finite set of vertices and \(E \subseteq \binom{V}{2}\) is a set of edges, each an unordered pair \(\{u, v\}\) with \(u \neq v\).
A cut in a graph \(G = (V, E)\) is a partition of the vertex set into two non-empty subsets \((A, B)\) with \(A \cup B = V\) and \(A \cap B = \emptyset\). The cut edges are:
\[c(A, B) = \bigl|\bigl\{\{u, v\} \in E : u \in A,\; v \in B\bigr\}\bigr|\]The Max-Cut problem asks to find a partition \((A, B)\) maximising \(c(A, B)\).
The complete graph \(K_n\) on \(n\) vertices has every possible edge. The number of edges is:
\[|E(K_n)| = \binom{n}{2} = \frac{n(n-1)}{2}\]Triangles & Orientations
A triangle in \(G\) is a set of three vertices \(\{u, v, w\}\) such that all three edges \(\{u,v\}, \{v,w\}, \{u,w\}\) are present. The number of triangles in \(K_n\) is \(\binom{n}{3}\).
An orientation of an undirected graph assigns a direction to each edge, producing a directed graph. Each undirected graph on \(m\) edges has \(2^m\) possible orientations.
NP-Hardness
A problem is NP-hard if no known polynomial-time algorithm solves it exactly. Unless \(\mathsf{P} = \mathsf{NP}\), there is no efficient exact algorithm. Max-Cut is NP-hard, which motivates approximation algorithms and derandomisation.
Randomness Complexity
The randomness complexity \(R\) of a randomised algorithm is the number of truly random bits it requires. If the algorithm uses \(R\) random bits, there are \(2^R\) possible random seeds.
Any randomised algorithm using \(R\) random bits can be derandomised by enumerating all \(2^R\) seeds. The resulting deterministic algorithm has running time:
\[\text{Time}_{\text{derand}} = 2^R \cdot \text{Time}_{\text{per seed}}\]If we can reduce \(R\) while preserving the probabilistic guarantee, we reduce the brute-force cost exponentially.
Tradeoff: Randomness vs Efficiency
Small \(R\) leads to efficient derandomisation. The goal is to replace \(R = n\) truly random bits with \(R' \ll n\) bits of limited randomness (e.g., pairwise independent) while preserving the expected performance.
To sample uniformly from a domain of size \(k\), we need exactly:
\[\lceil \log_2 k \rceil \text{ random bits}\]For \(n\) independent samples from \(\{0, 1\}\), we need \(n\) random bits. But if we only need pairwise independence, we can use far fewer.
Pairwise Independence
Random variables \(X_1, \ldots, X_n\) are fully (mutually) independent if for every subset \(S \subseteq [n]\) and every choice of values \(a_i\):
\[\Pr\!\left[\bigcap_{i \in S} (X_i = a_i)\right] = \prod_{i \in S} \Pr[X_i = a_i]\]Random variables \(X_1, \ldots, X_n\) are pairwise independent if for all \(i \neq j\) and all values \(a, b\):
\[\Pr[X_i = a \;\text{and}\; X_j = b] = \Pr[X_i = a] \cdot \Pr[X_j = b]\]Pairwise independence is strictly weaker than full independence.
Linearity of expectation requires no independence at all:
\[\mathbb{E}\!\left[\sum_i X_i\right] = \sum_i \mathbb{E}[X_i] \quad \text{(always true)}\]But variance of sums requires pairwise independence to decompose nicely:
\[\operatorname{Var}\!\left[\sum_i X_i\right] = \sum_i \operatorname{Var}[X_i] + 2\!\sum_{i < j}\!\operatorname{Cov}[X_i, X_j]\]Under pairwise independence, all covariance terms vanish, giving \(\operatorname{Var}[\sum X_i] = \sum \operatorname{Var}[X_i]\). This is all we need for Chebyshev-based analysis.
XOR Construction
Let \(X, Y\) be independent uniform bits in \(\{0, 1\}\). Define \(Z = X \oplus Y\). Then:
- \(Z\) is uniform: \(\Pr[Z = 0] = \Pr[Z = 1] = 1/2\)
- \((X, Y)\) are independent (by construction)
- \((X, Z)\) are independent: \(\Pr[X = a, Z = c] = \Pr[X = a, Y = a \oplus c] = 1/4\)
- \((Y, Z)\) are independent (by symmetry)
So \(X, Y, Z\) are pairwise independent. Three pairwise independent uniform bits from only two truly random bits!
Full independence requires \(\Pr[X = a, Y = b, Z = c] = \Pr[X = a]\Pr[Y = b]\Pr[Z = c] = 1/8\) for all \(a, b, c\).
But \(Z = X \oplus Y\), so \(\Pr[X = 0, Y = 0, Z = 1] = 0 \neq 1/8\). The triple is deterministically constrained: given any two, the third is fixed. \(\blacksquare\)
Hash Families
A family \(\mathcal{H}\) of functions \(h : X \to Y\) is universal (or 2-universal) if for all distinct \(x, x' \in X\):
\[\Pr_{h \sim \mathcal{H}}[h(x) = h(x')] \leq \frac{1}{|Y|}\]where \(h\) is chosen uniformly at random from \(\mathcal{H}\).
A family \(\mathcal{H}\) of functions \(h : X \to Y\) is strongly universal (or 2-independent) if for all distinct \(x, x' \in X\) and all \(y, y' \in Y\):
\[\Pr_{h \sim \mathcal{H}}[h(x) = y \;\text{and}\; h(x') = y'] = \frac{1}{|Y|^2}\]If \(\mathcal{H}\) is strongly universal, then it is universal.
For distinct \(x, x'\), marginalise over all possible values of \(h(x')\):
\[\Pr[h(x) = h(x')] = \sum_{y \in Y} \Pr[h(x) = y \;\text{and}\; h(x') = y] = \sum_{y \in Y} \frac{1}{|Y|^2} = \frac{|Y|}{|Y|^2} = \frac{1}{|Y|}\]This meets the universal hash family bound with equality. \(\blacksquare\)
XOR-Based Construction
Let \(x \in \{0,1\}^n\) be an input bit-string. For a subset \(S \subseteq [n]\), define:
\[h_S(x) = \bigoplus_{i \in S} x_i \quad \in \{0, 1\}\]The family \(\mathcal{H} = \{h_S : S \subseteq [n]\}\) has \(|\mathcal{H}| = 2^n\). For the practical version, we use subsets of size at most \(k = \lceil \log_2(n+1) \rceil\), giving \(|\mathcal{H}| = 2^k\) and requiring only \(k\) random bits to specify a hash function.
Inner Product mod \(p\)
Let \(p\) be prime and \(x, a \in \mathbb{Z}_p^k\). Define:
\[h_a(x) = \sum_{i=1}^{k} a_i \cdot x_i \mod p\]The family \(\mathcal{H} = \{h_a : a \in \mathbb{Z}_p^k\}\) is universal: for distinct \(x, x'\), we have \(\Pr_a[h_a(x) = h_a(x')] = 1/p = 1/|Y|\).
The inner-product family \(h_a(x) = \sum a_i x_i \bmod p\) is universal but not strongly universal. The single output value is uniform, but two distinct inputs do not produce jointly uniform outputs under this family (one linear equation in \(k\) unknowns leaves \(k-1\) degrees of freedom, but two equations leave \(k-2\)). To get strongly universal hashing, use the affine form \(h_{a,b}(x) = a \cdot x + b \bmod p\) with two independent parameters.
Conditional Expectation
If \(A_1, A_2, \ldots, A_k\) partition the sample space, then:
\[\mathbb{E}[X] = \sum_{i=1}^{k} \Pr[A_i] \cdot \mathbb{E}[X \mid A_i]\]Binary Split
For a random bit \(B \in \{0, 1\}\) with \(\Pr[B = 1] = p\):
\[\mathbb{E}[X] = p \cdot \mathbb{E}[X \mid B = 1] + (1 - p) \cdot \mathbb{E}[X \mid B = 0]\]This is a weighted average of the two conditional expectations.
For any two real numbers \(x, y\) and any \(p \in (0, 1)\):
\[p \cdot x + (1-p) \cdot y \leq \max(x, y)\]Consequence: since \(\mathbb{E}[X]\) is a weighted average of \(\mathbb{E}[X \mid B=0]\) and \(\mathbb{E}[X \mid B=1]\), at least one of the conditional expectations is \(\geq \mathbb{E}[X]\).
Chain of Conditional Expectations
Suppose a randomised algorithm uses random bits \(B_1, B_2, \ldots, B_R\) and we want to maximise \(\mathbb{E}[f(B_1, \ldots, B_R)]\). The method of conditional expectations fixes bits one at a time:
- Compute \(\mathbb{E}[f \mid B_1 = 0]\) and \(\mathbb{E}[f \mid B_1 = 1]\).
- Set \(b_1 = \arg\max\) of the two conditional expectations.
- Compute \(\mathbb{E}[f \mid B_1 = b_1, B_2 = 0]\) and \(\mathbb{E}[f \mid B_1 = b_1, B_2 = 1]\).
- Set \(b_2 = \arg\max\) and continue.
At each step we pick the better option, so the conditional expectation never decreases:
\[\mathbb{E}[f] \leq \mathbb{E}[f \mid B_1 = b_1] \leq \mathbb{E}[f \mid B_1 = b_1, B_2 = b_2] \leq \cdots \leq f(b_1, \ldots, b_R)\]The final deterministic output is at least as good as the original expected value. This converts any randomised algorithm into a deterministic one with guaranteed performance \(\geq \mathbb{E}[f]\).
The Probabilistic Method
If \(\Pr[\text{good outcome}] > 0\), then a good outcome exists. We don't need to find it constructively — the existence proof suffices.
\[\Pr[\text{good}] > 0 \implies \exists \text{ a good object}\]For any random variable \(X\):
\[\Pr[X \geq \mathbb{E}[X]] > 0\]That is, there must exist an outcome where \(X\) achieves at least its expected value.
Suppose for contradiction that \(\Pr[X \geq \mathbb{E}[X]] = 0\). Then \(X < \mathbb{E}[X]\) with probability 1, which implies:
\[\mathbb{E}[X] < \mathbb{E}[X]\]a contradiction. Therefore \(\Pr[X \geq \mathbb{E}[X]] > 0\). \(\blacksquare\)
Union Bound Application
To show a "globally good" outcome exists, identify bad events \(B_1, \ldots, B_m\) and show:
\[\Pr\!\left[\bigcup_{i=1}^{m} B_i\right] \leq \sum_{i=1}^{m} \Pr[B_i] < 1\]Then \(\Pr[\text{all good}] = 1 - \Pr[\bigcup B_i] > 0\), so a good outcome exists.
The Lovász Local Lemma (LLL) extends the probabilistic method to settings where bad events are not independent but have limited dependencies. It shows that if each bad event has low probability and depends on few others, then the probability that none of the bad events occur is positive. This is a powerful tool but is beyond the scope of this chapter.
Approximation Algorithms
For a maximisation problem, a polynomial-time algorithm is an \(\alpha\)-approximation (with \(0 < \alpha \leq 1\)) if for every instance it outputs a solution of value \(\geq \alpha \cdot \text{OPT}\), where \(\text{OPT}\) is the optimal value.
Max-Cut: The Easy \(1/2\)-Approximation
Assign each vertex to side \(A\) or \(B\) uniformly at random. Each edge \(\{u, v\}\) is cut with probability \(1/2\) (since \(u\) and \(v\) are on different sides with probability \(1/2\)). By linearity of expectation:
\[\mathbb{E}[\text{cut edges}] = \frac{|E|}{2} \geq \frac{\text{OPT}}{2}\]since \(\text{OPT} \leq |E|\). This gives a randomised \(1/2\)-approximation, which can be derandomised via the method of conditional expectations.
The Goemans–Williamson algorithm achieves an approximation ratio of:
\[\alpha_{\text{GW}} = \min_{0 \leq \theta \leq \pi} \frac{2}{\pi} \cdot \frac{\theta}{1 - \cos\theta} \approx 0.878\]It works by relaxing Max-Cut to a semidefinite program (SDP), solving the SDP optimally, then rounding the solution using a random hyperplane.
The SDP relaxation assigns a unit vector \(\mathbf{v}_i \in \mathbb{R}^n\) to each vertex \(i\). The relaxed objective is:
\[\frac{1}{2}\sum_{\{i,j\} \in E}(1 - \mathbf{v}_i \cdot \mathbf{v}_j)\]A random hyperplane through the origin partitions vertices by which side of the hyperplane their vector lies on. The probability edge \(\{i,j\}\) is cut equals \(\arccos(\mathbf{v}_i \cdot \mathbf{v}_j)/\pi\). The ratio \(\frac{\arccos(c)/\pi}{(1-c)/2}\) is minimised at \(\alpha_{\text{GW}} \approx 0.878\). \(\blacksquare\)
Hardness of Approximation
The Unique Games Conjecture (Khot, 2002) implies that no polynomial-time algorithm can achieve an approximation ratio better than \(\alpha_{\text{GW}} \approx 0.878\) for Max-Cut, unless \(\mathsf{P} = \mathsf{NP}\). Under a weaker assumption (just \(\mathsf{P} \neq \mathsf{NP}\)), it is known that no ratio better than \(16/17 \approx 0.941\) is achievable.
Math quiz
Chapter math quizzes are in the Quiz Hub. Filter by this chapter and choose Study / Math / All.