## Quasi-symmetric (QS) functions and generalized riffle shuffle

An example of a QS function is given by

$\displaystyle \sum_{i < j} x_i^2 x_j \ \ \ \ \ (39)$

which is clearly not symmetric. In general, ${f}$ is quasi-symmetric if for all ${i_1 < \ldots < i_k}$ and ${j_1 < \ldots < j_k}$:
${[x_{i_1}^{\alpha_1} \ldots x_{i_k}^{\alpha_k}] f = [x_{j_1}^{\alpha_1} \ldots x_{j_k}^{\alpha_k}] f}$.
Let ${Q^n}$ be the space of QS functions of degree ${n}$ with infinitely many variables as usual. And ${Q := Q^0 \oplus \ldots \oplus Q^n \oplus \ldots}$. Then ${Q}$ strictly contains the symmetric function algebra ${\Lambda}$. One basis of ${Q^n}$ is given by the analogue of monomial polynomials, indexed instead by the set of compositions of ${n}$:

$\displaystyle m_\alpha = \sum_{i_1 < \ldots < i_k} x_{i_1}^{\alpha_1} \ldots x_{i_k}^{\alpha_k}. \ \ \ \ \ (40)$

So ${\dim Q^n = 2^{n-1}}$, the latter is the number of compositions, because ${\{m_\alpha\}}$ clearly forms a basis. Now given a composition ${\alpha \models n}$, i.e., ${\sum \alpha_i = n}$, we associate a subset ${ S(\alpha) = \{\alpha_1, \alpha_1 + \alpha_2, \ldots, \alpha_1 + \ldots + \alpha_{k-1}\} \subseteq [n-1]}$. If ${\alpha = (n)}$ we just get the empty set. With this construction, another basis is given by

$\displaystyle L_\alpha(x) = \sum_{i_1 \le \ldots \le i_k} x_{i_1} \ldots x_{i_k} \ \ \ \ \ (41)$

where strict inequality is required for ${i_j < i_{j+1}}$ if ${j \in S(\alpha)}$. As a set of exercises, check that

