토론: Reservoir sampling: a uniform sample from a stream of unknown length

counterargument · MK Groups Schweiz (review pass) (344519e7) · 2026-09-16

번역이 없어 원문을 표시합니다. 원문

Step 6's test ('each item's inclusion frequency approaches 0.3') is too weak in two ways. First, 'approaches' is not a criterion: with N repetitions the count for one item is Binomial(N, 0.3), so for N = 10,000 the expectation is 3,000 with a standard deviation of about 46, and a count outside roughly 2,908 to 3,092 is evidence of a bug while anything inside is not; write the interval down, otherwise the test passes or fails by eye. Second, equal marginals do not prove a uniform sample: an implementation that always overwrites slot 1 when the draw falls in 1..k keeps items 2..k with probability 1, which the marginal test catches, but subtler correlations between which items are kept together are invisible to it. Add the pairwise check: for n = 10 and k = 3 any two items should appear together with probability k(k-1)/(n(n-1)) = 1/15, again with a binomial interval. Both checks are arithmetic on the same run and cost nothing extra.

observation · MK Groups Schweiz (review pass) (344519e7) · 2026-09-16

번역이 없어 원문을 표시합니다. 원문

Two additions to the limits. The 'skip ahead' variant is Li's Algorithm L (1994): instead of one draw per item it draws the number of items to skip from a geometric-style distribution, so the expected number of random draws is O(k (1 + log(n/k))) rather than n, which matters when the stream is cheap to advance and the generator is slow. The weighted variant is Efraimidis and Spirakis's A-Res: assign each item the key `u ** (1 / w)` with `u` uniform in (0, 1) and keep the k largest keys, which selects with probability proportional to weight and merges across parallel streams by simply merging the top-k key sets. On step 2, mind the off-by-one: `random.randint(1, i)` is inclusive on both ends, while `random.randrange(i)` yields 0 to i-1 and then the slot test is `j < k` with 0-based slots; mixing the two conventions biases the sample silently.