Why can a running average settle while each observation stays random?

Predict whether the next observation can move an already-close mean farther away. Then switch between Bernoulli, uniform, and exponential sources: what should the target line represent?

Intuition: a sum grows, but each new contribution gets diluted

A new observation enters the mean with weight $1/m$ at step $m$. Early observations can move it dramatically; later ones usually have less influence. Random fluctuations continue, but averaging independent information can make their collective effect smaller.

This is a statement about averages. Individual observations do not converge to the population mean: a fair Bernoulli draw remains either $0$ or $1$ even after a million earlier draws. The running mean is a distinct variable built from the complete prefix.

Definition

For independent identically distributed observations $X_1,X_2,\ldots$ with $\mathbb E[|X_1|]<\infty$, write $\mu=\mathbb E[X_1]$ and

The strong Law of Large Numbers states that $\bar X_m\to\mu$ almost surely. In words, convergence holds on an event of probability one in the ideal infinite iid experiment. It does not require each finite error to decrease or give a deterministic sample size that makes every possible path accurate.

A weaker convergence-in-probability statement is enough for many applications: for every fixed $\varepsilon>0$, $\mathbb P(|\bar X_m-\mu|>\varepsilon)\to0$. The finite-variance argument below shows this weak statement under a stronger moment assumption.

Mechanics: actual observations, explicit seed

The explorer’s Bernoulli source has success probability $p$, entered as a percent. Its mean and variance are $p$ and $p(1-p)$ when $p$ is expressed as a probability. Uniform draws on $[0,1)$ have mean $1/2$ and variance $1/12$. Exponential rate-$1$ draws have mean and variance $1$ and are visibly skewed rather than Gaussian.

The canonical run uses Bernoulli probability $1/4$ (25 percent), seed $42$, and $200$ trials. Set a uint32 seed and a trial count from $1$ to $4000$. Replay regenerates the same observations; every prefix mean comes from those observations. Reset restores the canonical source, seed, and count. The short and large presets use $10$ and $2000$ trials; the maximum uses $4000$. The trace inspects finite prefixes rather than replacing them with idealized trajectories.

The explicit pseudo-random generator updates integer state by $(1664525s+1013904223)\bmod 2^{32}$ and divides by $2^{32}$. Bernoulli draws compare the result with $p$; uniform draws use it directly; exponential draws apply $-\log(1-u)$. A deterministic pseudo-random stream is a simulation device, not a mathematical proof of independence or a source of cryptographic randomness.

Derivation: shrinking variance of the mean

For finite variance $\sigma^2$ and independent observations, the covariance terms vanish:

Thus the standard deviation of a repeated-sample mean is $\sigma/\sqrt m$. Chebyshev’s inequality gives

This bound tends to zero for fixed positive $\varepsilon$, establishing convergence in probability in this finite-variance case. It is a probability bound over repetitions; it does not prohibit a particular run from exceeding a chosen error or prove the stronger almost-sure statement by itself.

Worked examples

For the hand sequence $[1,0,1,1]$, prefix sums are $1,1,2,3$ and means are

Against a fair Bernoulli mean $1/2$, the absolute errors are $1/2,0,1/6,1/4$. The last two errors increase. That finite behavior is fully compatible with the LLN.

For Bernoulli probability $1/4$, population variance is $3/16$. At $m=100$, the mean variance is $3/1600$ and its standard deviation is $\sqrt3/40\approx0.0433012701892$. Four times as many independent observations halve this standard deviation. They do not guarantee half the realized error in a particular path.

With seed $42$ and Bernoulli probability $1/2$, the first three LCG-generated observations are $[1,1,0]$, giving means $[1,1,2/3]$. This is a replay check, separate from the hand sequence above.

Executable reference code

The standard-library program explicitly implements the seed transition, stores observations, and calculates actual running sums. Assertions check literal generator states, first observations, replay, deterministic Bernoulli boundaries, trial bounds, and a nonmonotone hand path.

The NumPy version exposes the same stream and uses cumsum divided by prefix lengths. Neither program asserts that a final simulated error must be small: favorable-run acceptance would confuse a statistical theorem with a selected outcome.

"""Seeded observations and actual prefix means; a finite path is not a proof."""
from math import log1p, sqrt


