Recall we have two bases for quasi-symmetric functions,
where is a composition (i.e., the order of the entries actually matter) and is the subset of associated with . We proved last time that , where the left hand side is the probability of getting from under the generalized riffle shuffle with parameter , , and the right hand side is the evaluation of the L quasi-symmetric function indexed by the descent set of (actually the inverse under of that, but in the definition of we need to apply again), with input .
Recall also that if we do -shuffle first and then -shuffle second, the end result is the same as shuffle, where is under lexicographical ordering. An important consequence of this is
where is the size of the descent set of (note it’s instead of as well as before, because the permutation determined by the actually sequence formed by the cards in a deck is different from the permutation used to bring the deck to that sequence). The last equality was established for general last lecture.
Thus we can use the definition of total variation distance to bound from the uniform measure on :
where , i.e., we can project the chain into a small state space determined by the number of descents. This simplification allows us to get
Theorem 1 If , then
where is the cumulative normal distribution function.
Persi mentioned the following open followup question to his analysis on the GSR shuffle: Suppose we change to , what will be the right mixing time? We do have an upper bound for , which gives
but this is not the correct answer, as seen when one takes (we get mixing time in this case, bigger than above). But at least it gives the right order in . The key to this problem seems to lie in understanding value of the quasi-symmetric functions of the form