A hundred thousand correlated samples can count as five hundred

By Ajish Pradeep · 2026-10-07 · 5 min read

Claim. When samples come in clusters that share a common effect, adding samples to the same clusters stops helping. In my simulation 100,000 samples from 50 clusters were worth about 500 independent ones, and a naive 95% interval covered the truth only 11% of the time.

Datasets are often counted in samples, while their diversity lives somewhere else. A corpus of a million sentences may come from a few thousand documents; a sensor dataset may hold millions of readings from a few dozen devices; an evaluation set may contain thousands of items drawn from a handful of sources. Samples from the same source share something: a style, a calibration, a context. I wanted a number for what that sharing costs, so I could say how many samples a dataset is "really" worth.

The design effect, on paper

Suppose there are $K$ clusters with $m$ samples each, and each sample is a cluster effect plus its own noise, scaled so that the total variance is 1 and the correlation between two samples from the same cluster is $\rho$ , the intra-cluster correlation. The variance of the overall average is then

\mathrm{Var}(\bar x) = \frac{\rho}{K} + \frac{1 - \rho}{K m} = \frac{1}{Km}\,\big(1 + (m - 1)\rho\big)

The factor $1 + (m-1)\rho$ is the design effect, a term from survey statistics. Dividing the sample count by it gives the effective sample size, the number of independent samples that would give the same precision:

n_{\text{eff}} = \frac{Km}{1 + (m - 1)\rho} \;\longrightarrow\; \frac{K}{\rho} \quad \text{as } m \to \infty

The limit is the uncomfortable part. However many samples are collected per cluster, the precision can never beat that of $K/\rho$ independent samples. With 50 clusters and a modest correlation of 0.1, that ceiling is 500.

Checking it

I simulated the model with numpy. For each setting I drew 2,000 datasets and recorded three things: the spread of their averages, which is the true standard error; the naive standard error that treats every sample as independent; and how often a "95%" interval from each would cover the true mean of zero. The second interval uses one value per cluster, the cluster average, in the spirit of the cluster-robust methods Cameron and Miller (2015)¹ review.

Clusters × samples	ρ	Design effect	Effective n	True / naive standard error	Naive 95% interval covers	Cluster-level interval covers
50 × 20	0	1	1,000	1.01	95%	95%
50 × 20	0.1	2.9	345	1.69	77%	95%
50 × 200	0.1	20.9	478	4.61	34%	94%
50 × 2,000	0.1	200.9	498	13.9	11%	95%
500 × 200	0.1	20.9	4,785	4.55	33%	95%
50 × 200	0.5	100.5	100	10.1	16%	95%

The ratio of true to naive standard error tracks the square root of the design effect closely in every row. With no correlation the naive interval is right. With $\rho = 0.1$ and 2,000 samples per cluster, the naive interval is about 14 times too narrow and covers the truth in only 11% of datasets. An interval computed from the 50 cluster averages covered it 95% of the time in every row.

More samples, or more clusters

Compare the two rows that both have 100,000 samples. Fifty clusters of 2,000 are worth about 500 independent samples. Five hundred clusters of 200 are worth about 4,800, nearly ten times as many, from the same number of samples. Holding the clusters at 50 and growing the samples per cluster shows the ceiling directly:

Clusters, samples per cluster, and what they are worth — Set the number of sources, how many samples each gives, and how alike samples from the same source are. (interactive figure)

Samples per cluster (50 clusters, ρ = 0.1)	1	10	100	1,000	10,000
Effective sample size	50	263	459	496	500

Past the first hundred, collecting more from the same sources buys almost nothing.

This is the arithmetic behind two practical habits. A test set should be judged by how many independent sources it covers, not how many items it holds. And when data can be collected either deeper or wider, wider is usually the better buy.

Where it shows up in machine learning

The same algebra applies wherever an average over correlated samples is reported:

Accuracy on a test set with many items per source: its error bar comes from the number of sources, and a difference between two models that looks significant at the item level may not be at the source level.
Validation loss during training, where repeated batches from a few long sequences behave the same way.
Data mixtures counted in samples, where "this source is 60% of the data" can describe a source with very few independent clusters.

The correction is cheap when the cluster of each sample is known: compute the statistic per cluster, then average and take the standard error over clusters. When it isn't known, the sample count should be read as an upper bound.

Correlation computed from a handful of points has the same weakness in another form, in correlation is not agreement. On the training side, how many items a sampler actually shows the model is in sampling with replacement sees about 63% of your data.

What I still don't know

My model has one level of clustering and the same correlation everywhere. Real data nests, with samples within sessions within sources, and correlations differ between clusters. The design effect generalises to that, but I haven't simulated it. The bigger open question for me is about training, where the same sharing happens. A model trained on a few large clusters learns their shared effects as if they were general, and I'd like to measure how the effective size of the training data, not only the test data, predicts how well a model transfers to a new cluster.

References

A Practitioner's Guide to Cluster-Robust Inference — A. Colin Cameron and Douglas L. Miller, Journal of Human Resources 2015