## Algebraic combinatorics lecture 12 part 1: Convergence of riffle shuffle using quasi-symmetric function theory

Recall we have two bases for quasi-symmetric functions,

$\displaystyle m_\alpha = \sum_{i_1 < \ldots < i_k} x_{i_1}^{\alpha_1} \ldots x_{i_k}^{\alpha_k}\\ L_\alpha = \sum_{i_1 < \ldots < i_k;i_j \le i_{j+1}, \forall j \in S(\alpha)} x_{i_1} \ldots x_{i_k} \ \ \ \ \ (1)$

where ${\alpha \models n}$ is a composition (i.e., the order of the entries actually matter) and ${S(\alpha)}$ is the subset of ${[n-1]}$ associated with ${\alpha}$. We proved last time that ${P_x(\omega) = L_{CO(\omega^{-1})}(x)}$, where the left hand side is the probability of getting ${\omega \in S_n}$ from ${\rm{id}}$ under the generalized riffle shuffle with parameter ${x}$, ${\sum_{i=1}^\infty x_i = 1}$, and the right hand side is the evaluation of the L quasi-symmetric function indexed by the descent set of ${\omega^{-1}}$ (actually the inverse under ${S}$ of that, but in the definition of ${L}$ we need to apply ${S}$ again), with input ${x}$.
Recall also that if we do ${x}$-shuffle first and then ${y}$-shuffle second, the end result is the same as ${x.y}$ shuffle, where ${x.y}$ is ${(x_i y_j)}$ under lexicographical ordering. An important consequence of this is

$\displaystyle Q_2^k(\omega) = Q_{2^k}(\omega) = \frac{1}{2^{nk}} \binom{2^k + n -1 - d(\omega^{-1})}{n} \ \ \ \ \ (2)$

where ${d(\omega^{-1})}$ is the size of the descent set of ${\omega^{-1}}$ (note it’s ${\omega^{-1}}$ instead of ${\omega}$ 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 ${Q_q(\omega)}$ last lecture.
Thus we can use the ${\sum |\mu(x) - \nu(x)|}$ definition of total variation distance to bound ${\delta_{id} Q_2^k}$ from the uniform measure on ${S_n}$:

$\displaystyle \sum_\omega | Q^k (\omega) - \frac{1}{n!}| = \sum_{j=0}^{n-1} A(n,j) | \frac{\binom{2^k + n-1-j}{n}}{2^{nk}} - 1/n!| \ \ \ \ \ (3)$

where ${A(n,j) = |\{\omega \in S_n: d(\omega^{-1}) = j\}|}$, 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 ${k = \frac{3}{2} \log_2 n + c}$, then

$\displaystyle \| Q^k - U\|_{\rm{TV}} = 1 - 2 \Phi(\frac{-2^{-c}}{\sqrt{\pi}}) + O(1/\sqrt{n}), \ \ \ \ \ (4)$

where ${\Phi}$ is the cumulative normal distribution function.

Persi mentioned the following open followup question to his analysis on the GSR shuffle: Suppose we change ${x = (1/2,1/2)}$ to ${(p,1-p)}$, what will be the right mixing time? We do have an upper bound for ${\sum_\omega |Q_{p,1-p}^k (\omega)-\frac{1}{n!}|}$, which gives

$\displaystyle \| Q_{p,1-p}^k(\omega) - U\| \le \binom{n}{2} (p^2 + (1-p)^2)^k \ \ \ \ \ (5)$

but this is not the correct answer, as seen when one takes ${p=1/2}$ (we get mixing time ${k=2 \log_2 n}$ in this case, bigger than ${3/2 \log_2 n}$ above). But at least it gives the right order in ${n}$. The key to this problem seems to lie in understanding value of the quasi-symmetric functions of the form

$\displaystyle L_\alpha(p^k, qp^{k-1}, \ldots). \ \ \ \ \ (6)$