Gráfico aleatorio

En matemáticas , un gráfico aleatorio es un gráfico que se genera mediante un proceso aleatorio . El primer modelo de gráficos aleatorios fue popularizado por Paul Erdős y Alfréd Rényi en una serie de artículos publicados entre 1959 y 1968.

Los dos modelos básicos de Erdős y Rényi

El modelo de Erdős y Rényi, de hecho, reúne dos modelos, formalmente diferentes, pero estrechamente relacionados. En ambos modelos,

el conjunto de vértices es ${1, 2, 3, ..., n }$ denotado por lo siguiente ; ${\ Displaystyle \ [\! [n] \!]}$
los bordes potencialmente presentes son las $n ( n -1) / 2$ partes de dos elementos de ; a veces se indica el conjunto de estos bordes , pero se indicará $J$ por conveniencia tipográfica y por coherencia con el artículo sobre la desigualdad de Harris . ${\ Displaystyle \ [\! [n] \!]}$ ${\ displaystyle {[\! [n] \!] \ elige 2}.}$
por tanto, el gráfico aleatorio no está dirigido y no tiene bucles ni bordes múltiples .

El gráfico aleatorio binomial

En este modelo, a menudo cada uno de los $n$ $($ $n$ $-1) / 2$ bordes está presente con probabilidad $p$ , ausente con probabilidad $1-$ $p$ , independientemente del estado de los otros bordes. El caso $p$ $= 0,5$ fue estudiado por Erdős ya en 1947. El número $N$ $p$ de aristas sigue la distribución binomial de los parámetros $n$ $($ $n$ $-1) / 2$ y $p$ . ${\ Displaystyle \ mathbb {G} (n, p),}$ ${\ Displaystyle \ mathbb {G} (n, p)}$

El gráfico aleatorio uniforme

En este modelo, mencionado a menudo, elegimos uniformemente un subconjunto de M aristas entre las $n$ $($ $n$ $-1) / 2$ aristas posibles. Cuando una gráfica G con n vértices tiene M aristas, la probabilidad de G viene dada por ${\ Displaystyle \ mathbb {G} (n, M),}$

{\ Displaystyle \ mathbb {P} (G) \ = \ {\ frac {1} {{n \ choose 2} \ choose M}}.}

Este es el modelo que se estudia principalmente en la serie de artículos seminales publicados por Erdős y Rényi entre 1959 y 1968. ${\ Displaystyle \ mathbb {G} (n, M)}$

Los dos procesos aleatorios con valores gráficos

Podemos partir de un gráfico sin aristas, por lo tanto completamente desconectado, y añadir una arista dibujada al azar de manera uniforme, luego otra, etc. , sin reemplazo. Obtenemos así una secuencia creciente (en el sentido de la inclusión del conjunto de aristas), de $1 +$ $n$ $($ $n$ $-1) / 2$ gráficas aleatorias, que forma un proceso de tiempo discreto con valores en el conjunto de gráficas . Cada término de la secuencia es un gráfico aleatorio uniforme definido en la sección anterior. Una ventaja de esta construcción es ver diferentes gráficos aleatorios con diferentes parámetros M coexistir , en un mismo espacio de probabilidad, y poder comparar sus características, no en promedio o en ley, sino para cada elemento ω del espacio de probabilidad considerado. . Esto permite razonar por acoplamiento. ${\ Displaystyle \ {\ mathbb {G} (n, M) \} _ {0 \ leq M \ leq n (n-1) / 2},}$
También podemos asociar con cada arista e de J una variable aleatoria $T e$ , el peso de la arista, de modo que la familia $( T e ) e \in J$ es una familia de variables aleatorias iid, por ejemplo con una ley uniforme sobre l ' intervalo [0, 1]. Luego denotamos la gráfica formada por las aristas cuyo peso es menor que p . Para cada borde, esto sucede con probabilidad ${\ Displaystyle \ mathbb {G} (n, p)}$

{\ Displaystyle \ mathbb {P} (T_ {e} \ leq p) \ = \ p.}

Obtenemos así una familia creciente, de gráficas aleatorias, que forma un proceso de tiempo continuo, con valores en el conjunto de gráficas. Esta familia está aumentando en el sentido de la inclusión del conjunto de aristas: una arista e presente en también está presente en ya que Cada término de la familia de grafos es un grafo aleatorio binomial definido previamente.

{\ Displaystyle \ {\ mathbb {G} (n, p) \} _ {0 \ leq p \ leq 1},}

{\ Displaystyle \ mathbb {G} (n, p)}

{\ Displaystyle \ mathbb {G} (n, p + \ varepsilon), \ \ varepsilon> 0,}

