Hacker News Reader

Comment by manifold | Hacker News Reader

Great article. This is probably a question for the statisticians: Would repeatedly sampling from a uniform distribution mean that on average the next card chosen will come from the middle of the remaining pack (as repeatedly sampling from a uniform distribution gives a normal distribution), or does the decreasing sample size somehow cancel that effect out? Then at the same time the algorithm is moving cards from the end towards the middle. Intuitively it feels like the shuffle ought to be biased towards selecting the middle-end of the pack first, but wikipedia indicates it's unbiased. Any help with getting further intuition?

View on HN

The key here is that you aren't sampling the same uniform distribution each time. You shrink the sample space by one each time you remove a card and append it to the end.

Repeatedly sampling from a uniform distribution gives a uniform distribution - uniform means the probability is the same for all cards.

Yes, but the average value of the sampled values will tend towards a Normal distribution by the central limit theorem, and I'm probably misapplying it by wondering whether the next sample tends to be from nearer the middle. I think skimbrel is right that as the sample being drawn from is decreasing each time the CLT will be invalidated anyway.

Sorry to be blunt, but you're confused.

The average of the sampled values will be normally distributed, but the values themselves will be uniform.

If you sample every number once from [0,100], the average is 50, but that doesn't imply that the distribution of the sampled elements is normal - it's uniform.

His question of whether "on average, does the next card come from the middle" (which it doesn't) isn't the same as "is the mean of the next sampled card in the middle" (which it is).

The language was a little misleading - he said "on average" when he intended "most frequently".

Ok thanks for clearing that up. I hadn't appreciated the difference between the two.

That's not how central tendency works. The average position converges to a normal.

Reply on news.ycombinator.com