Why finite calculations need a limit
A question about infinitely many trials often has a finite approximation. For instance, the event that a success ever occurs is the union of the events that a success occurs in the first trials. Those events increase with . To pass from their probabilities to the probability of the union, we need a theorem, not an assumption that probabilities commute with every set operation.
For events , write when for every and . Similarly, means and . These are statements about membership of outcomes, not merely inequalities between numbers .
Theorem 24.1.1
(Continuity of probability)
If , then . If , then .
Proof
(Disjoint pieces of an increasing union)
Set and for . The are pairwise disjoint, their union is , and their first terms have union . Countable additivity therefore gives
For decreasing events, by De Morgan's law. Apply the increasing case and . The finiteness matters in this complement argument; a general infinite measure need not be continuous from above without a finite-measure assumption.
Proof X-ray
Where nesting and finite mass are used
The proof of continuity from below uses only countable additivity, and it uses nesting exactly once: because , the differences are disjoint and the first of them reassemble . The key move is to read as a partial sum of a series of nonnegative terms, so that the limit exists and equals the full sum, which is . Without nesting there are no such pieces, and the counterexample below shows that no limit statement survives.
Continuity from above is reduced to the increasing case by complements, and this reduction is where enters: the identity needs a finite total mass. Under length measure on the real line, the sets decrease to the empty set although each has infinite length, so continuity from above fails there.
Worked example 24.1.2
(The first success)
Suppose independent trials have success probabilities , possibly varying with . Let be the event of at least one success by time . Its complement is failures, so
The product limit exists because its terms lie in and decrease. For a fixed , the limit is zero and eventual success has probability one. That does not give a deterministic deadline: for , every finite still has failure probability .
Common mistake
(Probability one is not certainty)
An event of probability one need not equal the entire sample space. In the infinite fair-coin sequence model, the single sequence of all tails is possible, but its probability is at most for every and hence is zero. “Almost surely” permits exceptional outcomes; it does not mean that the exceptions are logically impossible.
The decreasing-event result also underlies the limit arguments in the note on convergence modes and strong laws. The note on the Borel–Cantelli lemmas treats the different question of events occurring infinitely often through the limsup construction.
Bounds for countably many events
Theorem 24.1.3
(Countable union bound)
For any events ,
The right side may be infinite. No independence is required.
Proof
(Disjointification)
Let and . These disjoint events have the same union as the , and . Countable additivity and monotonicity give the bound.
Applied to complements, the bound also gives
although a negative lower bound says nothing beyond nonnegativity. If each has probability one, the intersection also has probability one. The word “countable” matters: for a uniform on , each event has probability one, but their intersection over all is empty.
Counterexample mode
A limit of probabilities is not enough
On with uniform probability, let and . Every , yet has probability one and has probability zero. The continuity theorem requires nested events, not simply convergent probabilities.
Counting overlap exactly
Theorem 24.1.4
(Inclusion–exclusion)
For finitely many events ,
The first sum adds individual probabilities, the second subtracts pairwise overlaps, the third restores triple overlaps, and so on.
Proof
(Counting one outcome at a time)
Fix one outcome belonging to exactly of the events. If , both sides contribute zero. If , its coefficient on the right is
by the binomial identity . Thus the corresponding indicator identity holds for every outcome. Taking expectations of this finite sum proves the formula.
Independence is unnecessary; the intersection probabilities must come from the stated model. An infinite alternating series cannot be substituted without an additional convergence argument.
Worked example 24.1.5
(At least one fixed point)
A permutation of three labeled objects is selected uniformly from the six permutations. Let be the event that object remains in its original position. Each , each pairwise intersection has probability , and the triple intersection also has probability . Consequently
The remaining two permutations have no fixed points. The three are not independent: knowing two objects are fixed forces the third to be fixed.
Worked example 24.1.6
(Fixed points of a random permutation of four objects)
For a uniformly random permutation of labeled objects, fixing every object in a set leaves permutations, so . There are sets of size , and . Inclusion–exclusion therefore gives
For this is , so of the permutations have a fixed point and have none. Stopping after the first two sums would give , which is not the answer: every term of the finite formula is needed. For the formula returns the value of the previous example.
Common mistake
(Adding probabilities of overlapping events)
In the three-object example, adding the individual probabilities gives , which would assert that every permutation fixes some object. The two cyclic permutations fix nothing, and the correct value subtracts the overlaps. The sum is only an upper bound; it equals the probability of the union exactly when all pairwise intersections have probability zero.
Exercises
Quick check
(Let under the uniform law on . Identify the intersection and compute its probability using continuity from above.)
Solution · Answer
The intersection is empty: any eventually exceeds , while is never included. The events decrease and , so continuity gives probability zero.
Quick check
(Events satisfy for . Bound the probability that at least one occurs, and the probability that none occurs. Must they be independent?)
Solution · Answer
The geometric series sums to . The union bound gives , so its complement has probability at least . No independence is needed.
Quick check
(Three events have , all pairwise intersections have probability , and the triple intersection has probability . Find the probability that at least one occurs. Does the result use an assumption of independence?)
Solution · Answer
Inclusion–exclusion gives . The supplied intersection probabilities suffice; the formula itself does not assume independence.
Quick check
(Independent trials have . Find the probability of no success in the first trials and the probability of eventual success.)
Solution · Answer
The product telescopes: . Continuity gives probability zero for no success ever, so eventual success has probability one. Each finite failure probability is positive.