{\ Displaystyle \ {T_ {e} \ leq p \} \ \ Rightarrow \ \ {T_ {e} \ leq p + \ varepsilon \}.}

Metáfora. Podemos imaginar los vértices del gráfico como n islas en un lago, que se comunican con la ayuda de pasarelas (bordes e ), sumergidas a las respectivas profundidades $T e$ debajo de la superficie del agua. Si el lago se vacía gradualmente de agua, veremos que los puentes emergen gradualmente y se forman componentes relacionados que unen más y más islas.

Vínculos entre los dos modelos

En virtud del Teorema del límite central , o la desigualdad de Hoeffding , la ley del binomio está muy concentrada en torno a su expectativa. Más precisamente, el número de aristas $N p$ de un gráfico de ley aleatoria es, por tanto, muy cercano, especialmente si esta última cantidad es grande delante de n : ${\ Displaystyle \ mathbb {G} (n, p)}$ ${\ Displaystyle {\ hat {M}} = \ left \ lfloor p \ {n \ Choose 2} \ right \ rfloor}$ ${\ hat {M}}$

{\ Displaystyle \ forall t> 0, \ qquad \ mathbb {P} \ left (\ left | N_ {p} - {\ hat {M}} \ right | \ geq tn \ right) \ \ leq \ 2 \, \ mathrm {e} ^ {- 2t ^ {2}}.}

Además, la distribución condicional de saber que $N$ $p$ $= M$ es precisamente Por esta razón, si $M$ está cerca o, de manera equivalente, si ${\ Displaystyle \ \ mathbb {G} (n, p)}$ ${\ Displaystyle \ mathbb {G} (n, M).}$ ${\ hat {M}}$

{\ Displaystyle p \ simeq {\ frac {2M} {n (n-1)}},}

En general se acepta (y a menudo demostrado) que los dos modelos y tienen propiedades muy similares. ${\ Displaystyle \ mathbb {G} (n, p)}$ ${\ Displaystyle \ mathbb {G} (n, M)}$

Yendo más allá, denote por $T ( k )$ el k -ésimo valor de la secuencia una vez que esta última secuencia está dispuesta en orden ascendente: la secuencia se llama secuencia de orden estadístico de la secuencia Cuando p toma el valor aleatorio $T$ $($ $M$ $)$ , Entonces es exactamente Para corroborar las observaciones anteriores, tenga en cuenta que $T$ $($ $M$ $)$ está muy cerca en el sentido de que, como consecuencia de los famosos resultados de Donsker y Kolmogorov , la probabilidad ${\ Displaystyle (T_ {e}) _ {e \ in J}}$ ${\ Displaystyle (T _ {(k)}) _ {1 \ leq e \ leq n (n-1) / 2}}$ ${\ Displaystyle (T_ {e}) _ {e \ in J}.}$ ${\ Displaystyle \ mathbb {G} (n, T _ {(M)})}$ ${\ Displaystyle \ mathbb {G} (n, M).}$ ${\ Displaystyle 2M / n (n-1),}$

{\ Displaystyle \ varphi _ {n} (x) = \ mathbb {P} \ left (\ sup _ {1 \ leq M \ leq n (n-1) / 2} \ left \ {| T _ {(M )} - {\ tfrac {2M} {n (n-1)}} | \ right \} \ geq {\ tfrac {x {\ sqrt {2}}} {n}} \ right)}

satisfecho

{\ Displaystyle \ exp (-2x ^ {2}) \ \ leq \ \ liminf _ {n} \ varphi _ {n} (x) \ \ leq \ \ limsup _ {n} \ varphi _ {n} (x ) \ \ leq \ 2 \ sum _ {r = 1} ^ {+ \ infty} (- 1) ^ {r-1} \ exp (-2r ^ {2} x ^ {2}),}

la 1 st y 4 th términos siendo las colas de la distribución de los Rayleigh y Kolmogorov leyes , respectivamente: en resumen, el supremo (cuando M varía) de los errores es del orden de 1 / n . ${\ Displaystyle | T _ {(M)} - 2M / n (n-1) |}$

Orden y crecimiento

Un gráfico puede verse como una parte del conjunto J de bordes, por lo que el espacio de probabilidad es aquí omega todas las partes de J , que a veces pueden identificar ${0,1} J$ . Esta identificación es particularmente útil cuando queremos aplicar la desigualdad de Harris .

La inclusión es una relación de orden parcial en Ω.
Como es habitual, se dice que un mapa X definido en Ω, con valores reales, aumenta si

