What does the union bound give for 200 shards each 0.1% likely to overflow this hour?
answer
- bound the union, not the individuals
- add the chances, then cap
- inequality, never an equality
- no independence assumption needed
- sum past one says nothing
basics
~20 sAt most 20%. The union bound says the chance that any bad event happens is no more than the sum of their individual chances, so 200 times 0.001 gives 0.2. It is an upper bound, and it needs no independence assumption.
solid answer
~40 sThe union bound states that for any events, `P(any of them) <= sum of P(each)`. Here that is `200 * 0.001 = 0.2`, so the chance at least one shard overflows this hour is at most 20%. The value of the bound is what it does *not* require: the shards may share a cause, a traffic spike or a rack, and the inequality still holds. Correlation only makes it looser - if all 200 shards overflow together, the true chance is 0.1% while the bound still reports 20%. It is also only an upper bound, and it becomes vacuous once the sum reaches 1: raise each shard to 1% and the sum is 2.0, which tells you nothing beyond `at most certain`.
code
pseudocode · 8 lines// upper bound on the chance that ANY bad event occurs
function union_bound(events):
total = 0
for each e in events:
total = total + probability(e) // dependence is never consulted
if total >= 1:
return 1 // vacuous: says only "at most certain"
return totalgo deeper
Recall the shape of the statement: the chance that at least one bad thing happens is no larger than the sum of the individual chances. Two hundred events at 0.1% each therefore total at most 20%.
Explain why the inequality holds - the sum counts every shared outcome more than once - and why that means no independence assumption is needed. Be able to name the case where it becomes an equality: mutually exclusive events.
Show the operational use: enumerate bad events per window, attach generous per-event estimates, and compare the sum with the error budget. Say aloud that clearing the bound proves safety while exceeding it proves nothing.
Weigh the cost of the looseness. A bound that ignores correlation can drive real over-provisioning when one shared cause dominates; decide when it is worth paying for a dependence model instead of buying headroom.
## The bound in one line For any events `A1 ... Am`, the union bound (also called Boole's inequality) says: ``` P(A1 or A2 or ... or Am) <= P(A1) + P(A2) + ... + P(Am) ``` With 200 shards each carrying a 0.001 chance of overflowing in the hour, the sum is `200 * 0.001 = 0.2`, so the probability that **at least one** of them overflows is at most 20%. That single line is most of what makes discrete probability usable in a design review, because the quantity people actually care about is almost never one component failing - it is *anything* failing. ## Why it needs no independence The reason is a counting argument, not a probabilistic one. Every outcome in the union is counted **once** on the left. On the right it is counted once for every event that contains it. So the right-hand side counts each shared outcome at least as many times as the left does, and the sum can therefore only over-state the union. Overlap is exactly what makes the bound loose; it can never make it false. This is why the union bound is the first tool to reach for when you cannot justify independence - which, in a system where shards share a network, a deployment and a traffic source, is nearly always. ## How loose is it here The true probability depends on how the 200 events relate, and it always lies between the largest single probability and the bound: | How the shard failures relate | True P(at least one) | Bound | |---|---|---| | Perfectly correlated - all overflow together | 0.001 | 0.2 | | Independent | 1 - 0.999^200 = 0.181 | 0.2 | | Mutually exclusive - at most one can overflow | 0.200 | 0.2 | The bound is **exact** only in the disjoint case. Under independence it is close here, because each term is tiny; as the individual probabilities grow the gap widens quickly. Correlation pushes the truth far below the bound, which is safe but can lead a team to over-provision for a risk that is really one shared failure. ## When the bound goes vacuous Because the right-hand side is a sum of probabilities, it can exceed 1, and a bound of "at most 2.0" is a true statement that carries no information. Raise each shard's hourly risk from 0.1% to 1% and the sum is `200 * 0.01 = 2.0`. Three honest responses: 1. **Bound a rarer event instead.** Instead of "any shard overflows", bound "three or more shards overflow", or shorten the window from an hour to a minute so each term shrinks. 2. **Use the complement where independence is defensible.** `1 - (1 - p)^m` is exact under independence and stays below 1 by construction - at the cost of an assumption the union bound never needed. 3. **Accept the answer.** A sum of 2.0 is itself a finding: with these per-shard rates, at least one overflow per hour is the expected state of the world, and the design needs a different mitigation rather than a tighter estimate. ## Using it at design time The practical procedure is short: - Enumerate the bad events explicitly - one per shard, per retry window, per dependency. Being exhaustive matters more than being precise. - Attach a per-event probability, even a crude upper estimate. Over-estimating a term keeps the bound valid, since the inequality only ever needs each term to be at least the truth. - Sum them and compare against the error budget for the period. - If the sum clears the budget, you are done, and you never argued about correlation. If it does not, you have learned that the design cannot be justified without a dependence argument. That asymmetry is the real lesson: the union bound can *prove a design safe* without any independence assumption, but it can never prove one unsafe, because the truth may sit far beneath it. ## The common mistakes - Reporting the sum as the probability rather than a ceiling. - Claiming the bound needs independent events; independence is what the *complement* formula needs. - Quoting a bound above 1 as though it were a probability. - Using it downward, as a claim that the risk is at least the sum, which the inequality never says.
- Does the bound still hold if all 200 shards would overflow for one shared reason, such as a traffic spike?Yes - it holds for any dependence whatsoever, because the sum over-counts every shared outcome. What changes is tightness, not validity. Under perfect correlation the true chance is 0.1%, the largest single term, while the bound still reports 20%. Correlation loosens the bound; it never breaks it.
- At what point does the union bound stop being usable, and what do you reach for then?Once the summed terms reach 1 the bound reduces to `at most certain`. Two hundred shards at 1% each sum to 2.0, for example. Either bound a rarer event - a shorter window, or two or more failures rather than one - or, where independence is defensible, compute the complement `1 - (1 - p)^m` exactly.
- Can the union bound tell you a design is too risky?No, and this is its defining limit. It only ever gives a ceiling, so a large value is consistent with a true risk far below it. Clearing the bound proves the design safe without any dependence argument; failing it proves nothing except that a better model is needed.
Costing a project's slip risk by adding up every task's chance of slipping gives an honest ceiling on the chance that something slips. It does not need the tasks to be unrelated - and once the total passes 100% it has simply stopped telling you anything.
saying these in an interview costs you the question
- Claims the union bound requires the events to be independent
- Adds the probabilities and reports the sum as exact
- Quotes a bound above 1 as a probability
- Thinks correlation breaks the bound instead of loosening it
- Reads the bound as a lower limit on the real risk