3 ms·
Any unbiased algorithm that uses an unbiased coin to shuffle n > 2 elements must be potentially unbounded. Proof: there are n! possible permutations. If the al
by orlp 2y ago
Any unbiased algorithm that uses an unbiased coin to shuffle n > 2 elements must be potentially unbounded.
Proof: there are n! possible permutations. If the algorithm always finishes within k coin tosses then there are 2^k possible outcomes. For n > 2 we have that n! does not divide 2^k, so not all outcomes can be equiprobable.
- klyrs 2y agoYou proved that not all outcomes are equiprobable, not that they're unbounded.
- LegionMammal978 2y agoThis is a proof by contradiction: it shows that any bounded algorithm doesn't have equally probable outputs, i.e., that it is necessarily biased, contradicting our assumption that it is unbiased. Therefore, an unbiased, bounded algorithm cannot exist (for n > 2): any algorithm is necessarily either biased or unbounded.
- Jaxan 2y agoThat is not enough because k is allowed to depend on n.
- LegionMammal978 2y agoFor n > 2, n! does not divide 2^k for any k, since n! has a factor of 3.