Mathematics Colloquia and Seminars
Return to Colloquia & Seminar listing
Spectral analysis of random-to-random Markov chainsAlgebra & Discrete Mathematics
"Pick a card–any card!–remove it and put it back anywhere in the deck."
Repeating this process leads to a card shuffling technique known as the
random-to-random shuffle. An important open problem is to determine how
many of these shuffles are needed to randomize the deck. This is
controlled by the spectra of the associated transition matrices.
By considering all the random-to-random shuffles simultaneously, we
prove that the eigenspaces admit a beautiful recursive structure.
This structure allows one to build eigenbases starting from bases for
the kernels. Among other things, we obtain complete combinatorial
descriptions of the eigenvalues of the transition matrices.
The representation theory of the symmetric group features prominently
in our analysis, but the results and the talk can be appreciated with
no prior knowledge of representation theory.
This talk is based on joint work with Ton Dieker.