I have an array of numbers $[a_0, \ldots, a_n]$ and want to shuffle it fairly. The Fisher-Yates algorithm proposes the following.
from $i = 0$ to $n$:
$j$ = randomly pick an index in $(0, i)$,
swap $a_i$ with $a_j$.
The claim is that $P(x_0 = a_0, \ldots, x_n = a_n) = \frac{1}{n!}$. I am looking for a way to prove this rigorously.
$\endgroup$ 11 Answer
$\begingroup$Proof by induction.
Suppose $A_i$ is the set of possible arrangement after the step i.
When $i = 1$, we have two possibles arrangements,$A_1 = \{(x_0=a_0, x_1=a_1,\dots) ; (x_0=a_1, x_1=a_0,\dots)\}$
for $i = 2$, each of preceding posibilities, alow $3$ times mores, because$a_2$ can switch with any of the three first variables $x_0, x_1, x_2$
$(x_0=a_0, x_1=a_1, x_2=a_2, \dots) $$(x_0=a_2, x_1=a_1, x_2=a_0, \dots)$$(x_0=a_0, x_1=a_2, x_2=a_1, \dots)$
$(x_0=a_1, x_1=a_0, x_2=a_2, \dots)$$(x_0=a_2, x_1=a_0, x_2=a_0, \dots)$$(x_0=a_1, x_1=a_2, x_2=a_1, \dots)$
then $|A_i| = 2 \times 3 = 3!$
Suppose when $i = n-1$, we have $|A_{n-1}| = n!$, then for $i = n$, $a_n$ can switch with any of the $n+1$ first variables $x_0,\dots, x_{n}$, hence we count $$|A_n| = (n+1) \times |A_{n-1}| = (n+1)! $$ possibilities. Hence $P(x_0=a_0,\dots, x_n=a_n) = 1/|A_{n}| = 1 / (n+1)!$
$\endgroup$
