in reply to Re: Fisher-Yates theory
in thread Fisher-Yates theory

One could argue in great length whether additional shuffling in the array improves the randomness, or whether it produces patterns in the longer term,

If your RNG was perfect, additional shuffles would neither improve or degrade the randomness.

but it isn't difficult to argue that regardless of which conclusion is valid, the fact that the entries nearer to the beginning have additional chances of being shuffled, while entries nearer the end have fewer chances, that *one* of these ends will be improved more than the other, therefore the algorithm is not optimal.

Unless neither conclusion is valid (see above) in which case a single shuffle is no better or worse than multiple shuffles and the algorithm is optimal.

In practice, however, our RNGs aren't perfect and you may have a point. I suppose you could resolve it by keeping track of the original indexes of the elements and then apply your map and do a second FY shuffle starting with the previous last and moving backwards to the previous first... still linear in time and space... but I doubt it is worth it. :-)

-sauoq
"My two cents aren't worth a dime.";

Replies are listed 'Best First'.
Re: Fisher-Yates theory
by Abigail-II (Bishop) on Jul 24, 2003 at 08:25 UTC
    The biggest problem with shuffling algorithms (not just Fisher-Yates) is the imperfectness of the RNG. The sequence of numbers it returns is determined by the seed, and only by the seed. And if from the seed only 32 bits are being used, there will be at most 2**32 different sequences. Which means that for a deck of more than 2 cards, Fisher-Yates cannot be 'fair', as N! won't be a divisor of any power of 2. Furthermore, 13! > 2**32, so even if you shuffle a deck of 13 cards, some permutations will *never* be selected, no matter how many times you perform the shuffle.

    This was pointed out by R. Salfi: COMPSTAT 1974, Vienna: 1974, pp 28 - 35.

    See also the documentation of the Shuffle module on CPAN.

    Abigail

[reply]
(Re:)+ Fisher-Yates theory
by rir (Vicar) on Jul 24, 2003 at 12:58 UTC
    One could argue in great length whether additional shuffling in the array improves the randomness, or whether it produces patterns in the longer term,

    If your RNG was perfect, additional shuffles would neither improve or degrade the randomness.

    It seems that additional "shuffling" is required to prevent a permutation of the array where there is a correlation between items that are swapped.

    It seems the "additional shuffling" is required.

    Consider the shuffling of an array of three items without the so called "additional shuffling": Starting from the left: 

    Initial:   abc

1 move:    abc             bac(1/3)        cba(1/3)

2 move:    abc(1/6)  acb(1/6)

    [download]
    Updated: Per Abigail's criticism of a misstyped table and obscurity. To clarify:

    I take issue with:

    On the surface, each array entry has the appearance of being given a single opportunity at being swapped with another array entry. In practice, array entries nearer to the beginning of the array have additional opportunities of being swapped (as a result of later swaps), meaning that less shuffling happens at the end of the array than at the beginning.

    One could argue in great length whether additional shuffling in the array improves the randomness, or whether it produces patterns in the longer term, but it isn't difficult to argue that regardless of which conclusion is valid, the fact that the entries nearer to the beginning have additional chances of being shuffled, while entries nearer the end have fewer chances, that *one* of these ends will be improved more than the other, therefore the algorithm is not optimal.

    Which seems to say that the possible movement of an already moved item is a weakness of the algorithm. But an array cannot be randomly shuffled in place without allowing elements to be moved more than once.

    The idea that the errors of a RNG will more adversely affect the items to which that RNG is more often applied is an argument that is more subtle. I reject it out of hand. If the RNG is incorrect the results will not be random and we are quibling about how obvious the error is. This distinction may be very important in practice and there are practical solutions to get a pseudo-randomness that is okay for varying definitions of okay.

[reply]
[d/l]
      I've no idea what you are trying to argue. I also don't understand your table of situations. In the first move of a Fisher-Yates shuffle, the last element is swapped, so with an initial 
          A, B, C

      [download]

      after the first move we have one of: 

          C, B, A
    A, C, B
    A, B, C

      [download]

      Your table suggests a possible B, C, A after the first move, but you need at least two swaps to go from A, B, C to B, C, A.

      Abigail

[reply]
[d/l]
[select]

In Section Meditations