On Mon, 4 Oct 2010, martin.peach@sympatico.ca wrote:
That's a bad way to shuffle, as it can swap things back again and generally reduce the randomness, the way someone who is good at shufflng cards can put them all back the way they started while appearing to mix them up.
But the programme is not meaning to swap things back. If things are swapped back in a random fashion, where the probability of swapping back follows from a sequence of independent uniform random-variables, what's the problem with that ? It's like the probability of getting twice the same dice number in a row, there's a certain amount of random repetition that is considered normal.
How would you write a formal proof of what you say ?
But I also believe that the quickest perfectly fair shuffle is done a lot more like [urn] than like swapping random elements. The latter converges towards being fair eventually, whereas [urn] is fair in N steps if random() is fair. The former doesn't take so many steps, but one has to decide where to stop swapping, and that's not a decision I'd like to be making, so I prefer [urn]-like processes (or similarly, [#grade]-like processes).
| Mathieu Bouchard ------------------------------ Villeray, Montréal, QC