When the naive shuffle is biased
A buggy shuffle of items runs and at each step swaps position with a position chosen uniformly from all three positions (the correct Fisher–Yates would restrict the choice to positions ). Under this buggy version, what is the probability the array ends in its original order? Give it to four decimal places.
Show hints (2)+
- There are equally likely execution paths but only orderings — since it can't be uniform.
- Count how many of the paths leave unchanged, then divide by .
Answer
Reveal answer →Final answer
0.1481 (± 0.001)
Want the full step-by-step worked solution? It's part of Premium — along with a worked solution for every question in the bank.
Asked at: Jane Street, Two Sigma