{\ Displaystyle \ {\ omega \ leq \ omega ^ {\ prime} \} \ quad \ Rightarrow \ quad \ {X (\ omega) \ leq X (\ omega ^ {\ prime}) \}.}

Se dice que una parte A de Ω aumenta si

{\ Displaystyle \ {\ omega \ leq \ omega ^ {\ prime} \ {\ text {y}} \ \ omega \ in A \} \ quad \ Rightarrow \ quad \ {\ omega ^ {\ prime} \ in A \}.}

De manera equivalente, se dice que una parte A de Ω aumenta si su función indicadora aumenta.

La propiedad de degradación de una aplicación o pieza tiene una definición análoga.

Ejemplos:

Entre las propiedades y parámetros de un gráfico,

la conectividad está aumentando, es decir la parte A de Ω formada por todas las gráficas conectadas, es una parte creciente de Ω: si agregamos una arista a una gráfica conectada, la gráfica así obtenida sigue conectada;
la planaridad es decreciente: si eliminamos una arista de un gráfico plano, el gráfico así obtenido sigue siendo plano;
el número cromático está aumentando;
el número de estabilidad está disminuyendo;
la propiedad libre de triángulos está disminuyendo.

Tenemos la siguiente desigualdad:

Desigualdad de Harris : en el marco del gráfico aleatorio binomial ,

es decir, dos variables aleatorias X e Y que aumentan en Ω. Entonces

{\ Displaystyle \ mathbb {E} [XY] \ geq \ mathbb {E} \ left [X \ right] \ mathbb {E} [Y] \,;}

es decir dos partes crecientes A y B de Ω. Entonces

{\ Displaystyle \ mathbb {P} (A \ cap B) \ geq \ mathbb {P} (A) \ mathbb {P} (B).}

Notas:

Esto equivale a decir que existe una correlación positiva entre las variables en cuestión, ya que podemos reformular la primera desigualdad de la siguiente forma utilizando la covarianza :

{\ Displaystyle {\ text {Cov}} \ left (X, Y \ right) \ \ geq \ 0.}

La desigualdad también es válida para las variables o partes decrecientes, pero el significado de las desigualdades cambia cuando las variables o partes involucradas tienen significados opuestos de monotonía.

Conectividad

El umbral de conectividad

Teorema (Erdős, Rényi, 1960) - Sea $a n = np ( n ) - ln n$ , o nuevamente:

{\ Displaystyle p (n) \ = \ {\ frac {\ ln n} {n}} \, + \, {\ frac {a_ {n}} {n}}.}

Si entonces ${\ Displaystyle \ lim _ {n} a_ {n} = + \ infty,}$ ${\ Displaystyle \ lim _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left (p (n), n \ right) \ mathrm {~ está ~ relacionado} \ right) = 1.}$
Si entonces ${\ Displaystyle \ lim _ {n} a_ {n} = - \ infty,}$ ${\ Displaystyle \ lim _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left (p (n), n \ right) \ mathrm {~ está ~ relacionado} \ right) = 0.}$

Decimos que $ln ( n ) / n$ es un umbral estrecho para la propiedad de conectividad, la estrechez se refiere al hecho de que la propiedad se satisface incluso si tiende al infinito estrictamente menos rápido que $año$ ${\ Displaystyle \ ln n.}$

Demostración

Nos damos un gráfico aleatorio G n con ley y un gráfico aleatorio con ley. El teorema se deriva del teorema doble exponencial , que a su vez se deriva de la enumeración de puntos aislados realizada en la siguiente sección. La conectividad es una propiedad creciente , por lo tanto, tan pronto como n sea lo suficientemente grande como para ${\ Displaystyle \ mathbb {G} \ left (p (n), n \ right)}$ ${\ Displaystyle {\ tilde {G}} _ {n}}$ ${\ Displaystyle \ mathbb {G} \ left ({\ tilde {p}} (n), n \ right).}$

{\ Displaystyle p (n) \ = \ {\ frac {\ ln n} {n}} \, + \, {\ frac {a_ {n}} {n}} \ quad \ geq \ quad {\ frac { \ ln n} {n}} + {\ frac {c} {n}} + {\ frac {\ varepsilon (n)} {n}} \ = \ {\ tilde {p}} (n),}

también tenemos

{\ Displaystyle \ mathbb {P} \ left (G_ {n} \ mathrm {~ está ~ relacionado} \ right) \ geq \ mathbb {P} \ left ({\ tilde {G}} _ {n} \ mathrm { ~ está ~ relacionado} \ derecha).}

