[PD] Shuffling arrays

[Mathieu Bouchard]

On Mon, 4 Oct 2010, martin.peach at 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