Resample

Select $k$ elements from sample $\mathbf{x}$ with replacement using generator $r$.

• Algorithm — uniform sampling with replacement, see Resample
• Complexity — $O(k)$ time
• Output — new array with $k$ elements (may contain duplicates)
• Domain — $k \geq 0$, sample size $n \geq 1$

Notation

• $\mathbf{x} = (x_1, \ldots, x_n)$ sample ($n \geq 1$)
• $x_i$ individual measurements

Properties

• Independence each selection is independent with equal probability $\frac{1}{n}$
• Duplicates same element may appear multiple times in output
• Determinism same generator state produces same selection

Example

• Rng("demo-resample").Resample([1, 2, 3, 4, 5], 3) — select 3 with replacement
• r.Resample(x, n) — bootstrap sample of same size as original

Implementation names

$\operatorname{Resample}$ picks elements with replacement, allowing the same element to be selected multiple times. This is essential for bootstrap methods where we simulate new samples from the observed data. Unlike $\operatorname{Sample}$ (without replacement), $\operatorname{Resample}$ can produce outputs larger than the input and will typically contain duplicate values. For reproducible bootstrap, combine with a seeded generator: Resample(data, n, Rng("bootstrap-1")).

Algorithm

The $\operatorname{Resample}$ function selects $k$ elements from a sample of size $n$ with replacement.

The algorithm generates $k$ independent uniform random integers in $[0, n)$ using the Rng generator, and collects the corresponding elements:

result = new array of size k
for i from 0 to k-1:
   j = uniform_int(0, n)
   result[i] = x[j]

Each selection is independent with equal probability $\frac{1}{n}$ for every element. The same element may appear multiple times in the output. Time complexity is $O(k)$ with $O(k)$ additional space for the result array.

Tests

The $\operatorname{Resample}$ test suite contains 19 test cases validating sampling with replacement (bootstrap resampling). Given a seed, input array $\mathbf{x}$ of size $n$, and draw count $k$, $\operatorname{Resample}$ returns $k$ elements drawn independently and uniformly from $\mathbf{x}$ (with replacement, so duplicates are possible). All tests verify reproducibility: the same seed, input, and $k$ must produce the same output across all language implementations.

Seed variation 6 tests with different seeds:

• seed-0-n10-k3: seed $= 0$, $n = 10$, $k = 3$
• seed-42-n10-k5: seed $= 42$, $n = 10$, $k = 5$
• seed-123-n10-k3: seed $= 123$, $n = 10$, $k = 3$
• seed-314-n10-k10: seed $= 314$, $n = 10$, $k = 10$
• seed-999-n10-k3: seed $= 999$, $n = 10$, $k = 3$
• seed-2718-n100-k25: seed $= 2718$, $n = 100$, $k = 25$

These tests validate that different seeds produce different bootstrap samples from the same input.

Parameter variation (seed $= 1729$) 13 tests exploring $n$ and $k$:

• seed-1729-n1-k1: $n = 1$, $k = 1$ (trivial case)
• seed-1729-n2-k1: $n = 2$, $k = 1$ (single draw from two)
• seed-1729-n5-k3: $n = 5$, $k = 3$ (standard draw)
• seed-1729-n5-k7: $n = 5$, $k = 7$ ($k > n$, valid for resampling)
• seed-1729-n10-k1: $n = 10$, $k = 1$ (single draw from many)
• seed-1729-n10-k3: $n = 10$, $k = 3$ (standard draw)
• seed-1729-n10-k5: $n = 10$, $k = 5$ (half draw)
• seed-1729-n10-k10: $n = 10$, $k = 10$ (draw equal to pool size)
• seed-1729-n10-k15: $n = 10$, $k = 15$ ($k > n$, exercises repeated sampling)
• seed-1729-n20-k5: $n = 20$, $k = 5$
• seed-1729-n20-k10: $n = 20$, $k = 10$
• seed-1729-n100-k10: $n = 100$, $k = 10$ (large pool, small draw)
• seed-1729-n100-k25: $n = 100$, $k = 25$ (large pool, moderate draw)

Unlike $\operatorname{Sample}$ (without replacement), $\operatorname{Resample}$ allows $k > n$ since each draw is independent. The $k > n$ cases (n5-k7, n10-k15) are unique to resampling and validate that the output can contain repeated values from the input.

References