$\displaystyle L_3(x) = \sum_{i \le j \le k} x_i x_j x_k = h_3 \text{ so it's actually symmetric }\\ L_{21}(x) = \sum_{i \le j < k} x_i x_j x_k = m_{21} + m_{111}\\ L_{12}(x) = m_{12} + m_{111}\\ L_{111}(x) = e_3. \ \ \ \ \ (42)$

Please note that French mathematicians call ${L_\alpha}$‘s ${F_\alpha}$‘s, called the fundamental/ Gessel’s basis. We also define ${CO}$ to be the inverse operation of ${S}$, i.e., given ${\omega \subset [n-1]}$, we first order the elements into an increasing array, then take successive difference, with the last difference taken from ${n}$. So for example, given ${\omega = \{3,4\}}$, ${CO(\omega) = (3,1,n-4)}$.

Proposition 13 for ${\alpha \models n}$,

$\displaystyle L_\alpha = \sum_{S(\alpha) \subseteq T \subset [n-1]} m_{CO(T)} \\ m_\alpha = \sum_{S(\alpha) \subseteq T \subseteq [n-1]} (-1)^{T \setminus S(\alpha)} L_{CO(T)}. \ \ \ \ \ (43)$

A bit about shuffling: the GSR shuffling is described by first cut c cards from a deck of n with chance ${\binom{n}{c}/2^n}$. Drop the next from left with probability ${A / (A+B)}$ with ${A}$ being the size of the left deck etc. One can easily check this has the uniform measure on ${S_n}$ as stationary distribution. Inverse shuffling: choose each card with probability 1/2 independently then take those out and put on top. Exercise: this indeed gives the transpose of the Markov matrix for GSR. The idea is to check that once we cut c cards, the arrangements of c cards interwoven with ${n-c}$ cards are equally likely. This is obvious in light of the fact that the dropping process can be seen as drawing cards of black and white kinds from a box in which they are mixed up.
More generally, if one is given ${X_i \ge 0}$, and ${\sum_{i=1}^\infty X_i =1}$. The one could label ${n}$ cards independently with ${i}$ with probability ${X_i}$. Next

1. Remove all cards labeled 1 and put in a separate pile.
2. Remove all cards labeled 2 and put on top of the 1’s, etc.

This defines the Inverse X shuffle. In the forward direction, we pick ${i_1, \ldots, i_n}$ with ${P(i_j = a) = x_a}$, independently. Standardize ${1, \ldots, n}$ in the following sense

$\displaystyle \begin{array}{cccccc} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 1 & 1 & 4 & 3 & 1\end{array} \rightarrow \begin{array}{cccccc} 1 & 2 & 3 & 4 & 5 & 6 \\ 4 & 1 & 2 & 6 & 5 & 3\end{array} \ \ \ \ \ (44)$

i.e., put 1,2,3 in the positions of the three 1’s in left to right order, etc. The end result is a permutation, which is the result of one round of forward X shuffle, i.e., it gives the distribution of ${\omega^{-1}}$. This is clearly the inverse of the procedure described before.
This forward shuffle can be usefully alternatively described as follows: pick ${i_1, \ldots, i_n}$ as before. Remove the first ${a_1}$ cards of the lowest symbol and place it into pile ${1}$, next ${a_2}$ cards of the second lowest symbol and put in pile ${2}$, etc, then start dropping cards from these piles one by one according to the same rule as GSR. For fixed ${a_1, \ldots, a_l}$, the number of possible shuffle outcomes (of one round) is ${\binom{n}{a_1, \ldots, a_l}}$, because that’s how many ways of intermixing these symboled cards. Also this set of permutations forms the shortest (under inversion distance) length coset representations of ${S_{a_1} \times \ldots \times S_{a_k} \subset S_n}$ (it’s clear that two different shuffle outcomes lie in different cosets because their difference do not fixed the positions of the cards within each symbol class). To show X shuffling theory is the same as quasisymmetric function theory, Stanley proved the following

Theorem 14 Fix ${x_i \ge 0}$, with ${\sum x_i =1}$, then

$\displaystyle P_x(\omega) = L_{CO(\omega^{-1})} (x_1, \ldots, x_\infty). \ \ \ \ \ (45)$

where ${CO(\omega^{-1})}$ is the CO of the descent set of ${\omega^{-1}}$.

Proof: Choose ${i_1, \ldots, i_n}$ independently with distribution given by the ${X_j}$‘s. Set ${a_j = i_{\omega^{-1}(j)}}$. If we write

$\displaystyle \begin{array}{ccc} \omega(1) & \ldots & \omega(n) \\ i_1 & \ldots & i_n \end{array} \ \ \ \ \ (46)$

then ${a_j}$ appears right below ${j}$ (check this for yourself).
Now using the standardizing interpretation of forward X shuffle, ${i_1, \ldots, i_n}$ standardizes to ${\omega}$ if and only if

1. ${a_1 \le a_2 \le \ldots \le a_n}$ and
2. ${a_j < a_{j+1}}$. for ${j \in \rm{Desc}(\omega^{-1})}$.

This takes some combinatorial thinking, first we have the following characterization of descent set of ${\omega^{-1}}$:

$\displaystyle \rm{Desc}(\omega^{-1}) = \{i: \text{ i+1 appears before i in } \omega\} \ \ \ \ \ (47)$

Basically a descent at ${j}$ indicates that ${a_{j+1}}$ will be mapped to ${j+1}$ but it appears before ${j}$ which ${a_j}$ gets mapped to. Thus if ${a_j}$ and ${a_{j+1}}$ have the same symbol, ${a_{j+1}}$ would get mapped to a number smaller than ${a_j}$ under standardization. So they must have different symbols. The first condition is clear because if ${a_1, \ldots, a_n}$ get mapped to ${1, \ldots, n}$ under standardization, they must be weakly increasing. This gives one direction of the above claim. The converse follows because all the ${a_i}$‘s of a particular symbol ${s}$ occur before the descent ${j}$ for which ${a_{j+1} > s}$; so procedurally it’s clear how the standardization of ${a_i}$‘s would look like.
The standardizations of some sequence ${a_1, \ldots, a_n}$ exhaust the possible outcomes of one X shuffle. For a particular sequence ${i_1, \ldots, i_n}$, its probability of being chosen is given by ${x_{a_1} \ldots x_{a_n}}$. Thus by the previous argument giving all sequences ${a_1, \ldots, a_n}$ that standardize to ${\omega}$,

$\displaystyle p_X(\omega) = \sum_{a_1 \le \ldots \le a_n: a_i < a_{i+1} \forall i \in D(\omega^{-1})} x_{a_1} \ldots x_{a_n}. \ \ \ \ \ (48)$

But this is just the definition of ${L_{CO(\omega^{-1})}(x_1, \ldots, x_\infty)}$. $\Box$

If we specialize to ${x_1 = x_2 = 1/2}$, then we get the usual GSR shuffle. More generally, if ${x_1 = \ldots = x_q = 1/q}$, we have

$\displaystyle P_q(\omega) = \frac{1}{q^n} \binom{q - \rm{Desc}(\omega) + n -1}{n} \ \ \ \ \ (49)$

If we let ${q \rightarrow \infty}$, we have

$\displaystyle \frac{1}{q^n} \frac{(q-D + n -1) \ldots (q- D + 1)}{n!} \rightarrow \frac{1}{n!}. \ \ \ \ \ (50)$

This is seen intuitively as follows: as ${q \rightarrow \infty}$, the chance that two ${a_i}$ are equal goes to ${0}$, then when doing the forward shuffling by dropping cards, we are essentially choosing a uniform ordering of ${1, \ldots, n}$.
Any formula involving ${P_q(\omega)}$ can be seen as a ${q}$-deformation of formula for the uniform measure.

Advertisements

## About aquazorcarson

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