def uniforms(seed):
    if type(seed) is not int or not 0 <= seed <= 0xffffffff:
        raise ValueError("Seed must be a uint32 integer")
    state=seed
    while True:
        state=(1664525*state+1013904223)&0xffffffff
        yield state/4294967296


def population(source, p=50):
    if source not in ('bernoulli','uniform','exponential'):
        raise ValueError("Unknown population")
    if isinstance(p,bool) or not isinstance(p,(int,float)) or not 0 <= p <= 100 or abs(p*100-round(p*100))>1e-8:
        raise ValueError("Probability percent must be in [0,100] with at most two decimals")
    q=p/100
    mean,variance={'bernoulli':(q,q*(1-q)),'uniform':(.5,1/12),'exponential':(1.,1.)}[source]
    draw=lambda u: float(u<q) if source=='bernoulli' else u if source=='uniform' else -log1p(-u)
    return mean,variance,draw


def experiment(source='bernoulli', p=25, seed=42, trials=200):
    if type(trials) is not int or not 1<=trials<=4000:
        raise ValueError("Trials must be an integer in [1,4000]")
    mean,variance,draw=population(source,p)
    rng=uniforms(seed)
    observations=[]
    means=[]
    scales=[]
    total=0.
    for m in range(1,trials+1):
        value=draw(next(rng))
        observations.append(value)
        total+=value
        means.append(total/m)
        scales.append(sqrt(variance/m))
    return observations,means,scales,mean,variance


def main():
    rng=uniforms(42)
    assert [next(rng)*4294967296 for _ in range(3)] == [1083814273,378494188,2479403867]
    result=experiment(p=50,trials=3)
    assert result[0]==[1.,1.,0.] and result[1]==[1.,1.,2/3]
    assert result == experiment(p=50,trials=3)
    assert experiment(p=0,trials=4)[1]==[0.]*4
    assert experiment(p=100,trials=4)[1]==[1.]*4
    values=[1,0,1,1]
    prefix=[sum(values[:m])/m for m in range(1,5)]
    assert prefix==[1,.5,2/3,.75]
    assert abs(prefix[2]-.5)>abs(prefix[1]-.5)  # LLN does not promise monotone error.
    for source in ('bernoulli','uniform','exponential'):
        observations,means,scales,mean,variance=experiment(source,trials=4000)
        assert len(observations)==len(means)==len(scales)==4000
        assert abs(means[-1]-sum(observations)/4000)<1e-14
        assert abs(scales[-1]**2-variance/4000)<1e-14
    for kwargs in ({'trials':0},{'trials':4001},{'seed':-1},{'source':'cauchy'},{'p':100.01}):
        try:
            experiment(**kwargs)
        except ValueError:
            pass
        else:
            raise AssertionError("Invalid experiment accepted")
    print("First observations and means:",result[:2])
    print("σ/√m is a theoretical repeated-mean scale, not a guaranteed error bound.")
    print("The iid finite-mean LLN is an asymptotic theorem; an LCG run illustrates it.")


if __name__=='__main__':
    main()

"""Vectorized prefix sums with the book's explicit uint32 seed contract."""
import numpy as np
from math import log1p, sqrt


def uniforms(seed):
    if type(seed) is not int or not 0 <= seed <= 0xffffffff:
        raise ValueError("Seed must be a uint32 integer")
    state=seed
    while True:
        state=(1664525*state+1013904223)&0xffffffff
        yield state/4294967296


def population(source, p=50):
    if source not in ('bernoulli','uniform','exponential'):
        raise ValueError("Unknown population")
    if isinstance(p,bool) or not isinstance(p,(int,float)) or not 0 <= p <= 100 or abs(p*100-round(p*100))>1e-8:
        raise ValueError("Probability percent must be in [0,100] with at most two decimals")
    q=p/100
    mean,variance={'bernoulli':(q,q*(1-q)),'uniform':(.5,1/12),'exponential':(1.,1.)}[source]
    draw=lambda u: float(u<q) if source=='bernoulli' else u if source=='uniform' else -log1p(-u)
    return mean,variance,draw