De hecho, incluso si eso significa construir y usar las mismas variables uniformes iid , en el mismo espacio de probabilidad Ω, como se indica en la sección “Los dos procesos aleatorios con valores gráficos” , tenemos, para todo ω de Ω, $G_ {n}$ ${\ Displaystyle {\ tilde {G}} _ {n}}$ ${\ Displaystyle (U_ {e}) _ {e \ in J}}$

{\ Displaystyle G_ {n} (\ omega) \ supset {\ tilde {G}} _ {n} (\ omega),}

Entonces

{\ Displaystyle \ left \ {{\ tilde {G}} _ {n} (\ omega) {\ text {está relacionado}} \ right \} \ Rightarrow \ left \ {G_ {n} (\ omega) \ mathrm {~ está ~ relacionado} \ right \},}

{\ Displaystyle \ mathbb {P} \ left ({\ tilde {G}} _ {n} \ mathrm {~ está ~ relacionado} \ right) \ leq \ mathbb {P} \ left (G_ {n} \ mathrm { ~ está ~ relacionado} \ derecha).}

Si se sigue que, para cualquier número real c , ${\ Displaystyle \ lim _ {n} a_ {n} = + \ infty,}$

{\ Displaystyle \ liminf _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left (p (n), n \ right) \ mathrm {~ está ~ relacionado} \ right) \ geq \ mathrm { e} ^ {- \ mathrm {e} ^ {- c}},}

o incluso

{\ Displaystyle \ liminf _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left (p (n), n \ right) \ mathrm {~ está ~ relacionado} \ right) \ geq \ sup \ izquierda \ {\ mathrm {e} ^ {- \ mathrm {e} ^ {- c}} \, | \, c \ in \ mathbb {R} \ right \} \ = \ 1.}

Por otro lado, si entonces, para n suficientemente grande, tendremos, para todo ω , y ${\ Displaystyle \ lim _ {n} a_ {n} = - \ infty,}$ ${\ Displaystyle G_ {n} (\ omega) \ subconjunto {\ tilde {G}} _ {n} (\ omega),}$

{\ Displaystyle \ mathbb {P} \ left ({\ tilde {G}} _ {n} \ mathrm {~ está ~ relacionado} \ right) \ geq \ mathbb {P} \ left (G_ {n} \ mathrm { ~ está ~ relacionado} \ derecha).}

Por lo tanto, para cualquier número real c ,

{\ Displaystyle \ limsup _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left (p (n), n \ right) \ mathrm {~ está ~ relacionado} \ right) \ leq \ inf \ izquierda \ {\ mathrm {e} ^ {- \ mathrm {e} ^ {- c}} \, | \, c \ in \ mathbb {R} \ right \} \ = \ 0.}

Enumeración de puntos aislados

Es más fácil (más probable) tener éxito en cortar las n - 1 conexiones entre un punto y su complemento, que las k ( n - k ) conexiones entre un grupo de k puntos y su complemento, porque la función $f ( k ) = k ( n - k )$ aumenta muy rápidamente alrededor de 1, por lo tanto, a medida que k aumenta, hay muchos más bordes para cortar y una probabilidad mucho menor de cortarlos todos con éxito. Como corolario, con la elección del parámetro p realizada anteriormente, el gráfico G ( n , p ) estará desconectado “casi solo” si tiene puntos aislados, en el sentido de que la probabilidad de estar conectado es muy cercana a la probabilidad de no tener puntos aislados, que es aproximadamente $igual a$ $e$ $-e$ $-$ $c$ De hecho, tenemos el siguiente resultado: ${\ Displaystyle \ mathbb {P} \ left (X_ {n} = 0 \ right),}$

Puntos aislados (Erdős, Rényi, 1960). - Supongamos que

{\ Displaystyle {\ tilde {p}} (n) \ = \ {\ frac {\ ln n} {n}} + {\ frac {c} {n}} + {\ frac {\ varepsilon (n)} {no}}.}

Entonces, el número $X n$ de puntos aislados del gráfico converge en derecho hacia una distribución de Poisson del parámetro $e$ $-$ $c$ . ${\ Displaystyle G \ left ({\ tilde {p}} (n), n \ right)}$

Demostración

En lo que sigue, se abrevia en y nos planteamos ${\ Displaystyle G \ left ({\ tilde {p}} (n), n \ right)}$ ${\ Displaystyle {\ tilde {G}} _ {n},}$

{\ Displaystyle \ mu = \ mathrm {e} ^ {- c}.}

Sea $X n$ el número de puntos aislados de Sabemos que ${\ Displaystyle {\ tilde {G}} _ {n}.}$

{\ Displaystyle X_ {n} = Y_ {1} + Y_ {2} + \ dots + Y_ {n},}

{\ Displaystyle Y_ {i} = 1 _ {\ mathrm {el ~ vértice ~} i \ mathrm {~ es ~ isol {\ aguda {e}}}}.}

