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.


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