CMP.9:5 - Archetypal Grounding

CMP.9:5.1 - Keep one uniform record from a stream of unknown length

Store the first record. At record t, replace the stored record with probability 1/t; otherwise retain it. Use a uniform integer in 1 through t to make this decision.

After t records, the new record has probability 1/t. Every earlier record had probability 1/(t-1) before this step and survives with probability (t-1)/t, giving 1/t as well. This establishes the invariant inductively. The procedure needs one record, a counter, and one update decision per arrival; counter and record representation costs remain visible.

For the stream A, A, B, the resulting value is A with probability 2/3 and B with probability 1/3. This is correct uniform sampling of record positions. If the new request is uniform sampling of distinct values, the old invariant answers a different question. One construction keeps a set of already seen values and applies the same update only on a first occurrence. That requires storage for the distinct-value set or another algorithm with its own access and error assumptions.

CMP.9:5.2 - Concentrate draws without changing an expectation

The target is the mean of values 0,0,0,4 under the uniform law on four identifiable outcomes, so μ=1. Direct draws have variance 3 per contribution.

Choose proposal probabilities q=(1/8,1/8,1/8,5/8), concentrating effort on the nonzero contribution. The corrected value on outcome 4 is 4*(1/4)/(5/8)=8/5; the other corrected values are zero. Its expectation is (5/8)*(8/5)=1, and its variance is (5/8)*(8/5)²-1=3/5. At the same number of independent draws, this construction reduces variance by a factor of five; the proposal and weighting cost decide the actual work benefit.

Using the unweighted sample mean instead has expectation (5/8)*4=5/2, the wrong target. Increasing the sample count would concentrate that wrong answer. If the required statistic changes to a different function on the four outcomes, retain the proposal only after recomputing its support, corrections and variation for that function.

CMP.9:5.3 - Correct a local walk before using it as a sampler

Sample uniformly from three states connected in a path, 0—1—2. A walk that chooses an adjacent state uniformly spends stationary probabilities (1/4,1/2,1/4): the middle state has twice as many incident choices. Uniform selection among neighbors does not imply uniform selection among visited states.

Correct a proposed move x to y by accepting it with probability

min(1, π(y)*q(x|y)/(π(x)*q(y|x))),

where π is the target and q the proposal probability. A rejection retains x. For positive target weights on connected states, the probability flow on either direction of an edge becomes the same minimum of the two proposed flows, so detailed balance holds. Normalizing constants cancel in the ratio.

For this uniform target, accept an end-to-middle move with probability 1/2 and a middle-to-end move with probability 1. The transition matrix, in state order 0,1,2, is

1/2  1/2   0
1/2   0   1/2
 0   1/2  1/2

Its rows and columns each sum to one, so the uniform law is stationary. The finite chain is connected and has self-transitions, hence converges from any start. Its other eigenvalues are 1/2 and -1/2; for this small matrix, powers give an explicit decreasing transient. For instance, starting at 0 gives (1/2,1/2,0) after one step and (1/2,1/4,1/4) after two, still not uniform.

If the three target weights change to (1,2,1), the original uncorrected neighbor walk has that stationary law. Reusing the former uniform-target acceptance probabilities would now be wrong. In either case, adjacent states are dependent observations; an independent-draw variance formula cannot be justified by the stationary law alone.