🎓 A1Learner
🔍

DSA Reservoir Sampling and Honest Randomness

Reservoir sampling keeps a fair random sample from a stream whose length is not known in advance. Fair means every item ends with the same chance of holding a slot.

The replacement chance shrinks

Item 5 enters with chance 1 over 5 for a single slot. Item 10 enters with chance 1 over 10.

for i in (1, 2, 5, 10):
    print('item', i, 'enter chance', round(1 / i, 3))

One shuffle with a fixed seed

Fisher-Yates walks from the last place backwards. Each place swaps with a random place up to itself.

import random
rng = random.Random(7)
deck = [1, 2, 3, 4, 5]
for i in range(len(deck) - 1, 0, -1):
    j = rng.randint(0, i)
    deck[i], deck[j] = deck[j], deck[i]
print(deck)

Counting proves fairness at k equals 1

After three items, each item holds the slot in one third of all runs. The counting argument tracks survival chances.

stay = 1.0
for i in (2, 3):
    stay = stay * (1 - 1 / i)
    print('first item survives item', i, round(stay, 3))

Example

import random

def sample_one(stream, rng):
    kept = None
    for i, item in enumerate(stream, start=1):
        if rng.random() < 1 / i:
            kept = item
    return kept

stream = ['a', 'b', 'c', 'd', 'e', 'f']
rng = random.Random(7)
trials = 6000
tally = {item: 0 for item in stream}
for _ in range(trials):
    tally[sample_one(stream, rng)] += 1
print('trials', trials)
print('fair share', trials // len(stream))
for item in stream:
    print(item, tally[item])

Key points

  • The reservoir holds k slots for the sample
  • Item number i replaces a slot with probability k over i
  • That rule gives every seen item the same final chance
  • Fisher-Yates shuffling swaps each place with a random earlier place
  • A fixed seed makes a random run repeat exactly

In this example, one slot samples a six-item stream over 6000 trials. The random generator uses the fixed seed 7, so the tallies repeat exactly on every run. Each tally sits near the fair share of 1000. The spread is the honest cost of randomness, shown instead of hidden.

Note

The seed 7 in the closing example fixes every tally printed there

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

Item number 20 arrives with a single slot held. What is its entry chance?