Seminar: Functional graph, shuffling, and mixing rate

Speaker: Claude Gravel

Title: Functional graph, shuffling, and mixing rate

Abstract: Given a function from a finite set $A$ to a finite set $B$, we can represent it using its functional graph, which consists of irreducible components. Each component consists of a cycle to which are attached trees. Several results are known about the behaviour of the asymptotic expected height of the trees, length of the cycles, etc., with respect to the sizes of $A$ and $B$ when sampling uniformly a random function. Given some subset, say $K$, of $B^{A}$ functions, we can analyze the properties above with respect to $K$. For instance, $K$ could be a particular subset of the permutations over $A$. $K$ could be those permutations obtained from some shuffling methods, for example, the Gilbert-Shannon-Reed model for manually shuffling a deck of $n$ cards. How many times should the shuffling algorithm be repeated so that the output distribution is close in some sense to the uniform distribution over permutations; this is the mixing rate. We explore some open questions regarding the mixing rate for shuffling methods with application to cryptography. In this talk, $A$ and $B$ are vector spaces over finite fields.