Universiteit Utrecht

Department of Mathematics


Coherent permutations with descent statistic



Sasha Gnedin (UU)
8 June 2005

This talk is based on a recent joint work with Grigori Olshanski.

We are interested in sequences  Pi = (Pi_n, n=1,2,...)  of random permutations of  [n]'s which satisfy
 (i)  Pi_n  is obtained from  Pi_{n+1}  by removing element  n+1,
(ii) conditionally given the allocation of descent positions, the distribution of  Pi_n  is uniform.

The problem of describing all distributions for such  Pi  has many faces and is related to
- certain Markov chains on the graph of ribbon diagrams,
- random card-shuffling algorithms,
- breaking ties in the data sampled from discrete distributions,
- positive characters of the algebra of quasisymmetric functions.

We present a constructive solution which complements known results on the boundary problems for Young's lattice, partition structures and composition structutes.


Back to the history of the seminar or the Colloquium Stochastiek homepage.
Yuri Yakubovich