Exchange Shuffle

An exchange shuffle is a shuffle of a deck of cards obtained by successively exchanging the cards in position 1, 2, ..., with cards in randomly chosen positions. Unlike the Fisher-Yates shuffle, the exchange shuffle chooses the second position from the entire deck at every step and does not in general produce a uniform random permutation. For , the most frequent permutation is , where if is even and either or if is odd (Goldstein and Moews 2003). Amazingly, for cards, the identity permutation (i.e., the original state before the cards were shuffled) is the most likely (Goldstein and Moews 2003).