Usemos el método de los momentos factoriales. Sea $I n , A$ el conjunto de inyecciones de en Para todos $[\! [1, n] \!]$ $A.$ ${\ Displaystyle r \ geq 1,}$

{\ Displaystyle (X_ {n}) _ {r} = (Y_ {1} + Y_ {2} + \ dots + Y_ {n}) _ {r} = \ sum _ {\ varphi \ in I_ {r, [\! [1, n] \!]}} \ \ Prod _ {i = 1} ^ {r} Y _ {\ varphi (i)}.}

Los términos de la suma anterior aparecen de hecho en la expansión de pero, aparte de estos términos, esta expansión trae muchos otros términos que aparentemente chocan. De hecho, ya sea ${\ Displaystyle \ prod _ {i = 1} ^ {r} Y _ {\ varphi (i)}}$ ${\ Displaystyle (Y_ {1} + Y_ {2} + \ dots + Y_ {n}) _ {r},}$

{\ Displaystyle E = \ left \ {a \ in [\! [1, n] \!] \, | \, Y_ {a} = 1 \ right \}.}

Entonces

{\ Displaystyle \ forall \, \ varphi \ in I_ {r, [\! [1, n] \!]}, \ qquad \ prod _ {i = 1} ^ {r} Y _ {\ varphi (i) } = 1 _ {\ varphi \ en I_ {r, E}},}

Entonces

{\ Displaystyle \ sum _ {\ varphi \ in I_ {r, [\! [1, n] \!]}} \ \ prod _ {i = 1} ^ {r} Y _ {\ varphi (i)} \ = \ | I_ {r, E} | \ = \ (| E |) _ {r} \ = \ (X_ {n}) _ {r}.}

Además, por simetría,

{\ Displaystyle \ mathbb {E} \ left [\ prod _ {i = 1} ^ {r} Y _ {\ varphi (i)} \ right] \ = \ \ mathbb {E} \ left [\ prod _ { i = 1} ^ {r} Y_ {i} \ right] = (1 - {\ tilde {p}} (n)) ^ {r (n-1) -r (r-1) / 2},}

donde $r ( n -1)$ es el número de aristas que potencialmente resultan de un vértice de E , y donde $r ( r -1) / 2$ es el número de aristas entre dos vértices de E , es decir. los que se cuentan por duplicado en el total $r ( n -1)$ . Entonces

{\ Displaystyle {\ begin {alineado} \ mathbb {E} \ left [(X_ {n}) _ {r} \ right] & = (n) _ {r} (1 - {\ tilde {p}} ( n)) ^ {r (n-1) -r (r-1) / 2} \\ & \ simeq n ^ {r} (1 - {\ tilde {p}} (n)) ^ {r (n -1)} \\ & = \ left (n (1 - {\ tilde {p}} (n)) ^ {n-1} \ right) ^ {r} \\ & \ simeq \ mu ^ {r} . \ end {alineado}}}

Por lo tanto, por el método de momentos, $X n$ converge en ley a una distribución de Poisson con parámetro μ , y

{\ Displaystyle \ lim \ mathbb {P} \ left (X_ {n} = 0 \ right) \ = \ \ mathrm {e} ^ {- \ mu} \ = \ \ mathrm {e} ^ {- \ mathrm { e} ^ {- c}}.}

Este teorema es una ilustración sorprendente del paradigma de Fish , que, cuando presenta muchas oportunidades para observar un evento raro ( es decir, improbable), entonces el número total de eventos raros observados sigue una ley de Poisson .

El teorema de la doble exponencial

Erdős y Rényi deducen un resultado más preciso que la propiedad de umbral estrecho:

Teorema de doble exponencial (Erdős, Rényi, 1960) - Suponga que

{\ Displaystyle {\ tilde {p}} (n) \ = \ {\ frac {\ ln n} {n}} + {\ frac {c} {n}} + {\ frac {\ varepsilon (n)} {no}}.}

Entonces

{\ Displaystyle \ lim _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left ({\ tilde {p}} (n), n \ right) \ mathrm {~ está ~ relacionado} \ right ) = e ^ {- e ^ {- c}}.}

Demostración Si no tiene un punto aislado, entonces hay pocas posibilidades de que sea algo más que conectado (cf. Spencer, 10 conferencias sobre gráficos aleatorios ). De hecho, sea B parte y sea k su cardinal. Denotemos el evento " B es un componente conectado de ". El evento puede verse como la unión (no disjunta) de

k

k

-2

subconjuntos de probabilidades

{\ Displaystyle X_ {n} = 0,}

