## fizzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# The Knuth shuffle

Sharing is caring!

The Knuth shuffle algorithm is an algorithm for randomly shuffling the elements of an array arr of size $n$ given a function that generates a uniformly distributed random number in $\mathcal{O}(1)$ time. The algorithm produces an unbiased permutation. That is, every permutation is equally likely.

for i in range(n-1,0,-1):
j = integer chosen uniformly randomly from [0,i]
swap arr[i] with arr[j]


Proof that the algorithm is unbiased
For any element $e$, the probability that it will be shuffled into position $n-1$ (last position at zero based indexing) is: the probability that it gets selected when $i=n-1$, which is $\frac{1}{n}$.

For any element $e$, the probability that it will be shuffled into position $n-2$ (second-to-last position) when $i=n-2$ is: the probability that it gets selected when $i=n-2$, which is $\frac{1}{n-1}$ multiplied by the probability that it is not selected for the last position, which is $1 - \frac{1}{n} = \frac{n-1}{n}$, giving $\frac{1}{n-1}\times\frac{n-1}{n} = \frac{1}{n}$

For any element $e$, the probability that it will be shuffled into position $n-3$ (third-to-last position) when $i=n-3$ is: the probability that it gets selected when $i=n-3$, which is $\frac{1}{n-2}$ multiplied by the probability that it is not selected for the last nor second-to-last position, which is $1 - \frac{2}{n} = \frac{n-2}{n}$, giving $\frac{1}{n-2}\times\frac{n-2}{n} = \frac{1}{n}$.

This can easily be generalised for any other position.

So we can see that for any element $e$, the probability that it will be shuffled into the last, second-to-last, third-to-last, etc position is $\frac{1}{n}$.