The random transposition walk on the symmetric group 
is the random walk which, at every step, multiplies
the current permutation by a uniformly chosen transposition. Thus its one-step probability
measure is
 |
(1)
|
The transposition-only walk, defined for 
, alternates between even
permutations and odd permutations. In the
aperiodic version of Diaconis and Shahshahani (1981), two indices are chosen independently
and uniformly from 
and their entries are exchanged. This gives the identity permutation probability 
and each transposition probability 
.
It has a cutoff in total variation distance
at 
steps with a window of order 
(Diaconis and Shahshahani 1981), with a parity-adjusted analog
for the transposition-only walk. At the cutoff scale, the fixed
point count approaches a Poisson distribution.
Arcona (2026) uses group representation theory
to determine the limiting distributions of the numbers of j
for every fixed 
, and also treats the star-transposition
walk in which each step swaps 1 with a uniformly chosen other point.