{\ Displaystyle {\ tilde {G}} _ {n}}

{\ Displaystyle {\ tilde {G}} _ {n}}

[\! [1, n] \!]

{\ Displaystyle {\ mathcal {C}} _ ​​{B}}

{\ Displaystyle {\ tilde {G}} _ {n}}

{\ Displaystyle {\ mathcal {C}} _ ​​{B}}

{\ Displaystyle {\ tilde {p}} (n) ^ {k-1} (1 - {\ tilde {p}} (n)) ^ {k (nk)},}

lo que conduce al siguiente aumento:

{\ Displaystyle \ mathbb {P} ({\ mathcal {C}} _ ​​{B}) \ \ leq \ k ^ {k-2} {\ tilde {p}} (n) ^ {k-1} (1 - {\ tilde {p}} (n)) ^ {k (nk)}.}

Aquí denota el número de árboles de expansión posibles para un gráfico conectado cuyos vértices serían los elementos de B , o incluso, de manera equivalente, el número de opciones posibles de una familia de k -1 aristas que hace que el conjunto B esté relacionado. Además, ¿ es la probabilidad de que las aristas k -1 del árbol de expansión considerado estén realmente presentes, y es la probabilidad de que no exista ninguna arista que conecte un vértice de B con un vértice de B c , de modo que B es decir, no solo esté conectado , pero también máxima entre las partes conectadas del gráfico. ${\ Displaystyle k ^ {k-2}}$ ${\ Displaystyle {\ tilde {p}} (n) ^ {k-1}}$ ${\ Displaystyle (1 - {\ tilde {p}} (n)) ^ {k (nk)}}$

El evento

{\ Displaystyle D_ {n} = \ {X_ {n} = 0 \ mathrm {~ mais ~} {\ tilde {G}} _ {n} \ mathrm {~ n} ^ {\ prime} \ mathrm {est ~ no ~ relacionado} \}}

comprobado

{\ Displaystyle D_ {n} \ subconjunto \ bigcup _ {2 \ leq | B | \ leq n / 2} {\ mathcal {C}} _ ​​{B}.}

De hecho, bajo la hipótesis D n , tiene varios componentes conectados, por lo tanto, el más pequeño de ellos (en el sentido del número de vértices) tiene como máximo n / 2 vértices, pero este componente conectado más pequeño tiene al menos dos vértices, ya que $X$ $n$ $= 0$ . Entonces ${\ Displaystyle {\ tilde {G}} _ {n}}$

{\ Displaystyle {\ begin {alineado} \ mathbb {P} (D_ {n}) & \ leq \ sum _ {2 \ leq | B | \ leq n / 2} \ mathbb {P} ({\ mathcal {C }} _ {B}) \\ & \ leq \ sum _ {2 \ leq k \ leq n / 2} {n \ elige k} k ^ {k-2} {\ tilde {p}} (n) ^ {k-1} (1 - {\ tilde {p}} (n)) ^ {k (nk)} \\ & \ leq \ sum _ {2 \ leq k \ leq n / 2} u_ {k}. \ end {alineado}}}

Sin embargo, para $α > 0$ ,

{\ Displaystyle {\ begin {alineado} u_ {2} & \ leq n ^ {- 1+ \ alpha} \, \ ln n \ end {alineado}}}

desde que

{\ Displaystyle \ ln n \ geq \ max \ left [c + \ varepsilon (n) \ ,, (- 2c-2 \ varepsilon (n) +4 {\ tilde {p}} (n)) / \ alpha \ derecha].}

Así como un componente conectado de tamaño superior a 2 es mucho menos probable que un componente conectado de tamaño 1, un componente conectado de tamaño superior a 3 es mucho menos probable que un componente conectado de tamaño 2, lo que da como resultado un

Propiedad : cuando n tiende a infinito

{\ Displaystyle u_ {2} (n) \ \ gg \ \ sum _ {3 \ leq k \ leq n / 2} u_ {k} (n).}

Algunos cálculos algo dolorosos, sin ser francamente difíciles, conducen a este resultado.

Demostración

El límite dado arriba para $u 2 ( n )$ no es solo un límite superior, sino que de hecho da el orden de magnitud de $u 2 ( n )$ . En cuanto al resto de la suma, tenemos que cortarlo en dos antes de aumentar cada una de las dos piezas:

