Random permutations and giant cycles

The other day, Nathanael Berestycki presented some very nice results on random permutations. Start with the identity permutation of ${\mathfrak{S}_N}$ and compose with random transpositions: in short, at time ${k}$ we consider the random permutation ${\sigma_k = \tau_k \circ \ldots \tau_{2} \circ \tau_1}$ where ${\tau_i}$ is a transposition chosen uniformly at random among the ${\frac{N(N-1)}{2}}$ transpositions of ${\mathfrak{S}_N}$. How long do we have to wait before seeing a permutation that has a cycle of length greater than ${\epsilon N}$, where ${\epsilon>0}$ is a fixed constant ?

The answer has been known for quite a long time (O. Schramm,2005), but no simple proof was available: the highlight of Nathanael’s talk was a short and elegant proof of the fact that we only have to wait a little bit more than ${N/2}$ steps to see this giant cycle! The first half of the proof is such a beauty that I cannot resist in sharing it here!

1. Visual representation

First, this is more visual to represent a permutation by its cycle decomposition. Consider for example the permutation ${\sigma = (1,3,4)(5,6,8,9,10,11)(2)(7) \in \mathfrak{S}_{10}}$ that sends ${1 \rightarrow 3 \rightarrow 4 \rightarrow 1}$ etc… It can be graphically represented by the following pictures:

cycle structure - visual representation

If this permutation is composed with the transposition ${(4,6)}$ , this gives the following cycle structure:

two cycles merge

If  it is composed with ${(8,11)}$ this gives,

a cycles breaks down into two

It is thus pretty clear that the cycle structure of ${\sigma_{k+1}}$ can be obtained from the cycle structure of ${\sigma_k}$ in only 2 ways:

• or two cycles of ${\sigma_k}$ merge into one,
• or one cycle of ${\sigma_k}$ breaks into two cycles.

In short, the process ${\{\sigma_k\}_k}$ behaves like a fragmentation-coalescence processes. At the beginning, the cycle structure of ${\sigma_0=\text{Id}}$ is trivial: there are ${N}$ trivial cycles of length one! Then, as times goes by, they begin to merge, and sometimes they also break down. At each step two integers ${i}$ and ${j}$ are chosen uniformly at random (with ${i \neq j}$): if ${i}$ and ${j}$ belong to the same cycle, this cycle breaks into two parts. Otherwise the cycle that contains ${i}$ merges with the cycle that contains ${j}$. Of course, since at the beginning all the cycles are extremely small, the probability that a cycles breaks into two part is extremely small: a cycle of size ${k}$ breaks into two part with probability roughly equal to ${\Big(\frac{k}{N}\Big)^2}$.

2. Comparison with the Erdos-Renyi random Graph

Since the fragmentation part of the process can be neglected at the beginning, this is natural to compare the cycle structure at time ${k}$ with the rangom graph ${G(N,p_k)}$ where ${\frac{N(N-1)}{2}p_k = k}$: this graph has ${N}$ vertices and roughly ${k}$ edges since each vertex is open with probability ${p_k}$. A coupling argument makes this idea more precise:

1. start with ${\sigma_0=\textrm{Id}}$ and the graph ${G_0}$ that has ${N}$ disconnected vertices ${\{1,2, \ldots, N\}}$
2. choose two different integers ${i \neq j}$
3. define ${\sigma_{k+1}=(i,j) \circ \sigma_k}$
4. to define ${G_{k+1}}$, take ${G_k}$ and join the vertices ${i}$ and ${j}$ (never mind if they were already joined)
5. go to step ${2}$.

