Draw a uniform random sample from an iterator you cannot count

When the collection is behind an iterator — a directory walk, a stream, a query cursor — and you cannot (or should not) make two passes over it, pick the random element while you walk: keep a winner, and at item number count, replace the winner with probability 1/count. At the end every item has had exactly 1/n probability of holding the crown. This is reservoir sampling specialised to k=1, and it needs exactly one pass and one random number per item.

The concrete instance: Windows XP chose your initial user account picture this way — a single pass over %ALLUSERSPROFILE%\...\Default Pictures via FindNextFile, RNG RtlRandomEx seeded with GetTickCount(), capped at 100 samples so a directory stuffed with a million files could not make profile creation pathological. (Raymond Chen, Old New Thing, 2026-09-09; HN discussion 49640646, read 2026-09-10. Everything below is forum-reported experience, not verified.)

Why not the obvious two-pass version

Count the files, draw r = rand % n + 1, walk again to item r. Three problems the thread kept circling:

• There is usually no cheap count. Filesystems do not expose "how many files in this directory" without walking it (ygra, 49642553: the count call would itself have to do the same walk, or the FS would need per-directory metadata that FAT32/NTFS do not have). And there is no "give me file #37" either — the second pass costs FindNextFile 37 times anyway, so two-pass doubles the FS calls for no algorithmic gain.
• The count can go stale mid-walk. moffkalast argued (49642083) the picture set is fixed stock photos, so n is a known constant; elgertam (49642412) and bombcar (49642398, whose team really did add logo pictures to the directory) answered that accounts are created at arbitrary times, the user may edit the directory, and OEMs customize it — the naive n is wrong exactly when someone cared enough to change something. Chen's stated second benefit of one-pass is precisely that a changing item count cannot break it. This disagreement is unresolved in-thread: one side says the set is static in practice, the other says static assumptions break on the machines where debugging is expensive.
• Rand-on-a-key is not uniform and not collision-free. KellyCriterion (49641693) asked why not just hash the username's first character; nkrisc (49642454) pointed out Adam/Anne/Archie then share a picture, and lentil_soup (49641766) noted you still do not know the modulus. Reported experience, not a proof.

Where it fails

• Early return silently biases to the front. The thread's most upvoted confusion: dsego (49642572) and quentinkent1 (49642684) were confident the snippet was wrong because it does not return on the first successful replace. yoz-y (49642714) gave the arithmetic: stopping at the first replace makes item one win with probability 1 over any later item that "steals" nothing. The loop must run to the end. If you find this algorithm "obviously wrong", check whether you assumed early return.
• The safety cap is a bias dial. Stopping after 100 samples means a 1001st file has probability ~0 and the first 100 are over-represented. That is a deliberate trade (pathological-directory insurance bought with uniformity); the failure is not capping, it is capping by accident — e.g. inheriting the constant from a demo where the directory held 12 files.
• Uniform does not mean distinct. XP's picker does not check which pictures already-assigned users got (question bombcar 49641336; answered from the leaked NT5 source, reddalo 49642753 — link in 49642241). Two users can and did get the same fish. If distinctness matters, that is a different algorithm (sampling without replacement) and this is not it.
• GetTickCount seeding is a feature-bug. Picture choice is fine; anything you would want unpredictable is not — the seed is the wall clock at second granularity.
• It solves selection, nothing else. The 2003 nostalgia digressions in-thread (which theme was prettier, whether the Admin account defaulted to the chess piece — TazeTSchnitzel 49641395 says the built-in Administrator always had the chess piece, i.e. a code path that bypassed the randomizer; several others reported the same memory, 49641144/49641353, with the caveat that thread itself called the memories unreliable) are exactly the kind of thing this algorithm does not tell you. Bypass paths and defaults are where "it's random" claims die.

Sources: HN item 49640646 and its comments (read 2026-09-10); Raymond Chen's post of 2026-09-09; one commenter's link to leaked NT5 source (unofficial; treat the "it doesn't check existing users" claim as reported, not verified). No claim here was checked against a live Windows XP system. Edited, not verified.