Statistics Graduate Level Quiz: Union Bounds And Concentration

10 questions · exam conditions

0:00

Union Bounds And ConcentrationQuestion 1 of 10

For each of 20 estimators, a two-sided concentration inequality gives $\Pr\left(|\widehat\theta_j-\theta_j|\ge 0.5\right)\le 2\exp(-n/8)$ . The estimators may be arbitrarily dependent.

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$ ?

48

, obtained by assigning the full error budget across the 20 estimators without the two-sided factor.

54

, obtained by requiring the sum of the 20 two-sided tail bounds to be at most

0.05

59

, obtained by adding an additional factor of two when combining the already two-sided bounds.

107

, obtained by halving the exponent to account for the 20 potentially dependent estimators.

← Back to quizzes

Statistics Graduate Level Quiz

Statistics Graduate Level Quiz: Union Bounds And Concentration

Practice Union Bounds And Concentration in Statistics Graduate Level with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Union Bounds And Concentration, giving you a quick way to practice the rules, question types, and explanations that matter most for Statistics Graduate Level.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

For each of 20 estimators, a two-sided concentration inequality gives $\Pr\left(|\widehat\theta_j-\theta_j|\ge 0.5\right)\le 2\exp(-n/8)$ . The estimators may be arbitrarily dependent.

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$ ?

$48$ , obtained by assigning the full error budget across the 20 estimators without the two-sided factor.
$54$ , obtained by requiring the sum of the 20 two-sided tail bounds to be at most $0.05$ . (correct answer)
$59$ , obtained by adding an additional factor of two when combining the already two-sided bounds.
$107$ , obtained by halving the exponent to account for the 20 potentially dependent estimators.

Explanation: 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.

Question 2

An estimator $\overline X_j$ is computed for each of 12 outcomes using a sample of size $n$ . Each estimator is unbiased, and $\operatorname{Var}(\overline X_j)\le 4/n$ . No restrictions are placed on dependence among the 12 estimators.

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$ ?

$12000$ , because the union of the 12 deviation events has probability at most $1200/n$ . (correct answer)
$6000$ , because each absolute-deviation event can be treated as two equally likely one-sided events.
$1200$ , because the factor of 12 is absorbed by the target confidence level of $0.90$ .
$1000$ , because controlling each estimator at confidence level $0.90$ also controls their maximum.

Explanation: 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.

Question 3

Ten studies each report the mean of 200 independent observations taking values in $[0,1]$ . Dependence across studies is unrestricted. For every study, Hoeffding's inequality gives $\Pr(|\overline X_j-\mu_j|\ge 0.1)\le 2\exp(-4)$ .

What lower bound for the probability that all ten reported means are within $0.1$ of their respective expectations follows directly from these inequalities?

$1-20\exp(-4)\approx 0.634$ , using the sum of all ten two-sided failure bounds. (correct answer)
$(1-2\exp(-4))^{10}\approx 0.689$ , using the product of the ten success probabilities.
$1-10\exp(-4)\approx 0.817$ , treating the supplied bounds as though they were one-sided.
$1-2\exp(-4)\approx 0.963$ , using the concentration guarantee for a representative study.

Explanation: 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.

Question 4

A researcher reports marginal confidence intervals for 60 regression coefficients. For each coefficient, the interval has coverage probability at least $0.99$ . No assumptions are made about dependence among the coverage events.

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?

$0.99^{60}$ , because simultaneous coverage is the product of the marginal coverages.
$0.99$ , because every interval has at least that marginal coverage probability.
$0.40$ , because the total probability of at least one noncoverage is at most $0.60$ . (correct answer)
$0$ , because arbitrary dependence precludes any positive simultaneous-coverage guarantee.

Explanation: 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.

Question 5

Three diagnostic procedures produce alarm events $A$ , $B$ , and $C$ . Their marginal probabilities are all $0.20$ , and each pairwise intersection has probability $0.05$ . No value is given for the triple intersection.

Which interval contains exactly all possible values of the probability that at least one procedure produces an alarm?

