sequential  ·  probability minimum replacement  ·  Chromy (1979)

Every unit within
one of its expectation.

Chromy's method selects units one at a time down an ordered list, each with probability proportional to its size, so that a unit expected 0.3 times is selected 0 or 1 times, a unit expected 2.4 times is selected 2 or 3 — never further — and the sample size is always exact. It is how many large surveys draw their samples, and how PROC SURVEYSELECT METHOD=PPS_SEQ works. Until now it lived inside proprietary software and one Stata module. chromy is the method in the open: one Rust engine, bound to R and Python.

install ↗ the R package site
a whole design, in R
s <- chromy_sample(frame, n = 40, size = "pupils",
                   order_by = c("region", "chromy_size"), seed = 123)

sum(s$sample$hits)                      40   # always: exact, not expected
sum(s$expected_hits)                    40
estimate_total(s, "outcome")            total 37623, SE 5010 (CV 13.3%)

The same seed gives the same sample, down to the last draw — the randomness comes from R's own generator, never from inside the engine.

the method

A walk down the list, one conditional draw per unit.

The expected hits accumulate down the ordered list. Every time the running sum crosses an integer, one selection is released; a single uniform per unit decides, conditionally on the walk so far, whether the pending selection lands here or carries forward. The conditionals are built so that each unit's hits come out with exactly the probability its expectation demands — a sequential implementation of the design, not an approximation to it.

Six units whose expected hits sum to three; the cumulative path crosses three integer levels, and each crossing releases one selection.

exact sample size

The hits sum to n in every realisation. Not on average: always.

minimum replacement

Hits are the floor or the ceiling of the expectation — a unit can be selected more than once, but never drift from what the design promised it.

implicit stratification

Units that sit together in the list are selected apart, so the sample spreads over whatever the sort keys encode.

the toolkit

The apparatus the method is used with in practice.

A selection procedure alone is half a design. Around it, the pieces the surveys that rely on Chromy's method actually use — each one a function of the engine, each one tested against the same reference.

serpentine sorting

The hierarchical sort that reverses direction at every group boundary, so the list meanders through the frame and neighbouring units are always alike. Categorical keys rank by byte order, never by locale: the same frame sorts the same way on every machine.

maximal size measure

For surveys that must estimate several totals from one sample: each unit's size is the largest of its scaled shares across the auxiliary variables (Folsom, Potter and Williams, 1987), so every variable gets at least its intended coverage.

equal-CV allocation

The factors that decide how much sample each variable commands, searched until every variable's total is anticipated with the same coefficient of variation — no estimate quietly sacrificed to another.

multiplicity estimation

The estimator that matches the design — values divided by the effective expected hits, weighted by the hits received — with the successive-difference variance read in list order, where the serpentine left genuinely similar neighbours.

one engine, three languages

The engine takes its randomness as arguments.

chromy-core has no dependencies and no generator: the uniforms arrive as arguments, so a selection is a pure function of its inputs. R draws them with R's generator — which is why set.seed() reproduces the original prototype draw for draw — and Python draws them from a documented seed. Three languages, one arithmetic, one reference.

A frame with sizes and the caller's uniforms go into chromy-core, used from Rust, from R as the package chromy, and from Python as pychromy; golden tests pin all three to one reference.

R · chromy

Data frames in, tibbles out; the whole design in one call; four vignettes from the walk to the validation.

package site ↗

Python · pychromy

Lists of columns in, dicts of parallel lists out — nothing to install besides the wheel; pandas optional by construction.

package site ↗

Rust · chromy-core

The engine itself, for a production system that draws its own samples; slices in, structs out.

docs.rs ↗

fidelity

Floating point is part of the design.

Expected hits that should sum to an integer rarely do in doubles, and a remainder that lands at 1 − 10−16 either is or is not a crossing — the answer changes who can be selected. The engine measures the drift with compensated summation, refuses it beyond 10−8 rather than rescaling the caller's probabilities, assigns what remains to a single unit, and reports every adjustment it made. The effective expected hits it returns are the denominators the estimator divides by.

The whole ecosystem is pinned to one reference implementation by golden fixtures: integer outputs exact, floating point at machine precision — and the R package goes further, replaying the reference seed for seed.

the accounting, reported with every sample
s$accounting
$eps_sum              -8.43e-15   # the measured drift
$corrected_unit       512         # who absorbed it
$adjusted_crossings   0
$max_adjustment       8.43e-15

# and a refusal is a refusal:
Error: the expected hits sum 3.2e-2 away from an
integer, beyond the 1e-8 tolerance; they do not
define a sample size

install

Three doors to the same engine.

R
pak::pak(
  "castlaboratory/chromy")
Python
pip install pychromy
Cargo.toml
[dependencies]
chromy-core = "0.1"

The R package builds from source with a Rust toolchain (≥ 1.77) until the CRAN binaries are up; the crate itself has no dependencies at all.