alt Hacker NewsThe randomness comes from sampling the probabilities. The strange assumption is that the probabilities are exactly proportional to number of cards currently in each stack.
The randomness comes from sampling the probabilities. The strange assumption is that the probabilities are exactly proportional to number of cards currently in each stack.
It's the simplest model that gives the right result for simple cases (e.g. once one pile is empty, the remaining cards must come from the other pile; and when they're evenly split, it should be a coin flip). It also entails, for example, that when there are N cards in one pile and one in the other, the single card gets placed in each possible spot with equal probability. (This recalls the old trick for getting a random line from a text file without pre-counting anything.)