{\ Displaystyle {\ begin {alineado} {\ frac {u_ {k + 1}} {u_ {k}}} & = (nk) \, (1 + {\ tfrac {1} {k}}) ^ { k-2} \, {\ tilde {p}} (n) \ times (1 - {\ tilde {p}} (n)) ^ {n-2k-1} \\ & = (nk) \, ( e + {\ hat {\ varepsilon}} (k)) \, {\ tilde {p}} (n) \ times (1 - {\ tilde {p}} (n)) ^ {n-2k-1} \ \ & \ leq {\ hat {c}} \, \ ln n \ (1 - {\ tilde {p}} (n)) ^ {n-2k-1} \ end {alineado}}}

{\ Displaystyle \ forall n, k, \ quad {\ hat {c}} \ geq (e + {\ hat {\ varepsilon}} (k)) \, {\ frac {n {\ tilde {p}} ( n)} {\ ln n}}.}

Por y ${\ displaystyle 0 <\ beta <(1- \ gamma) / 2 <0.5,}$ ${\ Displaystyle k \ leq \ beta n,}$

{\ Displaystyle {\ begin {alineado} {\ frac {u_ {k + 1}} {u_ {k}}} & \ leq {\ hat {c}} \, \ ln n \ \ exp \ left [- { \ tilde {p}} (n) (n-2k-1) \ right] \\ & \ leq {\ hat {c}} n ^ {- \ gamma} \ ln n, \ end {alineado}}}

desde que

{\ Displaystyle \ ln n \ geq {\ frac {{\ tilde {p}} (n) + (c + \ varepsilon (n)) (2 \ beta -1)} {1-2 \ beta - \ gamma} }.}

Por lo tanto, para n lo suficientemente grande, disminuye más rápido que una secuencia exponencial de razón cuando y ${\ Displaystyle u_ {k}}$ ${\ Displaystyle {\ hat {c}} n ^ {- \ gamma} \ ln n,}$ ${\ Displaystyle 2 \ leq k \ leq 1+ \ beta n,}$

{\ Displaystyle \ sum _ {k = 2} ^ {1+ \ beta n} u_ {k} \ \ leq \ {\ frac {u_ {2}} {1 - {\ hat {c}} n ^ {- \ gamma} \ ln n}} \ \ leq \ 2n ^ {- 1+ \ alpha} \, \ ln n.}

Además, porque podemos encontrar c y ρ positivos, de modo que, para todos ${\ Displaystyle 0 <\ alpha <1/4,}$ ${\ Displaystyle n \ geq 1,}$

{\ Displaystyle {\ begin {alineado} u_ {n / 2} & \ leq c \, \ rho ^ {n} \, n ^ {- \ alpha n}. \ end {alineado}}}

Por y ${\ displaystyle 0 <\ beta <(1- \ gamma) / 2 <0.5,}$ ${\ Displaystyle k \ geq \ beta n,}$

{\ Displaystyle {\ begin {alineado} {\ frac {u_ {k-1}} {u_ {k}}} & \ leq {\ frac {d} {\ ln n}} \ \ exp \ left [{\ tilde {p}} (n) (n-2k + 1) \ right] \\ & \ leq {\ frac {d \, n ^ {(1-2 \ beta) ^ {2} / \ gamma}} { \ ln n}} \\ & \ leq d \, n ^ {(1-2 \ beta) ^ {2} / \ gamma}, \ end {alineado}}}

tan pronto como n sea lo suficientemente grande. Por lo tanto, para y lo suficientemente cerca de 0.5, lo suficientemente cerca de 1, ${\ Displaystyle n / 2 \ geq k \ geq \ beta n,}$ $\beta$ ${\ displaystyle (1-2 \ beta) / \ gamma}$

{\ Displaystyle {\ begin {alineado} - \ alpha + ((1-2 \ beta) ^ {3} / 2 \ gamma) & <0, \\ {\ frac {u_ {k}} {u_ {n / 2}}} & \ leq d ^ {(1-2 \ beta) n / 2} n ^ {n (1-2 \ beta) ^ {3} / 2 \ gamma}, \\ u_ {k} & \ leq c \, {\ tilde {\ rho}} ^ {n} \, n ^ {(- \ alpha + ((1-2 \ beta) ^ {3} / 2 \ gamma)) n}, \ end { alineado}}}

{\ Displaystyle \ sum _ {k = \ beta n} ^ {n / 2} u_ {k} \ \ leq \ c \, {\ hat {\ rho}} ^ {n} \, n ^ {(- \ alpha + ((1-2 \ beta) ^ {3} / 2 \ gamma)) n} \ \ ll \ u_ {2}.}

En consecuencia

{\ Displaystyle \ lim _ {n} \ mathbb {P} \ left ({\ tilde {G}} _ {n} \ mathrm {~ está ~ relacionado} \ right) = \ lim _ {n} \ mathbb {P } \ left (X_ {n} = 0 \ right).}

