What's a uniform shuffle?

Question

What does it mean exactly a "uniform shuffle" algorithm ?

Is this method considered a uniform shuffle ?

public void shuffle(Comparable[] a) {
    int n = a.length;
    int k, j;
    for (int i = 0; i < n; i++) {
        k = StdRandom.uniform(n); // k in [0, n-1]
        j = StdRandom.uniform(n); // j in [0, n-1]
        exch(a, j, k);
    }
}

Answer 1

A uniform shuffle of a table $a = [a_0, ..., a_{n-1}]$ is a random permutation of its elements that makes every rearrangement equally probable. To put it in another way: there are $n!$ possible rearrangements of $n$ elements and you need to pick one of them uniformly at random.

Many methods for shuffling seem uniform to people but are not and so it is common to see them implemented badly. For instance, shuffling by repeatedly exchanging two randomly chosen elements, as in the question, is not uniform and is also wasteful, as it generates twice as many random numbers as necessary.

A simple algorithm for a uniform shuffle is this:

import random
def shuffle(a):
    n = len(a)
    for i in range(n-1):
        j = random.randint(i, n-1)
        (a[i], a[j]) = (a[j], a[i])

This works in time $\Theta(n)$ as follows: assuming $a_0, ..., a_{i-1}$ are already shuffled, randomly select an element $a_j$ among the remaining $a_i, ..., a_{n-1}$ and exchange it with $a_i$.

To see that the result is uniformly shuffled, observe that initially every element has $\frac{1}{n}$ chance to land in place $0$ and $\frac{n-1}{n}$ to land in one of the remaining places $1, \ldots, n-1$. Therefore place $0$ is uniformly shuffled. In the next step, every element has probability $\frac{1}{n-1} \cdot \frac{n-1}{n}$ to land in place $1$, because this happens when it is not placed at 0 (probabilty $\frac{n-1}{n}$) and it is selected to be at place 1 (probability $\frac{1}{n-1}$). We may proceed inductively: an element lands in place $i$ with probability $$\frac{n-1}{n} \cdot \frac{n-2}{n-1} \cdot \frac{n-3}{n-2} \cdot \cdots \cdot \frac{n-i}{n-i+1} \cdot \frac{1}{n-i} = \frac{1}{n}.$$ The first $i$ factors arise for an element not being placed anywhere among places $0, \ldots, i-1$, and the last one for it being chosen to be placed at $i$.

Answer 2

As Andrej explains in his answer, a random shuffle consists of applying a uniformly random permutation on the input, or equivalent. Your algorithm, in contrast, applies $n$ random transpositions. This cannot possible produce an exact random shuffle, since the probability of each resulting permutation is of the form $A/n^{2n}$, which cannot equal $1/n!$.

However, if you continue to perform random transpositions, eventually you will reach a distribution which is very close to that of a random shuffle. How many exactly are needed? Diaconis and Shahshahani [1] showed that $(1/2)n\log n + \omega(n)$. After performing that many random transpositions, you reach a distribution which is $o(1)$-close to uniformly random (in an appropriate sense).

More accurately, if you perform $(1/2)n\log n + f(n)$ transpositions then the resulting sequence of distributions (one for each $n$) is $o(1)$-close to uniformly random if and only if $f(n) = \omega(n)$.

---

1. Generating a random permutation with random transpositions by P. Diaconis and M. Shahshahani (1981)

Answer 3

This is a shuffle similar to what you have. If you go through the permutations you will find some shuffles are favored.

for (i is 1 to n)
  Swap i with random position between 1 and n

This was actually a error on a poker site poker site

It does not produce a uniform distribution
Consider all possible random

for (i is 1 to n)
    for (j is 1 to n)
         Swap i with j

This is just a simple 1, 2, 3.

permutation   count
312           4
321           4
123           4
231           5
213           5
132           5

It considers more flops / swaps than required and does not even have a uniform distribution.

Fisher Yates is considered uniform and efficient