Spectral analysis of random-to-random Markov chainsAlgebra & Discrete Mathematics
|Speaker:||Franco Saliola, UQAM|
|Start time:||Fri, Sep 25 2015, 2:10PM|
"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.