Denotemos por $T n$ el primer instante t donde se conecta la gráfica : ${\ Displaystyle \ mathbb {G} \ left (t, n \ right)}$

{\ Displaystyle T_ {n} \ = \ \ inf \ left \ {t \ geq 0 \ | \ \ mathbb {G} (t, n) \ mathrm {~ está ~ relacionado} \ right \},}

de manera que

{\ Displaystyle \ left \ {\ mathbb {G} \ left (t, n \ right) \ mathrm {~ está ~ relacionado} \ right \} \ quad \ Rightarrow \ quad \ left \ {T_ {n} \ leq t \ right \} \ quad \ Rightarrow \ quad \ left \ {\ forall \ varepsilon> 0, \ quad \ mathbb {G} \ left (t + \ varepsilon, n \ right) \ mathrm {~ está ~ relacionado} \ right \}.}

Entonces podemos ver el teorema de la doble exponencial como resultado de la expansión asintótica de $T n$ : si $Z n$ está definido por la siguiente relación:

{\ Displaystyle T_ {n} \ = \ {\ frac {\ ln n} {n}} \ + \ {\ frac {Z_ {n}} {n}},}

entonces el teorema de la doble exponencial establece que $Z n$ converge en derecho hacia la distribución de Gumbel , lo que podría traducirse, en una versión probabilística de la notación de Landau , por:

{\ Displaystyle T_ {n} \ = \ {\ frac {\ ln n} {n}} \ + \ \ Theta \ left ({\ frac {1} {n}} \ right).}

El gráfico aleatorio infinito

Erdős y Rényi generalizaron el modelo binomial al caso de un gráfico infinito contable , mostrando que entonces obtuvimos ( casi seguramente ) un gráfico que tiene propiedades de universalidad (que contiene en particular cualquier gráfico finito o contable como un subgráfico ); este gráfico se ha redescubierto varias veces y se conoce con mayor frecuencia como el gráfico de Rado .

Ver también

Notas

El primer artículo, publicado en 1959 , es "On Random Graphs I", Publ. Matemáticas. Debrecen 6, 290.
(en) P. Erdős , " Algunas observaciones sobre la teoría de los gráficos " , Bull. Amargo. Matemáticas. Soc. , vol. 53, n o 4,1947, p. 292-294 ( leer en línea ). A menudo se considera que este artículo marca el nacimiento del "método probabilístico" para el estudio de gráficos no aleatorios, en particular para la teoría de Ramsey .
Para antecedentes, consulte (en) el Sr. Karoński Ruciński y A., "Los orígenes de la teoría de gráficos aleatorios" , en The Mathematics of Paul Erdős , Berlín, Springer al. “Algoritmos Combin. "( N o 13),1997, p. 311-336.
Para obtener más detalles, consulte Janson, Łuczak y Ruciński 2000 , cap. 2, "Probabilidades exponencialmente pequeñas".
Ver Janson, Łuczak y Ruciński 2000 , sección 1.4, “Equivalencia asintótica”, p. 14.
Ver (en) Galen R. Shorack y Jon A. Wellner , Procesos empíricos con aplicaciones a la estadística , SIAM ,septiembre de 2009, 998 p. ( ISBN 978-0-89871-684-9 , leer en línea ), sección 3.8, “Limitación de distribuciones bajo la hipótesis nula”, pág. 142 y cap. 18, “El proceso cuantílico estandarizado”, pág. 637.
Janson, Łuczak y Ruciński 2000 , Th. 6.7, p. 144.
Véase el artículo “ biyección de Joyal ”, o Martin Aigner y Günter M. Ziegler, divina razonamientos , 2 ª edición, 2006, p. 195-201, fórmula de Cayley para el número de árboles .

Bibliografía

(en) Béla Bollobás , Random Graphs , Cambridge University Press,Enero de 2001, 2 nd ed. ( 1 st ed. 1985), 516 p. ( ISBN 978-0-521-79722-1 , leer en línea ).
(en) Svante Janson (en) , Tomasz Łuczak y Andrzej Ruciński, Random Graphs , Wiley-Interscience,Mayo de 2000, 1 st ed. , 333 p. , tapa dura ( ISBN 978-0-471-17541-4 ).
(en) Joel Spencer (en) , “Nueve conferencias sobre gráficos aleatorios” , en Summer School of Probability of Saint-Flour XXI-1991, Part 3 , Springer, coll. "Notas de clase en matemáticas. "( N o 1541)1993, p. 293-347.

Artículo relacionado

Introducción de probabilidades en la teoría de grafos

Enlace externo

Laurent Massoulié, Redes: control distribuido y fenómenos emergentes , 2015