The per-stage quantile budget, and when it is tight

ProofIntermediate⏱ 1 hourAI Systemsquantilesunion boundcompositiontightness

Problem

Let $W = W_1+\cdots+W_k$ with each $W_i \ge 0$ .

Prove that if $\sum_i(1-p_i) \le 1-p$ then $q_p(W) \le \sum_i q_{p_i}(W_i)$ , without assuming independence.
Exhibit a dependent example with $k=2$ for which the bound is attained with equality.
Show that for independent $W_i$ the bound is typically very loose, by computing both sides for $k$ i.i.d. exponentials with mean $1$ at $p = 0.99$ , $k = 4$ .

Write a complete argument. Every inequality you use should be one you could state precisely.

Hints — 0 of 2 revealed

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Problem	Field	Type	Difficulty	Time
Markov and Chebyshev are attained	High-Dim Probability	Proof	Foundation	15 min
When is the union bound tight?	Probability	Proof	Foundation	15 min
Budget a latency target across a fan-out	AI Systems	Numerical	Beginner	15 min
Generalisation for a finite class	Learning Theory	Proof	Beginner	30 min
Tightness of the descent lemma	Foundations	Proof	Beginner	15 min