<p>You can also try to get some intuition from the "correct" version, <a href="https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle" rel="nofollow noreferrer">Fisher-Yeates / Knuth shuffle</a>.</p>

<pre><code>for i in range(len(vec)-1):
    swap(i, randint(i, len(vec)-1))
</code></pre>

<p>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.</p>

<p>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 <em>last</em> 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}$.</p>

<p>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.</p>

CC BY-SA 3.0
2017-10-17T03:06:26.753Z
2017-10-17T03:06:26.753Z
usul
<p>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)&amp;:2,3\quad
(11)(12)(23)&amp;:3,1\quad
(11)(12)(33)&amp;:2,1\\
(11)(22)(13)&amp;:3,2\quad
(11)(22)(23)&amp;:1,3\quad
(11)(22)(33)&amp;:1,2\\
(11)(23)(13)&amp;:3,1\quad
(11)(23)(23)&amp;:1,2\quad
(11)(23)(33)&amp;:1,3\\
\end{eqnarray*}
$$
$$
\begin{eqnarray*}
(12)(12)(13)&amp;:3,2\quad
(12)(12)(23)&amp;:1,3\quad
(12)(12)(33)&amp;:1,2\\
(12)(22)(13)&amp;:2,3\quad
\mathbf{(12)(22)(23)}&amp;:3,1\quad
\mathbf{(12)(22)(33)}&amp;:2,1\\
(12)(23)(13)&amp;:1,3\quad
\mathbf{(12)(23)(23)}&amp;:2,1\quad
\mathbf{(12)(23)(33)}&amp;:3,1\\
\end{eqnarray*}$$</p>

<p>$$\begin{eqnarray*}(13)(12)(13)&amp;:1,3\quad
(13)(12)(23)&amp;:2,1\quad
(13)(12)(33)&amp;:3,1\\
(13)(22)(13)&amp;:1,2\quad
(13)(22)(23)&amp;:2,3\quad
(13)(22)(33)&amp;:3,2\\
(13)(23)(13)&amp;:2,1\quad
(13)(23)(23)&amp;:3,2\quad
(13)(23)(33)&amp;:2,3\\
\end{eqnarray*}
$$</p>

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

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

<p>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.</p>

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

<p>There is some work by <a href="https://en.wikipedia.org/wiki/Persi_Diaconis#Card_shuffling" rel="nofollow noreferrer">Diaconis et al.</a> showing that shuffling is pretty good, though.</p>

CC BY-SA 3.0
2017-10-16T21:17:38.410Z
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?
John Smith
CC BY-SA 3.0
2017-10-16T21:20:36.117Z
@JohnSmith ah yes, that's true too
Bjørn Kjos-Hanssen
CC BY-SA 3.0
2017-10-16T20:25:02.177Z
2017-10-16T20:48:00.323Z
2017-10-16T20:48:00.323Z
Bjørn Kjos-Hanssen
<p>Let us have a "shuffle algorithm":</p>

<pre><code>for i in range(len(vec)):
     swap(vec[i], vec[rand()%len(vec)])
</code></pre>

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

<randomized-algorithms>
Naive shuffle algorithm
John Smith
# Naive shuffle algorithm

(Asked by: username_0 on 2017-10-16)

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)?

**Tags:** randomized-algorithms


---

## 2 answers

### Answer by username_1 on 2017-10-17. Score: 4 | Accepted answer

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.


---

### Answer by username_2 on 2017-10-16. Score: 3

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.](https://en.wikipedia.org/wiki/Persi_Diaconis#Card_shuffling) showing that shuffling is pretty good, though.

> **Comments:**
> **username_0**: 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?  
> **username_2**: @JohnSmith ah yes, that's true too  

---

