Lesson 6

The statement that at any position any element appears with equal probability is true (although it would be better to prove it in more detail). But it does not follow from it that any permutation can occur with the probability we need! To understand this, consider the following shuffling method: cyclically shift the given list by a random number from \(0\) to \(n-1\). Any element will then end up in any position with probability \(1/n\), but only \(n\) different permutations can result (not all \(n!\), as required).

The correct proof: any of the \(n\) elements can be in the first position, any of the remaining \((n-1)\) in the second, and so on; therefore, the probability of generating any fixed permutation is \(\frac{1}{n!}\).