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)

Advertisements

About aquazorcarson

math PhD at Stanford, studying probability
This entry was posted in algebraic combinatorics, Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s