OurBigBook.comSite Source code

Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 2 / 31J / b / Solution

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) .

Solved by gpt-5.6-sol high.

 Ancestors (11)