Bound tails and state what convergence actually means

Try

A nonnegative variable has mean 2 but no specified distribution. You cannot calculate its exact probability of exceeding 10 from that mean alone. Predict whether the mean still supplies an upper bound. Compare this distribution-free question with a normal-tail calculation, which uses much more model information.

Predict

For a finite-variance average of independent observations, predict how a bound on large deviations changes with sample size. Then distinguish two possible conclusions: the average concentrates near its mean, or its centered and scaled distribution approaches a normal shape. They are related but not the same theorem.

Experiment

Markov gives P(X≥10)≤E(X)/10=1/5 for nonnegative X. If a variable has variance 9, Chebyshev gives P(|X−EX|≥12)≤9/144=1/16. These are bounds, not generally exact probabilities; an upper bound greater than one can be replaced by the trivial bound one.

For iid observations with mean μ and variance 9, the average of n observations has variance 9/n. Thus P(|X̄_n−μ|≥1)≤9/n. At n=900 this bound is 0.01. The finite guarantee can be conservative, but it requires no normal population assumption.

Understand

Markov’s inequality follows from X≥a·1(X≥a) for X≥0 and a>0. Taking expectations gives P(X≥a)≤E(X)/a when the mean is finite. Applying Markov to the nonnegative squared deviation yields Chebyshev: P(|X−μ|≥ε)≤Var(X)/ε². The hypotheses, including nonnegativity in the first case and finite variance in the second, are essential.

Jensen’s inequality says g(E(X))≤E(g(X)) for convex g under suitable integrability and domain conditions. A supporting line at the mean lies below the convex graph; averaging that line preserves its value at the mean. For g(x)=x², Jensen yields E(X²)≥[E(X)]². Equality for strictly convex g requires degeneracy under the standard finite setting, not merely symmetry.

For iid observations with finite variance σ², Chebyshev applied to their average gives a bound σ²/(nε²) tending to zero for every fixed ε>0. This proves a weak law of large numbers: convergence in probability to μ. It does not assert that every realized running average gets closer at each step. Other laws hold under different hypotheses; the proof here establishes this particular version.

The classical iid central limit theorem assumes a finite positive variance and states that √n(X̄_n−μ)/σ converges in distribution to a standard normal variable. It concerns a standardized statistic, not individual observations becoming normal. If the population is normal, averages are exactly normal for every n; otherwise finite-n use is an approximation.

There is no universal n that ensures every CLT tail approximation is accurate. Skew, tails and the probability region matter. Dependence or infinite variance can invalidate the familiar theorem and standard-error formula. For binomial normal approximations, sufficient expected successes and failures help; a continuity correction may improve discrete-tail approximation but does not make it exact.

Almost-sure convergence, convergence in probability and convergence in distribution are distinct notions. This lesson proves only the finite-variance weak law and states the classical CLT; stronger convergence theory needs its own hypotheses and proofs.

Heterogeneous counts: an expected count is not the count

Let I₁,…,Iₙ be zero-or-one indicators with possibly different probabilities pᵢ. The random total is S=ΣIᵢ; its expected total is the fixed number μ=E[S]=Σpᵢ. Do not use the same symbol for both. Linearity gives this mean regardless of dependence. Variance is Σpᵢ(1−pᵢ) plus twice the sum of pair covariances. Pairwise independence suffices to remove those covariances; a full product distribution requires mutual independence, a stronger claim.

Can a familiar variance formula produce a false guarantee?

Predict the probability that the count S reaches the threshold. Change the joint protocol while preserving all three marginal probabilities.

P(I₁=1) 0/41/42/43/44/4 P(I₂=1) 0/41/42/43/44/4 P(I₃=1) 0/41/42/43/44/4 Protocol Independent uniform drawsOne common uniform draw Threshold 1234 Reset

Mean μ=1.5; actual variance=0.625. Sum of marginal variances=0.625; this is the total variance only when the covariance sum vanishes.

Exact tail P(S≥3)=6/64=0.09375.

P(S=0)	6/64
P(S=1)	26/64
P(S=2)	26/64
P(S=3)	6/64
Markov upper bound	0.5
Chebyshev upper bound (actual variance)	0.2777777777777778
Cantelli upper bound (actual variance)	0.21739130434782608
Candidate using independent variance (not guaranteed for common draw)	0.21739130434782608

For each marginal p, its bit is1 when its uniform draw is below p. The common protocol reuses the same draw. Exactly64 equiprobable quarter-grid triples are enumerated; in common mode the unused two coordinates merely repeat each of four effective outcomes16 times. Temporary synthetic evidence, not measured failure rates or automatic mastery.

For a positive threshold t, Markov gives P(S≥t)≤min(1,μ/t), using only S≥0. If t>μ, put a=t−μ. Chebyshev gives the valid upper bound min(1,σ²/a²), where σ² is the actual variance. Neither theorem supplies an exact probability. A bound over one may be clipped to one because probabilities cannot exceed one; a threshold at or below the mean does not meet this upper-tail Chebyshev substitution’s positive-gap hypothesis.

Derive a one-sided variance bound

Let X have finite mean μ and variance σ², and take a>0. For any s≥0, on the event X−μ≥a we have (X−μ+s)²≥(a+s)². The squared quantity is nonnegative everywhere, so taking expectations gives P(X−μ≥a)≤(σ²+s²)/(a+s)². Its expectation has no cross term because E[X−μ]=0. Choosing s=σ²/a yields P(X−μ≥a)≤σ²/(σ²+a²), called Cantelli’s inequality. This also handles σ²=0 with a positive denominator. It is no larger than the corresponding Chebyshev bound, but it still uses a correctly justified variance and need not be the best bound when the count’s support or exact law is known.