The fundamental remark is that each cycle of ${\sigma_k}$ is included in a connected component of ${G_k}$: this is true at the beginning, and this property obviously remains true at each step. The Erdos-Renyi random graph ${G(n,p)}$ is one of the most studied object: it is well-known that for ${c<1}$, with probability tending to ${1}$, the size of the largest connected component of ${G(N,\frac{c}{N})}$ is of order ${\ln(N)}$. Since ${p_k \sim \frac{2k}{N^2}}$, this immediately shows that for ${k \approx \alpha N}$, with ${\alpha < \frac{1}{2}}$ the length of the longuest cycle in ${\sigma_k}$ is of order ${\ln(N)}$ or less. This is one half of the result. It remains to work a little bit to show that if we wait a little bit more than ${\frac{N}{2}}$, the first cycle of order ${N}$ appears.

For a permutation ${\sigma \in \mathfrak{S}_N}$ with cycle decomposition ${\sigma = \prod_{j=1}^r c_i}$ (cycles of length ${1}$ included), one can consider the quantity

$\displaystyle T(\sigma) = \sum_{j=1}^R |c_j|^2.$

This is a quantity between ${N}$ (for the identity) and ${N^2}$ that measures in some extends the sizes of the cycles. In order to normalize everything and to take into account that the cycle structure abruptly changes near the critical value ${\frac{N}{2}}$, one can also observe this quantity on a logarithmic scale:

$\displaystyle s(\sigma) = \frac{ \ln\Big( T(\sigma)/N^2 \Big) }{\ln(N)}.$

This quantity ${s(\sigma)}$ lies between ${0}$ and ${1}$, and evolves quite smoothly with time: look at what it looks like, once the time has been rescaled by a factor ${N}$:

fluid limit ?

The plot represented the evolution of the quantity ${s\Big(\sigma(\alpha N)\Big)}$ between time $k=0$ and $k=\frac{N}{2}$ for dimensions $N=10000,20000,30000$.

Question: does the random quantity $s(\alpha,N)={s\Big(\sigma(\alpha N)\Big)}$ converge (in probability) towards a non trivial constant ${S(\alpha) \in (0,1)}$ ? It must be the analogue quantity for the random graph ${G(N,\frac{2\alpha}{N})}$, so I bet it is a known result …

Brownian particles on a circle

Today, James norris gave a talk related to Diffusion-limited aggregation processes and mentioned, in passing, the following amusing fact: put ${N}$ equidistant Brownian particles ${W_1, \ldots, W_N}$ on the circle with unit circumference and let them evolved. When two of them collide they get stuck to each other and continue together afterwards: after a certain amount of time ${T_N}$, only one particle remains. Perhaps surprisingly, this is extremely easy to obtain the first few properties of ${T_N}$. For example, ${\lim_N \mathop{\mathbb E}\left[ T_N \right] = \frac{1}{6}}$.

To see that, define ${D_k}$ the distance between ${W_k}$ and ${W_{k+1}}$ (modulo ${N}$) so that ${D_k = \frac{1}{N}}$ for ${k=1,2 \ldots, N}$. Notice then (It\^o’s formula) that

$\displaystyle M_t = e^{\lambda t} \sum_{k=1^N} \sin(\sqrt{\lambda} D_k)$

is a (local) martingale that starts from ${M_0 = N \sin(\frac{\sqrt{\lambda}}{N})}$. Also, at time ${T_N}$, exactly ${N-1}$ of the distances ${D_1, D_2, \ldots, D_N}$ are equal to ${0}$ while one of them is equal to ${1}$: this is why ${M_{T_N} = e^{\lambda T_N} \sin(\sqrt{\lambda})}$. The end is clear: apply the optional sampling theorem (to be rigorous, take ${\lambda}$ not too big, or do some kind of truncations to be sure that the optional sampling theoem applies) to conclude that

$\displaystyle \mathop{\mathbb E}\left[ e^{\lambda T_N} \right] = \frac{N \sin(\frac{\sqrt{\lambda}}{N})}{\sin(\sqrt{\lambda})}.$

This gives for example ${\mathop{\mathbb E}\left[ T_N \right] = \frac{1}{6}(1-\frac{1}{N^2})}$. I just find it cute!

So what if we do that on a segment ?