Union Bounds & Concentration - Statistics Graduate Level

1. What lower bound for the probability that all ten reported means are within $0.1$ of their respective expectations follows directly from these inequalities?
   Answer: $1-20\exp(-4)\approx 0.634$, using the sum of all ten two-sided failure bounds. When you need a probability guarantee that all of several events hold simultaneously, your first instinct should be the union bound (Boole's inequality): the probability that at least one event fails is at most the sum of the individual failure probabilities. Equivalently, $\Pr(\text{all succeed}) \ge 1 - \sum_{j=1}^{10} \Pr(\text{study } j \text{ fails})$. This is exactly what answer A does. Each study contributes a two-sided failure bound of $2\exp(-4)$, so summing across all ten studies gives a total failure bound of $10 \cdot 2\exp(-4) = 20\exp(-4)$. The resulting lower bound is $1 - 20\exp(-4) \approx 0.634$. Critically, the union bound requires no assumptions about dependence across studies — and the passage explicitly states that dependence is unrestricted, making this the only approach that works directly from the given inequalities. Answer B is tempting but invalid: multiplying individual success probabilities $(1 - 2\exp(-4))^{10}$ assumes the ten studies are independent, which is not given and cannot be assumed. Answer C uses $1 - 10\exp(-4)$, which would be correct only if each bound were $\exp(-4)$ (one-sided). But Hoeffding's inequality as stated already accounts for both tails, giving $2\exp(-4)$ per study — so this answer quietly drops a factor of 2. Answer D reports the guarantee for a single representative study, ignoring the joint requirement across all ten — a straightforward scope error. The key strategy: when asked for a joint guarantee with unrestricted dependence, reach immediately for the union bound. Independence-based product formulas are a classic trap when dependence is unspecified.
2. Which interval contains exactly all possible values of the probability that at least one procedure produces an alarm?
   Answer: $[0.45,0.50]$, because the unknown triple intersection can range from $0$ through $0.05$. Whenever you see a union-of-events problem with missing intersection information, your first move should be the inclusion-exclusion formula. For three events: $P(A \cup B \cup C) = P(A)+P(B)+P(C) - P(A\cap B) - P(A\cap C) - P(B\cap C) + P(A\cap B\cap C)$ Plugging in the known values — each marginal is $0.20$ and each pairwise intersection is $0.05$ — you get: $P(A \cup B \cup C) = 3(0.20) - 3(0.05) + P(A\cap B\cap C) = 0.45 + P(A\cap B\cap C)$ Now the key question: what values can $P(A\cap B\cap C)$ take? The triple intersection must be non-negative, so its lower bound is $0$. It also cannot exceed any pairwise intersection, and each pairwise probability is $0.05$, so its upper bound is $0.05$. Therefore $P(A\cup B\cup C)$ ranges over $[0.45, 0.50]$, confirming D is correct. A is wrong because it ignores the triple intersection term entirely and misapplies the direction of its effect — the triple intersection adds back probability, it doesn't subtract further. B incorrectly identifies $0.60$ as an upper endpoint; that would be the naïve sum $3(0.20)$ before subtracting any overlaps. The actual upper bound is $0.50$, not $0.60$. C invents a constraint — there is no rule forcing the triple intersection to equal one of the pairwise values. This is a fabricated condition with no probabilistic basis. Your strategy: always write out the full inclusion-exclusion formula before evaluating any answer choice. The unknown quantity's valid range directly determines the interval, so bounding it with basic probability axioms (non-negativity and monotonicity) is the decisive step.
3. Which conclusion is guaranteed about the probability that no monitoring rule ever issues an alarm?
   Answer: It is at least $1-\alpha$, because the countable union of alarm events has probability at most $\alpha$. Whenever you see a problem involving an infinite collection of events with bounded probabilities, your first instinct should be to reach for Boole's Inequality (the union bound): for any countable collection of events, regardless of their dependence structure, $\Pr\!\left(\bigcup_{k=1}^{\infty} A_k\right) \le \sum_{k=1}^{\infty} \Pr(A_k)$. Here, summing the individual bounds gives $\sum_{k=1}^{\infty} \frac{\alpha}{2^k} = \alpha \cdot \frac{1/2}{1 - 1/2} = \alpha$. So the probability that at least one alarm fires is at most $\alpha$, which means the probability that no alarm ever fires satisfies $\Pr\!\left(\bigcap_{k=1}^{\infty} A_k^c\right) = 1 - \Pr\!\left(\bigcup_{k=1}^{\infty} A_k\right) \ge 1 - \alpha$. That confirms C is correct. A is wrong because it fixates on only the first term $\alpha/2$, ignoring the contributions of all subsequent alarm events. The complement of the union involves all events, not just $A_1$. B is wrong because the product formula $\prod_{k=1}^{\infty}(1-\alpha/2^k)$ holds only when the events are independent. The problem explicitly states events may be arbitrarily dependent, so independence cannot be assumed and this formula is invalid. D is wrong because Boole's Inequality extends naturally to countably infinite collections — it is not restricted to finite unions. A positive lower bound of $1 - \alpha$ is entirely valid here. Study tip: On exam questions involving infinite sequences of error-prone events, always check whether the individual probabilities form a convergent series. If they do, the union bound gives you a finite, usable guarantee — even under full dependence.
4. What is the smallest integer sample size guaranteed by these inequalities and the union bound to make the probability that every estimator is within $0.5$ of its target at least $0.95$?
   Answer: $54$, obtained by requiring the sum of the 20 two-sided tail bounds to be at most $0.05$. When you see a question combining tail bounds with a union bound, your goal is to control the probability that any estimator fails. Since the estimators may be dependent, the union bound is the right tool: $\Pr(\text{any } |\widehat\theta_j - \theta_j| \ge 0.5) \le \sum_{j=1}^{20} \Pr(|\widehat\theta_j - \theta_j| \ge 0.5)$. Each individual bound is already two-sided, giving $\Pr(|\widehat\theta_j - \theta_j| \ge 0.5) \le 2e^{-n/8}$. Summing over all 20 estimators, you need $20 \cdot 2e^{-n/8} \le 0.05$. Solving: $e^{-n/8} \le \frac{0.05}{40} = 0.00125$, so $n \ge 8\ln(800) \approx 8 \times 6.685 \approx 53.48$. The smallest integer satisfying this is $n = 54$, confirming B is correct. Choice A is wrong because it ignores the factor of 2 already present in each two-sided bound. The individual bound is $2e^{-n/8}$, not $e^{-n/8}$, so dropping that factor underestimates the required sample size, leading to insufficient coverage. Choice C incorrectly doubles the bound a second time, as if the two-sided nature needed to be accounted for again after applying the union bound. The factor of 2 is already embedded in each term — you must not apply it twice. Choice D halves the exponent (using $e^{-n/16}$ effectively), which has no probabilistic justification. Dependence is handled by the union bound itself — no adjustment to the exponent is needed. Study tip: Always read the given tail bound carefully. If it's already two-sided (i.e., has the factor of 2 included), do not introduce another factor of 2 when applying the union bound.
5. What is the largest universal lower bound, based only on the stated information, for the probability that all 60 intervals simultaneously cover their respective coefficients?
   Answer: $0.40$, because the total probability of at least one noncoverage is at most $0.60$. Whenever you see a question about simultaneous coverage of multiple confidence intervals, your first instinct should be to reach for Bonferroni's inequality (the union bound), not independence assumptions. The key tool here is the Boole/Bonferroni inequality: for any events $E_1, \ldots, E_n$, regardless of their dependence structure, $P\!\left(\bigcap_{i=1}^n E_i\right) \geq 1 - \sum_{i=1}^n P(E_i^c).$ Each interval fails to cover with probability at most $1 - 0.99 = 0.01$. Summing across all 60 intervals, the total probability of at least one noncoverage event is bounded above by $60 \times 0.01 = 0.60$. Therefore, the probability that all intervals cover simultaneously is at least $1 - 0.60 = 0.40$. This bound holds under any dependence structure, making it a true universal lower bound — confirming C. A is wrong because multiplying marginal coverages assumes independence. The problem explicitly states no dependence assumptions are made, so $0.99^{60}$ is not a valid universal bound — it could be too low or too high depending on the actual dependence. B is wrong because $0.99$ describes each marginal coverage probability, not the joint coverage probability. Reporting a single interval's guarantee says nothing directly about whether all 60 succeed together. D is wrong because Bonferroni's inequality works for any dependence structure — it doesn't require independence. The bound of $0.40$ is always valid, so a positive simultaneous-coverage guarantee is absolutely achievable. Study tip: When a problem says "no assumptions about dependence," that's your signal to use Bonferroni. The formula $P(\text{all}) \geq 1 - \sum P(E_i^c)$ is assumption-free and appears frequently in multiple-testing questions.
6. Which statement correctly compares the exact probability of at least one false alarm with the union-bound estimate?
   Answer: The exact probability is $1-0.99^{30}\approx 0.260$, while the union bound gives the valid upper bound $0.30$. When you see a problem involving the probability of at least one event across many independent trials, you should immediately think about two tools: the exact complement rule and the union bound (Boole's inequality). The exact probability of at least one false alarm among 30 independent checks is found via the complement: $P(\text{at least one}) = 1 - P(\text{none}) = 1 - 0.99^{30} \approx 1 - 0.740 = 0.260.$ The union bound states that $P\!\left(\bigcup_{i=1}^n A_i\right) \leq \sum_{i=1}^n P(A_i),$ giving $30 \times 0.01 = 0.30.$ Since the union bound is always a valid upper bound, and $0.260 < 0.30$, answer B is correct — the exact probability is $1 - 0.99^{30} \approx 0.260$ and the union bound $0.30$ sits above it. A reverses the roles, incorrectly labeling $0.30$ as the exact probability and calling the union bound smaller, which contradicts the inequality — the union bound is always $\geq$ the exact probability, never smaller. C confuses the probability of no false alarm ($0.99^{30} \approx 0.740$) with the probability of at least one, and incorrectly calls the union bound a lower bound — it is always an upper bound. D is a common misconception: independence does not make the union bound exact. The union bound is tight only when events are mutually exclusive, not when they are independent. Study tip: Always remember — the union bound $\sum P(A_i)$ overestimates because it double-counts overlaps. Independence reduces those overlaps but does not eliminate them, so the bound remains strict whenever $n \geq 2$.
7. Without additional assumptions about dependence or the selection rule, which upper bound is guaranteed for the probability that the selected model has the specified failure?
   Answer: $0.50$, because failure of the selected model implies failure of at least one examined candidate. When a data-dependent rule selects among many candidates, you're dealing with a union-bound / multiple-comparisons problem. The key insight is that the selected model must be one of the 500 candidates examined, so any failure of the selected model implies that at least one of those 500 candidates failed. This is exactly the logic behind D. Formally, let $F_{\widehat{k}}$ be the event that the selected model fails, and let $F_k$ be the failure event for candidate $k$. Since $\widehat{k} \in \{1, \ldots, 500\}$, we have $F_{\widehat{k}} \subseteq \bigcup_{k=1}^{500} F_k$. Applying the union bound: $P(F_{\widehat{k}}) \leq P\!\left(\bigcup_{k=1}^{500} F_k\right) \leq \sum_{k=1}^{500} 0.001 = 0.50.$ No assumptions about independence or the selection rule are needed — just the union bound, which always holds. A is wrong because it confuses marginal guarantees with post-selection guarantees. The fixed-$k$ bound of $0.001$ applies before selection; once you pick $\widehat{k}$ data-dependently, the marginal guarantee no longer applies to the chosen model without further argument. B is wrong because it assumes the failure events are independent, which is an additional assumption not given in the problem. The formula $1-(0.999)^{500}$ is valid only under independence. C is wrong and overly pessimistic. The union bound still provides a nontrivial guarantee ($0.50$) even under arbitrary dependence and arbitrary selection rules. Your study tip: whenever you see data-dependent selection over $m$ candidates each with failure probability $\delta$, your default tool is the union bound giving $m\delta$ — no independence required.
8. Approximately what is the smallest value of $t$ for which these bounds guarantee $\Pr\left(\max_{1\le j\le 100}(Y_j-\mathbb E[Y_j])<t\right)\ge 0.95$?
   Answer: $1.95$, obtained by requiring $100\exp(-2t^2)\le 0.05$. Whenever you see a question about controlling the maximum of many random variables, your instinct should be the union bound (Boole's inequality): for any events $A_1, \ldots, A_n$, we have $\Pr(A_1 \cup \cdots \cup A_n) \le \sum_{j=1}^n \Pr(A_j)$, and crucially, this holds regardless of dependence structure among the variables. Here, you want $\Pr\!\left(\max_j (Y_j - \mathbb{E}[Y_j]) \ge t\right) \le 0.05$. The event that the max exceeds $t$ is exactly the union of the 100 individual exceedance events. Applying the union bound gives $\Pr\!\left(\max_j (Y_j - \mathbb{E}[Y_j]) \ge t\right) \le \sum_{j=1}^{100} \exp(-2t^2) = 100\exp(-2t^2)$. Setting this at most $0.05$ yields $\exp(-2t^2) \le 0.0005$, so $2t^2 \ge \ln(2000)$, giving $t \approx \sqrt{\ln(2000)/2} \approx 1.95$. This is exactly answer C. Choice A sets a single exponential equal to $1/100 = 0.01$, which would control just one tail at the $1\%$ level — it ignores that you must account for all 100 variables simultaneously and is too small. Choice B is a distractor suggesting some partial allocation of error probability that doesn't correspond to any standard bounding procedure — it's numerically between A and C without a coherent justification. Choice D applies a two-sided correction that isn't called for here; the problem specifies a one-sided bound, so there's no need to double the tail probability. The key study tip: when variables are possibly dependent, the union bound is often your only tool — you cannot assume independence to multiply probabilities. Always check whether the problem specifies dependence before reaching for sharper bounds.
9. Using only Chebyshev's inequality and the union bound, what is the smallest integer $n$ that guarantees $\Pr\left(\max_{1\le j\le 12}|\overline X_j-\mu_j|<0.2\right)\ge 0.90$?
   Answer: $12000$, because the union of the 12 deviation events has probability at most $1200/n$. When you need to control the maximum of several estimation errors simultaneously, you must account for every estimator — and that's exactly where the union bound enters. Start with Chebyshev's inequality applied to a single estimator: since $\operatorname{Var}(\overline X_j) \le 4/n$, we have $\Pr(|\overline X_j - \mu_j| \ge 0.2) \le \frac{4/n}{(0.2)^2} = \frac{100}{n}.$ Now, the event $\{\max_j |\overline X_j - \mu_j| \ge 0.2\}$ is precisely the union of the 12 individual deviation events. The union bound (Boole's inequality) gives $\Pr\!\left(\max_j |\overline X_j - \mu_j| \ge 0.2\right) \le 12 \cdot \frac{100}{n} = \frac{1200}{n}.$ For this to be at most $0.10$ (so that success probability $\ge 0.90$), you need $n \ge 1200/0.10 = 12000$. Answer A is correct. Choice B is wrong because splitting each event into "two one-sided events" doesn't reduce the bound — it's the same event viewed differently, and misapplying this idea would incorrectly halve the required $n$. Choice C is wrong because the factor of 12 cannot be absorbed into the confidence level; the union bound explicitly multiplies the per-event probability by 12, independent of your target confidence. Choice D is wrong because controlling each estimator individually at 90% confidence does not control their maximum — you'd need each to succeed simultaneously, requiring a much stricter per-estimator guarantee. Study tip: On problems involving simultaneous guarantees across multiple events, always apply the union bound first, then solve for $n$. Forgetting the multiplier (here, 12) is the most common error on these questions.
10. What is the smallest upper bound on $\Pr(V\ge 2)$ that follows from the stated marginal guarantees and a first-moment concentration argument?
    Answer: $0.20$, because $\mathbb{E}[V]\le 200(0.002)=0.40$ regardless of dependence, and Markov's inequality gives $\Pr(V\ge 2)\le \mathbb{E}[V]/2\le 0.20$. When a question asks for a bound on $\Pr(V \ge k)$ under arbitrary dependence, your first instinct should be Markov's inequality: for any non-negative random variable, $\Pr(V \ge k) \le \mathbb{E}[V]/k$. This is the "first-moment concentration argument" the question references, and it requires only knowledge of the mean — no independence, no distributional assumptions. Here, by linearity of expectation, $\mathbb{E}[V] \le 200 \times 0.002 = 0.40$ regardless of how the rejection indicators depend on one another. Applying Markov's inequality with $k = 2$ gives $\Pr(V \ge 2) \le 0.40/2 = 0.20$. That's answer C, and it's the tightest bound derivable from marginal probabilities alone under arbitrary dependence. Answer A conflates two different events. The union bound gives $\Pr(V \ge 1) \le 0.40$, but the event $\{V \ge 2\}$ is strictly smaller than $\{V \ge 1\}$, so applying that same bound to $\Pr(V \ge 2)$ is valid but wasteful — it's looser than the Markov bound and not what the question asks for. Answer B squares the union-bound value, as if 0.40 were an independent per-event probability. This is statistically incoherent: the union bound is already a probability over all 200 tests jointly, not a per-test figure you can raise to a power. Answer D assumes a binomial model, which requires independence among the rejection indicators — an assumption explicitly ruled out by the problem's "arbitrarily dependent" condition. Study tip: On problems involving dependence and tail probabilities, Markov's inequality is almost always the right tool — it needs only $\mathbb{E}[V]$, which linearity of expectation delivers even under dependence.

Start this quiz