The Raffle Changes After Every Winner

A raffle with ten winners is not one random choice repeated ten times. After the first name leaves the bowl, the second draw faces a different distribution.

Put the first winner back and the same person can win twice. Leave the winner out and the draws become dependent. A duplicate is no longer an unlikely outcome; it is an impossible one. That is a different probability space, not a cosmetic rule added after sampling.

Sampling one item from a finite set is one kind of randomness. Sampling several distinct items is another. The difference sounds small in English, but it changes both the math and the implementation.

With replacement vs without replacement

Suppose your set is $S = \{A, B, C, D\}$.

If you sample with replacement, you draw one item, record it, then put it back before the next draw. Every draw sees the same full set. The sequence $(A, A)$ is perfectly possible.

If you sample without replacement, you draw one item and remove it from the available pool. After drawing $A$, the next draw is from $\{B, C, D\}$, and $(A, A)$ is impossible.

That one change means the draws are no longer independent. Each choice affects the future choices.

What uniform without replacement means

If you sample $k$ items uniformly without replacement from a set of size $n$, the cleanest definition is:

Every subset of size $k$ should be equally likely.

Sampling 2 items from $\{A, B, C, D\}$ yields 6 possible unordered outcomes: $\{A,B\}$, $\{A,C\}$, $\{A,D\}$, $\{B,C\}$, $\{B,D\}$, $\{C,D\}$. A uniform without-replacement sampler should give each subset probability $1/6$.

A useful fact drops out immediately:

Choose 3 distinct items from 10, and each individual item has inclusion probability $3/10$. That does not mean the events are independent. If one item is already in your sample, there is slightly less room for the others.

Where distinct samples appear

Without-replacement sampling appears whenever duplicates are wasteful, impossible, or misleading: choosing a mini-batch of distinct examples, assigning reviewers, selecting experiment units, proposing candidate moves, or sampling rows for inspection.

Uniform sampling gives you one fair choice. Without-replacement sampling gives you a fair subset.

A simple implementation

The most straightforward way to sample k items without replacement is to partially shuffle the array and keep the first k elements. Here is a TypeScript version using the Fisher-Yates idea:

export function sampleWithoutReplacement<T>(
  xs: readonly T[],
  k: number
): T[] {
  if (k < 0 || k > xs.length) {
    throw new Error("Invalid sample size");
  }

  const ys = [...xs];

  for (let i = 0; i < k; i++) {
    const j = i + Math.floor(Math.random() * (ys.length - i));
    [ys[i], ys[j]] = [ys[j], ys[i]];
  }

  return ys.slice(0, k);
}

Each iteration picks one uniformly random element from the remaining suffix and moves it into position. A full Fisher-Yates shuffle would continue to the end; this version stops after k swaps.

There is an honest cost hidden above: const ys = [...xs] still copies all n items, so this implementation uses $O(n)$ extra memory even though it performs only $O(k)$ random swaps. That trade-off is fine for an ordinary in-memory array. For k \ll n and a huge immutable population, Robert Floyd’s algorithm can sample the indices in expected $O(k)$ space instead.

A tempting but awkward alternative

A common first attempt: repeatedly draw uniformly with replacement, insert results into a Set, stop when the set has size k.

This eventually works, but it has a strange runtime profile. When k gets close to n, duplicates become frequent and progress slows. The algorithm spends time proposing outcomes it cannot use, then throwing them away.

The partial shuffle samples from the right space directly and has a fixed amount of work. Rejection through a Set becomes least pleasant exactly when you ask for most of the population.

The Math.random() in this example is for understanding the algorithm. A real public raffle needs a cryptographically secure source and an auditable draw procedure. Correct combinatorics cannot compensate for an opaque or predictable generator.

The output distribution now lives over subsets, not individual items. That single change explains the dependency between draws and the shape of the implementation.

Without replacement is not repeated uniform choice with duplicate cleanup. It is uniform choice over a different set of outcomes.