1
$\begingroup$

Given an array of integer numbers and random generator how to perfectly shuffle the array? "Perfectly" means that every permutation is equally likely. One solution is go from 1st element to last element and swap current element, say i-th, with randomly choose from range i, i+1, ..., n. This way it is easy to show that each element has probability 1/n to be in any place. For example lets choose number, say m. The probability of it to be in the position one is 1/n. probability of it to be in position 2 is $\frac{n-1}{n} \cdot \frac{1}{n-1}=\frac{1}{n}$ , and so forth.

My question is about another way to shuffle numbers. Going from 1 to n we swap current number with randomly chosen one from entire array. Does this algorithm guarantee that every permutation obtained this way is equally likely?

Thank you.

EDIT: I meant that we can swap card with itself. (entire is literally entire array)

  • 0
    Your proof is not sufficient. If I just randomly cut the deck once, each card has a $\frac 1n$ chance to be in each location, but there are only $n$ possible orders, not $n!$.2012-12-06
  • 0
    yes, it is not sufficient. I wanted just show intuition behind it. But I hope the idea is clear. So that if randomly chosen number has probability 1/n to be in a randomly chosen spot then the permutation is "perfect".2012-12-06
  • 0
    The point is that each card ending in each position with probability $\frac 1n$ is necessary but not sufficient. There could be correlations between the positions of different cards which mean that some permutations are more likely than others.2012-12-06
  • 0
    I don't understand. Let's calculate probability of any permutation $i_1, i_2,\dots, i_n$. Probability of element $i_1$ to be on the first place is 1/n. Probability of element $i_2$ to be on the second place (given that $i_1$ is on the first place) is 1/(n-1) and so forth. This gives us that the probability of that permutation is $\frac{1}{n!}$. It is exactly what we want. Is it wrong?2012-12-06
  • 0
    No, in my example, if $1$ is in first place, the probability that $2$ is in second place is $1$, not $\frac 1{n-1}$. That is what I mean by correlation. This is because a cut doesn't change the order except for rotating it.2012-12-06
  • 0
    People usually use their hands. Though card shuffling machines do exist.2012-12-06
  • 0
    shuffling a deck is just a name. I am interested in mathematical part. I named this way to attract attention :-)2012-12-06

2 Answers 2

2

Your algorithm does not work. The reason for this is quite simple: for any position $i$, you choose from $n-1$ cards to swap the card in that posiiton with - all the positions that are not $i$. So the set of choices that you make could be encoded as a sequence of $n$ integers, each in the set $\{ 1, 2, \ldots, n \}$ and with the $i$th such integer not equal to $i$; there are $(n-1)^n$ such sequences, all equally likely.

But you need the probability of a given permutation $\pi$ to be $1/n!$. That means that you need $(n-1)^n / n!$ of these sequences to give the permutation $\pi$. But $(n-1)^n / n!$ is not always an integer - for example when $n = 3$ it's $2^3 / 3! = 8/6 = 4/3$.

It might help to demonstrate this for $n = 3$. Consider the 3-tuple $(x_1, x_2, x_3)$, where $1 \le x_i \le 3$ for each $i$ and $x_i \not = i$. We'll swap the card in position $i$ with the card in position $x_i$. The possible sequences are $(2,1,1), (2,1,2), (2,3,1), (2,3,2), (3,1,1), (3,1,2), (3,3,1), (3,3,2)$ -- there are eight of them. Consider for example $(2,1,1)$. This says to swap positions 1 and 2, then 2 and 1, then 3 and 1; starting with $123$ you get $321$. In the end you get eight (non-distinct) orderings, so the probability of any order must be a multiple of $1/8$; but $1/6$ is not a multiple of $1/8$.

This is one of the common implementation errors for the Fisher-Yates shuffle, about which Jeff Atwood has compiled some interesting data.)

  • 0
    I interpreted the question to include swapping a card with itself. This changes things, but I think it still doesn't work. +1 especially for the Atwood link, which shows this doesn't work, which (I think) is reading the way I did.2012-12-06
  • 0
    @RossMillikan your interpretation is correct2012-12-06
  • 0
    So now we just need $n^n/n!$ to not be an integer. It's not.2012-12-06
0

Here's an approach, not an answer: Card $1$ can end in first place either by swapping with itself and never getting picked, probability $\frac 1n(\frac {n-1}n)^{n-1}\approx \frac 1{(n-1)e}$ or by swapping with something, swapping back, and never being picked again with probability $\frac {n-1}{n^2}(\frac{n-1}n)^{n-2}\approx \frac 1{(n-1)e}$, or by swapping three or more times. Work in this manner and see if it adds to $\frac 1n$ in the limit of large $n$.