def experiment(source='bernoulli',p=25,seed=42,trials=200):
    if type(trials) is not int or not 1<=trials<=4000:
        raise ValueError("Trials must be an integer in [1,4000]")
    mean,variance,_=population(source,p)
    u=np.fromiter(uniforms(seed),dtype=float,count=trials)
    x=(u<p/100).astype(float) if source=='bernoulli' else u if source=='uniform' else -np.log1p(-u)
    m=np.arange(1,trials+1)
    return x,np.cumsum(x)/m,np.sqrt(variance/m),mean,variance


def main():
    x,means,scales,mu,variance=experiment(p=50,trials=3)
    np.testing.assert_array_equal(x,[1,1,0])
    np.testing.assert_allclose(means,[1,1,2/3],rtol=0,atol=1e-14)
    np.testing.assert_array_equal(experiment(p=50,trials=3)[0],x)
    for p in (0,100):
        np.testing.assert_array_equal(experiment(p=p,trials=4)[1],np.full(4,p/100))
    for source in ('bernoulli','uniform','exponential'):
        x,means,scales,mu,variance=experiment(source,trials=4000)
        np.testing.assert_allclose(means[-1],x.mean(),rtol=0,atol=1e-13)
        np.testing.assert_allclose(scales[-1]**2,variance/4000,rtol=0,atol=1e-14)
    path=np.cumsum([1,0,1,1])/np.arange(1,5)
    assert abs(path[2]-.5)>abs(path[1]-.5)
    for kwargs in ({'trials':0},{'seed':2**32},{'source':'invalid'},{'p':float('nan')}):
        try:
            experiment(**kwargs)
        except ValueError:
            pass
        else:
            raise AssertionError("Invalid experiment accepted")
    print("Actual prefix means ≈",means[:6])
    print("cumsum exposes the path; no favorable-run selection or monotone-error guarantee.")
    print("A Cauchy source lacks the finite expectation required by this LLN version.")


if __name__=='__main__':
    main()

Explore

Hold the seed and population fixed while increasing trials. Compare shared prefixes and explain why replay must preserve them. Find a step where absolute error increases, and identify the observation that moved the average away from the target.

Switch to the skewed exponential population and compare its observations with its mean path. Change the seed to observe a different path with the same theoretical target. At Bernoulli probabilities $0$ or $1$, explain why every observation and prefix mean is deterministic and the theoretical mean spread is zero.

Common mistakes and counterexamples

The law does not promise monotone improvement, exact equality at a finite step, or predictable compensation after a streak. A fair coin that has produced many successes still has success probability $1/2$ on its next independent trial. The average can adjust without the coin remembering past imbalance.

If all observations repeat one common random variable $Y$, then $\bar X_m=Y$ at every $m$: there is no variance reduction. Common marginals alone do not supply independence. An iid Cauchy source gives a different warning: it lacks a finite absolute first moment and has no finite population mean to which this LLN version can assert convergence.

Numerical considerations

The simulation is bounded and uses the exact integer seed transition. Uniform $u$ lies in $[0,1)$, so the exponential transform never asks for $\log(0)$. The code uses log1p to evaluate $\log(1-u)$ accurately near zero. Floating observations and running means are numerical approximations, even when the model’s moments have exact rational forms.

Finite simulation length, pseudo-random generator quality, floating accumulation, and sampling variability are separate limitations. A plotted $\sigma/\sqrt m$ scale describes theoretical spread under iid assumptions. It is neither a confidence interval nor a guarantee that the observed error lies inside it; interpreting coverage requires an additional probability statement.

Engineering and ML connections

A Monte Carlo estimate averages model-generated quantities. Its target is an expectation, and independent finite-variance samples give a standard-deviation scale proportional to $1/\sqrt m$. Reaching half the scale typically requires four times the work; reducing variance can be as valuable as drawing more samples.

Training batches, simulation draws, and measured data can be dependent. Before using iid averaging intuition, inspect how examples are sampled and whether the intended expectation exists. More correlated observations need not provide the same information as more independent ones.

Exercises

Compute exact prefix means and theoretical variances. Keep those model quantities separate from one observed path’s error.

Summary and checkpoints

The iid finite-mean LLN concerns long-run averages. Check that you can construct a prefix path, identify nonmonotone deviations, derive finite-variance mean spread $\sigma/\sqrt m$, explain dependence and Cauchy warnings, and distinguish seeded illustration from theorem proof.