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 6∤276 \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)

Create a free account to see the full worked solution and track your progress.

Interview format: Market Maker, Systematic & Data-Driven Trading

Related questions