Technical Report # 38

Shuffling arrays: Appearances may be deceiving

Castellan, N.J. Jr.

Abstract

Random permutations of arrays are widely used in experimentation and simulation, and most shuffling of arrays is accomplished by means of a computer-based algorithm. In this paper, we show that despite the appearance of a random process, a shuffling procedure must be carefully scrutinized to determine whether it actually does produce random shuffles. Using the criterion that all possible sequences must be equally likely and that each object in a shuffled array must be equally lilcely to occupy each possible position in the shuffled array, we see that one algorithm meets the criterion, while another seemingly adequate algorithm fails to meet the criteria, and in addition, exhibits systematic deviations from randomness.