0
$\begingroup$

Let us have a "shuffle algorithm":

for i in range(len(vec)):
     swap(vec[i], vec[rand()%len(vec)])

Why the reshuffles we get using this algoritm for a number of times turn out to be biased (unequal)?

$\endgroup$
4
$\begingroup$

You can also try to get some intuition from the "correct" version, Fisher-Yeates / Knuth shuffle.

for i in range(len(vec)-1):
    swap(i, randint(i, len(vec)-1))

The idea is that, when we get to i, the previous elements are perfectly random, so let's leave them there and recursively shuffle the rest. In contrast, the naive algorithm will sometimes "reach backward" to make a swap.

Now I'm noticing that in the naive shuffle, elements which are below the current index i can only ever move forward from now to the end of the algorithm. Okay, so in particular, the last element only has two ways to end up in the first position: Either the first element can swap with him, and then nobody else ever swaps with him (this has about a $\frac{1}{n}\frac{1}{e}$ chance), or else nobody ever swaps with him until the last round, and then he swaps with whoever's in first (this has the exact same chance). So the last element should only end up first with probability about $\frac{2}{en} \approx 0.74\frac{1}{n}$ instead of $\frac{1}{n}$.

I simulated this in python with n=100 and 100,000 trials, and got 734 trials in which the last element ended up first, versus 992 trials using Fisher-Yeates.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

Consider the case $n=3$. There are 27 possible runs of the algorithm. Let's see where the first vector ends up ($X_1$) in each case, and where the 2nd ends up ($X_2$). $$ \text{Format:}\quad\sigma_1\sigma_2\sigma_3: X_1, X_2$$ $$\begin{eqnarray*} (11)(12)(13)&:2,3\quad (11)(12)(23)&:3,1\quad (11)(12)(33)&:2,1\\ (11)(22)(13)&:3,2\quad (11)(22)(23)&:1,3\quad (11)(22)(33)&:1,2\\ (11)(23)(13)&:3,1\quad (11)(23)(23)&:1,2\quad (11)(23)(33)&:1,3\\ \end{eqnarray*} $$ $$ \begin{eqnarray*} (12)(12)(13)&:3,2\quad (12)(12)(23)&:1,3\quad (12)(12)(33)&:1,2\\ (12)(22)(13)&:2,3\quad \mathbf{(12)(22)(23)}&:3,1\quad \mathbf{(12)(22)(33)}&:2,1\\ (12)(23)(13)&:1,3\quad \mathbf{(12)(23)(23)}&:2,1\quad \mathbf{(12)(23)(33)}&:3,1\\ \end{eqnarray*}$$

$$\begin{eqnarray*}(13)(12)(13)&:1,3\quad (13)(12)(23)&:2,1\quad (13)(12)(33)&:3,1\\ (13)(22)(13)&:1,2\quad (13)(22)(23)&:2,3\quad (13)(22)(33)&:3,2\\ (13)(23)(13)&:2,1\quad (13)(23)(23)&:3,2\quad (13)(23)(33)&:2,3\\ \end{eqnarray*} $$

We see $\Pr(X_2)=1)=10/27$, $\Pr(X_2=2)=8/27$, and $\Pr(X_2=3)=9/27$.

Note that if $\sigma_1\in\{(13), (11)\}$, then the distribution of $X_2$ is uniform.

However, if $\sigma_1=(12)$, then any of the 4 subsequent combinations that don't move position 1 leads to $X_2=1$, making that a slightly favored outcome.

I guess the point is that the second two moves must be of the form $(2x)(3y)$ and so they are rather likely to not involve position 1.

There is some work by Diaconis et al. showing that shuffling is pretty good, though.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thanks! isn't that true: this algorithm builds (for a vector with length n) a tree with n levels, each vertex (except leaves) having n children, so together we have n^n possible results, while the real amount of permutations of length n is n!, and n^n can't be divisible (evenly) by n!, so the algorithm is biased anyway? $\endgroup$ – John Smith Oct 16 '17 at 21:17
  • $\begingroup$ @JohnSmith ah yes, that's true too $\endgroup$ – Bjørn Kjos-Hanssen Oct 16 '17 at 21:20

Not the answer you're looking for? Browse other questions tagged or ask your own question.