Sampling with replacement sees about 63% of your data

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

Claim. An "epoch" of N draws with replacement shows the model only about 63% of N items. Balancing groups lowers that further for the largest group, and in my simulation writing a group's target share as a per-item weight gave the smallest group 0.1% of the batches instead of 7%.

Weighted samplers are a common way to stop a large data source from drowning out a small one. Instead of shuffling the dataset, the loader draws each batch from a distribution over items, and the weights decide how often each source appears. The word "epoch" usually survives the change, meaning "as many draws as there are items". I wanted to know what an epoch means after that change: how much of the data a model actually sees in one, and what can go wrong in the weights.

One epoch with replacement, on paper

Draw $N$ times uniformly, with replacement, from $N$ items. A given item is missed by one draw with probability $1 - 1/N$ , and by all of them with probability

\left(1 - \frac{1}{N}\right)^N \;\longrightarrow\; \frac{1}{e} \approx 0.368

So the expected fraction of items seen at least once is $1 - 1/e \approx 0.632$ , for any large $N$ . More generally, if a group of $n$ items receives $k$ draws, the fraction of it that is seen is about

1 - e^{-k/n}

A sampler without replacement, which walks through a shuffled order, sees $\min(1, k/n)$ of the group instead. The gap between those two curves is the price of drawing with replacement.

Checking it

I simulated it with numpy. For $N$ of 100, 10,000 and a million, one epoch of uniform draws saw 62.0%, 63.4% and 63.21% of the items, against the limit of 63.21%. The items that were seen were each drawn 1.58 times on average. A third of the data simply sat out the epoch, while the rest was partly repeated.

Balancing groups

Now three groups of very different size: 600,000 items, 60,000 and 6,000. Left uniform, the batches are 90%, 9% and 0.9% from each. A common compromise is to give each group a share proportional to the square root of its size, which here is 70.6%, 22.3% and 7.1%. Each item in group $g$ is then drawn with probability proportional to $f_g / n_g$ , its group's share divided by the group's size.

How much of each group an epoch actually shows the model — Three groups of very different size, four samplers, and an epoch as long as you like. (interactive figure)

One epoch of 666,000 draws	Share of batches (large / middle / small)	Fraction seen (large / middle / small)	Overall unique
Uniform with replacement	90.0% / 9.1% / 0.9%	63% / 63% / 63%	63.2%
Square-root shares, with replacement	70.6% / 22.4% / 7.0%	54% / 92% / 100%	58.1%
Square-root shares, without replacement within each group	70.6% / 22.3% / 7.1%	78% / 100% / 100%	80.5%
Shares used as per-item weights (the mistake)	96.8% / 3.1% / 0.1%	66% / 29% / 10%	62.0%

Balancing worked for the batch shares, and it cost the large group. It now gets 0.784 draws per item instead of 1, and with replacement that shows only $1 - e^{-0.784} = 54\%$ of it, which is what the simulation found. Meanwhile each item of the small group was drawn about eight times. Balancing with replacement repeats the small groups heavily and still leaves most of the large group out.

Walking through each group in a shuffled order, cycling when a small group runs out, kept the same shares and raised the coverage of the large group from 54% to 78%, which is the most possible at 0.784 draws per item. The small groups are covered completely. Gürbüzbalaban et al. (2021)¹ and Shamir (2016)² analyse the optimisation side of this choice and give convergence results showing that sampling without replacement, which is how most training loops actually work, converges at least as well, under their assumptions, as the with-replacement sampling that much of the theory assumes. Here the difference is simply which data the model sees.

The weight that means two things

The last row is the mistake I wanted to measure, because it is so easy to make. A configuration that says small: 0.07 reads naturally as "7% of the batches should come from the small group". If the sampler instead treats it as a weight per item, the realised share of group $g$ becomes

\text{share}_g = \frac{w_g\, n_g}{\sum_j w_j\, n_j}

which scales with the group's size, the very thing the weight was meant to cancel. With the square-root shares as per-item weights, the small group's share fell from the intended 7.1% to 0.1%, about 70 times too small, and only 10% of its items were seen in the epoch. The middle group lost a factor of seven. The two readings differ by a factor of $n_g$ , and nothing in the loss curve would show it.

What I would check in a sampler

From these numbers, these are the checks I would run on any weighted loader:

the realised share of each group over a few thousand batches, compared with the intended share;
the fraction of each group seen at least once per epoch, compared with $1 - e^{-k/n}$ or $\min(1, k/n)$ ;
whether the configured numbers are per-item weights or per-group shares, written down where the configuration lives.

Counting what a dataset is worth runs into the same distinction between items and independent sources, in a hundred thousand correlated samples can count as five hundred.

What I still don't know

Seeing an item once per epoch is not the same as learning from it, and seeing it eight times is not eight times as useful. I have measured coverage, not what coverage does to the trained model. With heavily repeated small groups, the model will memorise them faster than it generalises from them, and I don't know at what repetition rate that starts to matter. I'd like to measure it on a task where the small group really differs from the large one.

References

Why Random Reshuffling Beats Stochastic Gradient Descent — Mert Gürbüzbalaban, Asuman Ozdaglar and Pablo A. Parrilo, Mathematical Programming 2021
Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization — Ohad Shamir, NeurIPS 2016