For the three marginal probabilities1/4,1/2,3/4, independence gives μ=3/2 and σ²=5/8. At threshold3, Cantelli gives5/23 while the exact independent tail is3/32. Now reuse a single uniform U and set Iᵢ=1 when U<pᵢ. The marginals are unchanged but S has probabilities1/4 at each of0,1,2,3, giving variance5/4 and exact tail1/4. Reusing5/8 in Cantelli would assert an upper bound5/23, which is less than1/4: the claimed guarantee is false. The correct variance gives5/14. Markov’s1/2 remains valid in both protocols because the common mean and nonnegativity still hold.

If only the marginal means are known for a count of n indicators, support0≤S≤n yields S²≤nS, hence Var(S)≤nμ−μ². Substituting this conservative upper variance into Cantelli is valid because v/(v+a²) increases with v≥0. This is a dependence-robust bound, not generally an exact variance or the sharpest attainable bound for the specified marginals. If t>n, the support itself proves probability zero. Keep exact laws, sufficient inequalities and their assumptions visibly separate.

Entropy inequalities with support and equality conditions

For probability vectors p,q on the same finite alphabet, use natural logarithms and define D(p∥q)=Σpᵢ ln(pᵢ/qᵢ), with zero-mass terms zero and D=∞ if some pᵢ>0 has qᵢ=0. These support conventions matter: a claimed finite answer cannot ignore an event the comparison model declares impossible.

For q positive on the support I of p, apply ln u≤u−1 to u=qᵢ/pᵢ and multiply by pᵢ. Summing yields −D≤Σᵢ∈I qᵢ−1≤0. Therefore D≥0. Equality requires qᵢ/pᵢ=1 on I and no q mass outside I, hence p=q. This proves Gibbs’ inequality, including zeros, without assuming the two supports initially coincide.

Entropy H(p)=−Σpᵢ ln pᵢ consequently satisfies H(p)≤ln m on an alphabet of m symbols: compare p with the uniform vector. Equality holds exactly for uniform p. This is a finite-alphabet statement; differential entropy has different units and can be negative.

For nonnegative aᵢ,bᵢ with A=Σaᵢ>0 and B=Σbᵢ>0, normalize pᵢ=aᵢ/A,qᵢ=bᵢ/B. Rearranging D≥0 proves the log-sum inequality Σaᵢ ln(aᵢ/bᵢ)≥A ln(A/B), with the same infinite/support conventions. When A=0 both sides are zero; when A>0,B=0 both are infinite. Equality for finite terms requires matching normalized vectors.

Change the comparison model's support

Predict whether divergence stays finite when the model assigns zero probability to a possible event. Natural logarithms give nats.

True p: 0.25 Model q: 0.20

D(Bernoulli(p) ∥ Bernoulli(q)) = 0.007382 nats. Zero-mass terms are defined by continuity; a nonzero true mass against zero model mass gives infinity.

Temporary practice only. No saved response, automatic proof grade or mastery award.

Conditioning and data processing

For finite random variables X,Y, factor p(x,y)=p(y)p(x|y) on positive-mass y. Expanding the logarithm gives H(X,Y)=H(Y)+H(X|Y), where H(X|Y) averages the conditional entropies. Also

$$I(X;Y)=D(p_{XY}\Vert p_Xp_Y)=H(X)-H(X\mid Y)\ge0.$$

Thus conditioning reduces entropy on average, with equality exactly when X,Y are independent. It need not reduce entropy at each particular observed value. For example let P(Y=0)=0.9 with X=0 certainly there, while conditional on Y=1, X is a fair bit. Then H(X)=−0.95 ln 0.95−0.05 ln 0.05≈0.1985 nats, but H(X|Y=1)=ln 2≈0.6931. The average conditional entropy is 0.1 ln 2≈0.0693, which is smaller.

For a finite Markov relation X→Y→Z, meaning p(z|x,y)=p(z|y) on supported pairs, apply the chain rule twice: I(X;Y,Z)=I(X;Y)+I(X;Z|Y)=I(X;Y), while I(X;Y,Z)=I(X;Z)+I(X;Y|Z). Conditional mutual information is an average of nonnegative divergences, so I(X;Z)≤I(X;Y). This proves the data-processing inequality with the actual conditional-independence hypothesis. An operation that also reads X does not satisfy it merely because it is called “postprocessing.”

Changed case: lossless and lossy observations

Let X be uniform on the four values 0, 1, 2, 3, Y=X mod 2, and Z=0 always. Compute H(X), I(X;Y), I(X;Z), and H(X|Y). The values are ln 4, ln 2,0,ln 2. A parity observation removes one of the two bits; deleting it removes that information. Now replace Z by X. This does not violate data processing: Z=X is not generated solely from Y in this experiment. Review criteria: calculate actual conditional laws, distinguish nats from bits (divide by ln 2), and identify the broken Markov condition rather than dismissing the inequality.

Primary comparison: MIT Information and Entropy, Spring 2008, Chapter 6, checked 30 October 2026. This proof package is finite-alphabet; infinite sums and continuous entropy require separate integrability statements.

Apply

Derive the weak-law bound step by step and state exactly what tends to zero. Then calculate the supplied CLT practice probability, labeling it approximate and naming a failure condition. For Jensen, explain why its inequality direction follows convexity rather than an assumption that averaging always increases values.

Continue

This completes an authored calculus-based probability sequence, not an independently assessed full-course claim. Measure-theoretic conditioning, stronger convergence results, characteristic functions and stochastic processes remain further study. Use an unfamiliar joint-law problem and a written theorem audit to test transfer beyond numerical answer matching.