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.

That is what intuition says, but in this case intuition falls short of reality. A Fisher-Yates shuffle avoids (not introduces) bias by making the pool smaller for each iteration. There are n! possible permutations of a set of n items. After the first iteration, an F-Y shuffle gives n possible outcomes, each equally likely. The second iteration yields (n - 1) for each of the n possible outcomes, leaving us with n*(n-1) possibilities - again equally likely. Follow that to its conclusion, you get n(n-1)(n-2)...1 possibilities, each equally likely.

For an example take a 3 item set. There are 3! (= 6) possible permutations of this set if it is shuffled. The first iteration of the loop, there are three possibilities: a-(1 2 3), b-(2 1 3), and c-(3 2 1). The second iteration only swaps the 2nd and 3rd elements, so for a you have an equal possibility of (1 2 3) and (1 3 2); for b - (2 1 3) and (2 3 1); for c - (3 2 1) and (3 1 2). None of the possibilities are duplicated, each one has a 1/6 chance of being selected.

           Iter 1  -  Iter 2
           (1 2 3) -> (1 2 3)
                   -> (1 3 2)
            
(1 2 3) -> (2 1 3) -> (2 1 3)
                   -> (2 3 1)

           (3 2 1) -> (3 2 1)
                   -> (3 1 2)
[download]

Six possibilities, each equally likely.

Another way to look at it is this: The first element has a 2/3 chance of getting swapped the first time and a 1/2 chance the second - giving it a 1/2 * 2/3 = 1/3 chance of ending up in any given slot.

Update: Finally, Re: Re: Re: random elements from array - new twist shows a statistical analysis of a Fisher-Yates shuffle. Whew, I'm done. I hope this wasn't homework - or if it was, Anonymous Monk learned something ;-)