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$

closed as off-topic by Emil Jeřábek, Kaveh, Jan Johannsen, Yuval Filmus, András Salamon Oct 21 '17 at 13:03

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Emil Jeřábek, Kaveh, Jan Johannsen, Yuval Filmus, András Salamon
If this question can be reworded to fit the rules in the help center, please edit the question.

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.

$\endgroup$
4
$\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.

$\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.