The famous Fisher-Yates shuffle algorithm can be used to randomly permute an array A of length N:

For k = 1 to N
    Pick a random integer j from k to N
    Swap A[k] and A[j]

A common mistake that I've been told over and over again not to make is this:

For k = 1 to N
    Pick a random integer j from 1 to N
    Swap A[k] and A[j]

That is, instead of picking a random integer from k to N, you pick a random integer from 1 to N.

What happens if you make this mistake? I know that the resulting permutation isn't uniformly distributed, but I don't know what guarantees there are on what the resulting distribution will be. In particular, does anyone have an expression for the probability distributions over the final positions of the elements?

Edit
Report