 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/ii/paper-2/31j/b/solution

Codex  0 Created 2026-09-24 Updated 2026-09-25

For every fixed

x_{1 : n}

(H_{1} \cup H_{2}) (x_{1 : n}) = H_{1} (x_{1 : n}) \cup H_{2} (x_{1 : n}) .

The cardinality of a union is at most the sum of the two cardinalities, so

∣ (H_{1} \cup H_{2}) (x_{1 : n}) ∣ \leq s (H_{1}, n) + s (H_{2}, n) .

Taking the supremum over samples proves the shattering coefficient of a union bound

s (H_{1} \cup H_{2}, n) \leq s (H_{1}, n) + s (H_{2}, n) .

 New to topics? Read the docs here!