21
$\begingroup$

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!

$\endgroup$
7
  • $\begingroup$ Sounds interesting - what is the role of edge directions? How do you determine the orientation of edges - do you randomize these as well? shouldn't all directed cycles on the same k nodes have the same value? wouldn't it be more natural to look at the undirected case? $\endgroup$
    – Or Zuk
    May 16, 2011 at 22:16
  • 1
    $\begingroup$ One thought: For any $k$ you can get a simple upper bound on the heaviest cycle by looking at the average of the $k$ heaviest edges. If $k$ tends to infinity fast enough (e.g. like a constant fraction of $n$), this should be $o(\log n)$. Conversely, there's likely to be at least one edge of weight $C \log n$ if $C$ is small. If you take the best (or even a random) triangle containing that edge, you'll still be order $\log n$. $\endgroup$ May 16, 2011 at 22:51
  • $\begingroup$ To Kevin: Sorry I don't see why it's $\log n$. Shouldn't it be of order $\sqrt{\log n}$? (max of n i.i.d Gaussians?) To Or Zuk: the edge directions are fixed. You can think about this as being an undirected graph, allowing edges with negative edge length, with the condition $X_{ij} = -X_{ji}$. No, not all directed cycles on the same $k$ nodes have the same value: the order of the edge tranversal matter: for instance, the cycle 1 -> 2 -> 3 -> 4 -> 1 has value: 12 + 23 + 34 + 41, while the cycle 1 -> 3 -> 2 -> 4 -> 1 has value: 13 + 32 + 24 + 41 = 13 - 23 + 34 + 41. $\endgroup$ May 17, 2011 at 13:40
  • $\begingroup$ One approach I considered was to take the largest edge, then the second largest edge, etc. until these edges form a cycle. This will form a cycle whose maximum normalization is relatively large. What is the distribution of lengths of this cycle? However, the cycle with the greatest normalized weight does not need to be of this form. $\endgroup$ Mar 19, 2013 at 5:21
  • $\begingroup$ By the way, there is a related question about random matrices. Consider a random matrix with lognormal $\exp(N(0,\sigma^2))$ entries off the diagonal so that $a_{ij} = 1/a_{ji}$. As $\sigma^2\to \infty$, how does the largest eigenvalue behave? The largest eigenvalue is closely related to the maximum normalized cycle in this question. $\endgroup$ Apr 16, 2013 at 4:07

3 Answers 3

1
$\begingroup$

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
$\endgroup$
0
$\begingroup$

This was too long for a comment. (I ignored edge directionality - not sure it matters)

Taking the maximum of i.i.d. variables reduces the variance. As $k$ is increased, you take the maximum of a larger number of r.v.s., each already with a smaller variance, so the overall variance is further reduced. Say $y_N$ is the maximum of $m$ i.i.d. Gaussians each $N(0,\sigma^2)$, you have $E[y_N] \sim \sigma \sqrt{2\log m}$ and $V[y_N] \sim \sigma/\sqrt{2\log m}$. Using a (very) crude approximation $\binom n k = n^k$ you can approximate the mean and variance of the maximal cycle of length $k$: the mean is $E_k \sim \sqrt{2 \log n}$ so independent of $k$ (similar to what you've got), but the variance $V_k \sim \frac{1}{k \sqrt{2 \log n}}$ does depend on $k$. Therefore, at least under the i.i.d approximation, larger cycles give a smaller variance thus smaller $k$'s are more likely to give the maximum ($k=2$ the most likely).

$\endgroup$
3
  • $\begingroup$ Note that 2-cycles have value 0 due to the constraint $X_{ij} = -X_{ji}$, for $k \geq 3$. Why is the more concentrated cycle more likely to win? In general, if we have two random variables $X$ and $Y$ of the same mean, but $Var(X) < Var(Y)$, I don't think it's true that $P(X > Y) > 1/2$. (For example, take two independent R.V. symmetric about 0, then this probability is exactly 1/2 regardless of what the variance of $X$ and $Y$ are). $\endgroup$ May 17, 2011 at 13:43
  • $\begingroup$ Thanks for the clarification on directionality, so yes k≥3, but if you fix k and take n→∞, the asymptotics still doesn't change (nk becomes an even better approximation). Of course the independence approximation is more questionable (since many cycles use the same set of edges). I meant that the LESS concentrated cycle is more likely to win. This isn't true for just 2 variables, but if you've got many variables all with the same mean, the higher the variance is, the more likely you're to be the maximum (I didn't try to quantify it - the effect might be small). $\endgroup$
    – Or Zuk
    May 17, 2011 at 20:23
  • $\begingroup$ Yes sorry, I meant the less concentrated cycle. I agree that the effect is probably small. For concreteness, take m independent Gaussians $X_1, \ldots, X_m$, all have mean 0 but different variance. Then $X_1$ would win if the $m-1$-dimensional Gaussian $Y := (Y_2, \ldots, Y_m) = (X_1 - X_2, \ldots, X_1 - X_m)$ is elementwise positive. That is, $X_1$ wins with probability $P(Y_i > 0 \forall i)$. Now $Cov(Y_i, Y_j) = Var(X_1)$, so by Slepian's lemma $X_i$ with largest variance is most likely to win. (I'll have to think about how to quantify this though) $\endgroup$ May 18, 2011 at 8:53
0
$\begingroup$

I'm hoping someone will take these thoughts and run with them, so that eventually the question gets answered and stops bumping to the top.

Let's set n=4 and look at 3 cycles vs 4 cycles. Arrange labeling so that 4 of the normalized values are for the 3-cycles are a,b,c,and d, and so that the following relations hold: a+b+c+d=0, and the values for 3 of the 4-cycles are 3/4 times one of (a+b), (a+c), or (-b-c). If a is the largest value, then b and c have to be smaller than a/3 and their sum bigger than -4a/3 in order for the 3 cycles to win the prize for maximal normalized value. One might be able to work out the probabilities for this case, and then make a similar comparison between pairs of k cycles and (2k-2l) cycles for judicious choices of k, l, and n. My intuition on this is poor, but it suggests to me that 4 cycles have a slight edge on 3-cycles for n=4 and even for larger n. It may be possible to build up a set of inclusion-exclusion type relations for n+1 based on the relations for n.

Gerhard "Someone Take The Baton Now" Paseman, 2012.08.07

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.