¿cuál es la longitud del ciclo máximo normalizado en el grafo completo dirigido?

Question

Consideremos el grafo completo y dirigido de $n$ vértices. Sean las longitudes de las aristas $\{X_{ij}: 1 \leq i, j \leq n\}$ sea i.i.d normal estándar, con la restricción $X_{ij} = -X_{ji}$ . El valor de a ciclo normalizado es la suma de las aristas implicadas, dividida por la longitud del ciclo. Queremos saber:

Para cualquier $k$ y grandes $n$ (de especial interés son $k = 3$ y $k = n/2$ ), ¿cuál es la probabilidad de que el ciclo máximo normalizado sea de longitud $k$ ?

Algunas reflexiones: Tenga en cuenta que $3 \leq k \leq n$ . Existen $\binom{n}{k}(k-1)!$ ciclos dirigidos de longitud $k$ (excepto para $k =2$ en la que tenemos $\binom{n}{k}$ tales ciclos), y cada ciclo normalizado de longitud $k$ es gaussiano con varianza $\frac{1}{\sqrt{k}}$ . Para los pequeños $k$ y grandes $n$ el número de ciclos dirigidos de longitud $k$ es aproximadamente $n^k$ . Para $k = n/2$ este número es aproximadamente $\sqrt{2}(\frac{2n}{e})^k$ . Por lo tanto, los ciclos de pequeña longitud tienen la ventaja de tener mayor varianza, los ciclos de mayor longitud tienen la ventaja de que hay muchos más.

Para ver que la dependencia entre ciclos realmente importa, supongamos que todos los ciclos son independientes. Como el máximo de $m$ i.i.d Gaussiana es $\sqrt{2\pi \log m}$ para pequeños $k$ tenemos $$E(\max \mbox{cycle of length k}) \approx \frac{2\sqrt{2\pi k \log(n)}}{\sqrt{k}} = 2\sqrt{2\pi \log(n)}$$ . Para $k = n/2$ tenemos $$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))}$$ . Pero el máximo de $m$ Gaussianos i.i.d con varianza $\frac{1}{k}$ tiene varianza $\approx \frac{1}{k}$ (desigualdad de Borell), por lo que la diferencia de $\sqrt{\log (2/e)}$ no se recogerá.

Otro enfoque ingenuo: considerar un límite de unión fácil para obtener un límite superior en $E(\max \mbox{cycle of length k}) $ . Sea $Z$ denota la normal estándar. Entonces $$ 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}) $$ donde $C$ es una constante fija. Resolver para $m$ de modo que el lado derecho es $1$ vemos que $m \approx \sqrt{2\log n}$ por lo que se trata de un límite poco informativo.

Así que hay que tener en cuenta la dependencia entre ciclos. Pero no sé qué hacer. No he encontrado nada útil en la bibliografía. Cualquier idea será bienvenida.

Merci !

Answer 1

Escribí un programa para recoger algunos datos.

Para $n=8$ y $10^5$ ensayos, aquí están las estadísticas sobre los ciclos más largos de longitud $k$ y los recuentos de las veces que el ciclo con mayor peso normalizado tuvo longitud $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

En algunos casos que inspeccioné, el mayor ciclo de peso de longitud $k+1$ a menudo compartían una cadena dirigida de $k$ vértices con el mayor ciclo de peso de longitud $k$ pero, por supuesto, no siempre fue así. Parecía haber una alta correlación entre los mayores pesos de los ciclos de diferentes longitudes.

Para $n=10, 12, 20$ hice una optimización restringida sobre los ciclos de longitud máxima $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

Answer 2

Esto era demasiado largo para un comentario. (He ignorado la direccionalidad de los bordes - no estoy seguro de que importe)

Tomar el máximo de variables i.i.d. reduce la varianza. Como $k$ se incrementa, se toma el máximo de un mayor número de v.a.r., cada una ya con una varianza menor, por lo que la varianza global se reduce aún más. Digamos $y_N$ es el máximo de $m$ Gaussianos i.i.d. cada uno $N(0,\sigma^2)$ , tienes $E[y_N] \sim \sigma \sqrt{2\log m}$ y $V[y_N] \sim \sigma/\sqrt{2\log m}$ . Utilizando una aproximación (muy) burda $\binom n k = n^k$ se puede aproximar la media y la varianza del ciclo máximo de longitud $k$ la media es $E_k \sim \sqrt{2 \log n}$ tan independiente de $k$ (similar a la que tienes), pero la varianza $V_k \sim \frac{1}{k \sqrt{2 \log n}}$ depende de $k$ . Por lo tanto, al menos bajo la aproximación i.i.d, los ciclos más grandes dan una varianza más pequeña por lo tanto más pequeños $k$ tienen más probabilidades de dar el máximo ( $k=2$ la más probable).

Answer 3

Espero que alguien se haga eco de estas ideas y las utilice, de modo que la pregunta obtenga respuesta y deje de estar en el candelero.

Fijemos n=4 y analicemos 3 ciclos frente a 4 ciclos. Ordena las etiquetas de modo que 4 de los valores normalizados para los 3 ciclos sean a,b,c,y d, y que se cumplan las siguientes relaciones: a+b+c+d=0, y los valores para 3 de los 4 ciclos sean 3/4 veces uno de (a+b), (a+c), o (-b-c). Si a es el mayor valor, entonces b y c tienen que ser menores que a/3 y su suma mayor que -4a/3 para que los 3 ciclos ganen el premio al máximo valor normalizado. Se podrían calcular las probabilidades para este caso, y luego hacer una comparación similar entre pares de k ciclos y (2k-2l) ciclos para elecciones juiciosas de k, l y n. Mi intuición al respecto es pobre, pero me sugiere que 4 ciclos tienen una ligera ventaja sobre 3 ciclos para n=4 e incluso para n más grande. Tal vez sea posible construir un conjunto de relaciones de tipo inclusión-exclusión para n+1 a partir de las relaciones para n.

Gerhard "Someone Take The Baton Now" Paseman, 2012.08.07