When the naive shuffle is biased

A buggy shuffle of 33 items runs i=1,2,3i = 1, 2, 3 and at each step swaps position ii with a position chosen uniformly from all three positions (the correct Fisher–Yates would restrict the choice to positions i\ge i). Under this buggy version, what is the probability the array ends in its original order? Give it to four decimal places.

Show hints (2)+
  1. There are 33=273^3 = 27 equally likely execution paths but only 3!=63! = 6 orderings — since 6276 \nmid 27 it can't be uniform.
  2. Count how many of the 2727 paths leave [1,2,3][1,2,3] unchanged, then divide by 2727.

Answer

Reveal 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

Related questions