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