método del segundo momento

El subgrafo de percolación de enlaces de Bernoulli de un grafo G con parámetro p es un subgrafo aleatorio obtenido de G eliminando cada arista de G con probabilidad 1− p , independientemente. El árbol binario completo infinito T es un árbol infinito donde un vértice (llamado raíz) tiene dos vecinos y cada uno de los demás vértices tiene tres vecinos. El método del segundo momento puede usarse para demostrar que, para cada parámetro p ∈ (1/2, 1 ] con probabilidad positiva, la componente conexa de la raíz en el subgrafo de percolación de T es infinita.

Sea K el componente de percolación de la raíz, y sea T _n el conjunto de vértices de T que están a una distancia n de la raíz. Sea X _n el número de vértices en T _n ∩ K .

Para demostrar que K es infinito con probabilidad positiva, basta con demostrar que${\displaystyle \Pr(X_{n}>0\ \ \forall n)>0}$Desde los acontecimientos${\displaystyle \{X_{n}>0\}}$forman una secuencia decreciente, por continuidad de las medidas de probabilidad esto es equivalente a demostrar que${\displaystyle \inf _{n}\Pr(X_{n}>0)>0}$.

La desigualdad de Cauchy-Schwarz da como resultado $${\displaystyle \operatorname {E} [X_{n}]^{2}\leq \operatorname {E} [X_{n}^{2}]\,\operatorname {E} \left[(1_{X_{n}>0})^{2}\right]=\operatorname {E} [X_{n}^{2}]\,\Pr(X_{n}>0).}$$ Por lo tanto, basta con demostrar que $${\displaystyle \inf _{n}{\frac {\operatorname {E} \left[X_{n}\right]^{2}}{\operatorname {E} \left[X_{n}^{2}\right]}}>0\,,}$$ Es decir, que el segundo momento está acotado superiormente por una constante multiplicada por el cuadrado del primer momento (y ambos son distintos de cero). En muchas aplicaciones del método del segundo momento, no es posible calcular los momentos con precisión, pero aun así se puede establecer esta desigualdad.

En esta aplicación particular, estos momentos se pueden calcular. Para cada v específico en T _n , $${\displaystyle \Pr(v\in K)=p^{n}.}$$ Desde${\displaystyle |T_{n}|=2^{n}}$De ello se deduce que $${\displaystyle \operatorname {E} [X_{n}]=2^{n}\,p^{n}}$$ que es el primer momento. Ahora viene el cálculo del segundo momento. $${\displaystyle \operatorname {E} \!\left[X_{n}^{2}\right]=\operatorname {E} \!\left[\sum _{v\in T_{n}}\sum _{u\in T_{n}}1_{v\in K}\,1_{u\in K}\right]=\sum _{v\in T_{n}}\sum _{u\in T_{n}}\Pr(v,u\in K).}$$ Para cada par v , u en T _n, sea w ( v , u ) el vértice en T que está más alejado de la raíz y se encuentra en el camino simple en T a cada uno de los dos vértices v y u , y sea k ( v , u ) la distancia de w a la raíz. Para que v y u estén ambos en K , es necesario y suficiente que los tres caminos simples de w ( v , u ) a v , u y la raíz estén en K . Dado que el número de aristas contenidas en la unión de estos tres caminos es 2 n − k ( v , u ) , obtenemos $${\displaystyle \Pr(v,u\in K)=p^{2n-k(v,u)}.}$$ El número de pares ( v , u ) tales que k ( v , u ) = s es igual a${\displaystyle 2^{s}\,2^{ns}\,2^{ns-1}=2^{2n-s-1}}$, para${\displaystyle s=0,1,\dots ,n-1}$y igual a${\displaystyle 2^{n}}$para${\displaystyle s=n}$Por lo tanto, para${\displaystyle p>{\frac {1}{2}}}$, $${\displaystyle \operatorname {E} [X_{n}^{2}]=(2p)^{n}+\sum _{s=0}^{n-1}2^{2n-s-1}p^{2n-s}={\frac {(2p)^{n+1}-2(2p)^{n}+(2p)^{2n+1}}{4p-2}},}$$ de modo que $${\displaystyle {\frac {(\operatorname {E} [X_{n}])^{2}}{\operatorname {E} [X_{n}^{2}]}}={\frac {4p-2}{(2p)^{1-n}-2(2p)^{-n}+2p}}\to 2-{\frac {1}{p}}>0,}$$ con lo cual se completa la demostración.

La elección de la variable aleatoria a la que se aplica el método de los momentos suele marcar la diferencia. Un ejemplo se da en el contexto de la coloración de grafos . En este caso, si denotamos por Z el número de todas las q- coloraciones, se obtiene una cota superior para el umbral de q- colorabilidad, que no es ajustada. Si en cambio consideramos el número _Zbal , es decir, el número de coloraciones casi equilibradas —aquellas en las que cada clase de color contiene alrededor de n/q vértices—, se obtiene un umbral mejorado, que sí es ajustado.

• La elección de las variables aleatorias X _n fue bastante natural en este caso. En algunas aplicaciones más complejas del método, podría ser necesario cierto ingenio para elegir las variables aleatorias X _n para las cuales el argumento pueda llevarse a cabo.
• En ocasiones, se utiliza la desigualdad de Paley-Zygmund en lugar de la desigualdad de Cauchy-Schwarz , y a veces puede proporcionar resultados más precisos.
• Bajo la suposición (incorrecta) de que los eventos v y u en K son siempre independientes, se tiene${\displaystyle \Pr(v,u\in K)=\Pr(v\in K)\,\Pr(u\in K)}$y el segundo momento es igual al cuadrado del primer momento. El método del segundo momento suele funcionar en situaciones en las que los eventos o variables aleatorias correspondientes son "casi independientes".
• En esta aplicación, las variables aleatorias X _n se dan como sumas$${\displaystyle X_{n}=\sum _{v\in T_{n}}1_{v\in K}.}$$En otras aplicaciones, las variables aleatorias útiles correspondientes son integrales.$${\displaystyle X_{n}=\int f_{n}(t)\,d\mu (t),}$$donde las funciones f _n son aleatorias. En tal situación, se considera la medida del producto μ × μ y se calcula$${\displaystyle {\begin{aligned}\operatorname {E} \left[X_{n}^{2}\right]&=\operatorname {E} \left[\iint f_{n}(x)\,f_{n}(y)\,d\mu (x)\,d\mu (y)\right]\\&=\operatorname {E} \left[\iint \operatorname {E} \left[f_{n}(x)\,f_{n}(y)\right]\,d\mu (x)\,d\mu (y)\right],\end{aligned}}}$$donde el último paso se justifica típicamente utilizando el teorema de Fubini .