$[0.40,0.45]$ , because the pairwise overlaps must reduce the sum of the marginal probabilities by at least $0.15$ .
$[0.45,0.60]$ , because the first-order union bound provides the upper endpoint and pairwise subtraction provides the lower endpoint.
$[0.50,0.60]$ , because the triple intersection must equal one of the three pairwise intersection probabilities.
$[0.45,0.50]$ , because the unknown triple intersection can range from $0$ through $0.05$ . (correct answer)

Explanation: 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.

Question 6

For each of 100 possibly dependent statistics, the one-sided tail bound $\Pr(Y_j-\mathbb E[Y_j]\ge t)\le \exp(-2t^2)$ holds for every positive $t$ .

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$ ?

$1.52$ , obtained by setting a single exponential tail equal to $1/100$ .
$1.73$ , obtained by dividing the total error probability among only the upper-tail exceedances.
$1.95$ , obtained by requiring $100\exp(-2t^2)\le 0.05$ . (correct answer)
$2.30$ , obtained by applying an additional two-sided correction to every tail probability.

Explanation: 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.

Question 7

A model-selection algorithm examines 500 candidate models using the same dataset and selects an index $\widehat k$ in a data-dependent manner. For each fixed candidate $k$ , the probability that candidate $k$ has a specified severe generalization failure is at most $0.001$ .

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?

$0.001$ , because selecting a model does not change the marginal failure guarantee for each fixed candidate.
$1-(0.999)^{500}$ , because the candidate-specific failure events combine as independent trials.
$1$ , because data-dependent selection eliminates every nontrivial guarantee based on fixed candidates.
$0.50$ , because failure of the selected model implies failure of at least one examined candidate. (correct answer)

Explanation: 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.

Question 8

A countably infinite sequence of monitoring rules has alarm events $A_1,A_2,\ldots$ satisfying $\Pr(A_k)\le \alpha/2^k$ for every positive integer $k$ , where $0<\alpha<1$ . The events may be arbitrarily dependent.

Which conclusion is guaranteed about the probability that no monitoring rule ever issues an alarm?

It is at least $1-\alpha/2$ , because the largest individual alarm probability occurs at the first rule.
It equals $\prod_{k=1}^{\infty}(1-\alpha/2^k)$ , because the error allocations decrease geometrically.
It is at least $1-\alpha$ , because the countable union of alarm events has probability at most $\alpha$ . (correct answer)
No positive lower bound is available, because a union bound applies only to finitely many events.

Explanation: 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.

Question 9

In a multiple-testing procedure, let $V$ denote the number of false rejections among 200 null hypotheses. Each hypothesis has false-rejection probability at most $0.002$ , but the rejection indicators may be arbitrarily dependent.

What is the smallest upper bound on $\Pr(V\ge 2)$ that follows from the stated marginal guarantees and a first-moment concentration argument?

$0.40$ , because the union bound gives $\Pr(V\ge 1)\le 200(0.002)=0.40$ , and this bound applies directly to the event $V\ge 2$ .
$0.16$ , because the probability of two or more false rejections is bounded by $(0.40)^2$ , treating the union-bound value as a per-event probability.
$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$ . (correct answer)
Approximately $0.062$ , because modeling $V$ as a binomial random variable with mean $0.40$ determines the probability of two or more successes.

Explanation: 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.

Question 10

Thirty independent quality-control checks are performed. Under proper operation, each check has probability $0.01$ of issuing a false alarm.

Which statement correctly compares the exact probability of at least one false alarm with the union-bound estimate?

The exact probability is $0.30$ , while the union bound is $1-0.99^{30}$ and is slightly smaller.
The exact probability is $1-0.99^{30}\approx 0.260$ , while the union bound gives the valid upper bound $0.30$ . (correct answer)
The exact probability is $0.99^{30}\approx 0.740$ , while the union bound gives the lower bound $0.70$ .
The exact probability and the union bound both equal $0.30$ because the checks are mutually independent.

Explanation: 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