Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)

share|improve this question
    
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!$. –  Ross Millikan Dec 6 '12 at 4:03
    
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". –  ashim Dec 6 '12 at 4:10
    
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. –  Ross Millikan Dec 6 '12 at 4:21
    
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? –  ashim Dec 6 '12 at 4:49
    
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. –  Ross Millikan Dec 6 '12 at 4:52

2 Answers 2

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

share|improve this answer

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

share|improve this answer
    
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. –  Ross Millikan Dec 6 '12 at 4:44
    
@RossMillikan your interpretation is correct –  ashim Dec 6 '12 at 4:56
    
So now we just need $n^n/n!$ to not be an integer. It's not. –  Michael Lugo Dec 6 '12 at 16:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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