[Math] what is the cycle length of the maximum normalized cycle in the directed complete graph

co.combinatoricspr.probability

Consider the complete, directed graph on $n$ vertices. Let the edge lengths $\{X_{ij}: 1 \leq i, j \leq n\}$ be i.i.d standard normal, with the constraint $X_{ij} = -X_{ji}$. The value of a normalized cycle is the sum of the edges involved, divided by the cycle length. We want to know:

For any fixed $k$ and large $n$, (of particular interest are $k = 3$ and $k = n/2$), what is the probability that the maximum normalized cycle is of length $k$?

Some thoughts:
Note that $3 \leq k \leq n$. There are $\binom{n}{k}(k-1)!$ directed cycles of length $k$ (except for $k =2$, in which we have $\binom{n}{k}$ such cycles), and each normalized cycle of length $k$ is Gaussian with variance $\frac{1}{\sqrt{k}}$. For small $k$ and large $n$, the number of directed cycles of length $k$ is approximately $n^k$. For $k = n/2$, this number is approximately $\sqrt{2}(\frac{2n}{e})^k$. Therefore, cycles of small length has the advantage of having larger variance, cycles of longer length has the advantage that there are many more of them.

To see that the dependency between cycles really matter, suppose that all cycles are independent. Since max of $m$ i.i.d Gaussian is $\sqrt{2\pi \log m}$, for small $k$, we have
$$E(\max \mbox{cycle of length k}) \approx \frac{2\sqrt{2\pi k \log(n)}}{\sqrt{k}} = 2\sqrt{2\pi \log(n)}$$.
For $k = n/2$, we have
$$E(\max \mbox{cycle of length n/2}) \approx \frac{2\sqrt{2\pi k (\log(n) + \log(2/e)}}{\sqrt{k}} = 2\sqrt{2\pi (\log(n) + \log(2/e))}$$.
But the max of $m$ i.i.d Gaussians with variance $\frac{1}{k}$ has variance $\approx \frac{1}{k}$ (Borell's inequality), therefore the difference of $\sqrt{\log (2/e)}$ will not get picked up.

Another naive approach: consider an easy union bound to get an upper bound on $E(\max \mbox{cycle of length k}) $. Let $Z$ denotes the standard normal. Then
$$
P(\exists \mbox{ a $k$-cycle } > m) \leq \binom{n}{k}(k-1)!\cdot P(Z > \sqrt{k} m) \leq \exp(k\log n – k\log C – \frac{1}{2}\log(k) – \log(m) – \frac{km^2}{2})
$$
where $C$ is some fixed constant. Solve for $m$ so that the RHS is $1$, we see that $m \approx \sqrt{2\log n}$, so this is an uninformative bound.

So one needs to take into account the dependency between cycles. But I'm quite stuck on what to do here. A quick literature search didn't return anything useful. Any ideas will be appreciated.

Thanks!

Best Answer

I wrote a program to collect some data.

For $n=8$, and $10^5$ trials, here are statistics on the longest cycles of length $k$ and the counts of the times that the cycle with the greatest normalized weight had length $k$. 

k  count         avg            std_dev
3  50415  1.40995707256456 0.277702203891974
4  30427  1.3675029633889 0.248163593506348
5  13738  1.32184789116913 0.229675012490759
6   4428  1.26765935699902 0.215218146521779
7    916  1.20083001890189 0.202927859960246
8     76  1.11148487469463 0.190259341168933

In a few cases I inspected, the largest weight cycle of length $k+1$ often shared a directed chain of $k$ vertices with the largest weight cycle of length $k$, but of course this did not always happen. There seemed to be a high correlation between the largest weights of cycles of different lengths.

For $n=10, 12, 20$, I did a restricted optimization over the cycles of length at most $6$. 

        n=10, 10^5 trials
k  count         avg            std_dev
3  44788 1.56377702460182 0.258071707092035
4  30386 1.53787677069062 0.228885384830286
5  16974 1.50659766688642 0.212244752764919
6   7852 1.4715247336037 0.199249497688295

        n=12, 10^5 trials
k  count         avg            std_dev
3  41207 1.67848840347225 0.244485830656911
4  29722 1.66261483794121 0.21443274525213
5  18687 1.64098125565814 0.198203806693267
6  10384 1.61519351038532 0.186681888604542

        n=20, 2000 trials
k  count         avg            std_dev
3    667 1.97010656830871 0.212728229010943
4    584 1.97273614009628 0.18001851348712
5    418 1.96707199503644 0.16332139093596
6    331 1.95442360307882 0.154839166051771
Related Question