The Thorp shuffle is a random permutation of 
card positions defined by independent
fair switches between paired binary addresses. For an address 
, one physical shuffle
sends it to
 |
where 
is exclusive or and the switch coins 
are independent
fair bits for the 
suffixes. The same coin acts on both addresses in each pair, making the map a permutation. After 
physical shuffles, one coordinate sweep has visited each binary
direction once. The stationary distribution
on the full symmetric group 
is uniform.
A support bound gives
 |
Indeed, 
physical shuffles use 
fair bits, so at most 
permutations are attainable from a fixed deck. At threshold
, this yields a lower
bound 
for the mixing time.
