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.