 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/ii/paper-1/31l/c/solution

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

For fixed

x_{1 : n}

put

A_{σ} = \sum_{i} σ_{i} x_{i} x_{i}^{T}

. Then

R (H (x_{1 : n})) = \frac{1}{n} E_{σ} sup_{M ⪰ 0, tr M \leq s} tr (M A_{σ}) \leq \frac{s}{n} E_{σ} ∥ A_{σ} ∥_{op} \leq \frac{s}{n} E_{σ} ∥ A_{σ} ∥_{F} .

Jensen's inequality and cancellation of cross terms between independent signs give

E_{σ} ∥ A_{σ} ∥_{F} \leq (\sum_{i} tr [(x_{i} x_{i}^{T})^{2}])^{1/2} = (\sum_{i} ∥ x_{i} ∥_{2}^{4})^{1/2} \leq C^{2} n .

Therefore

R_{n} (H) \leq \frac{C ^{2} s}{n} .

 New to topics? Read the docs here!