Capítulo 5

Ferramentas probabilísticas

A desigualdade de van den Berg–Kesten e a fórmula de Russo permitem estudar dois aspectos das conexões abertas. A primeira controla ocorrências disjuntas de eventos crescentes; a segunda relaciona a variação de uma esperança com as influências das arestas.

5.1 Desigualdade BK

Fixe um conjunto finito de arestas \(F\subset E(G)\) e escreva \(\Omega _F=\{ 0,1\} ^F\). Para \(K\subset F\) e \(\omega \in \Omega _F\), denotamos por

\[ C_{\omega ,K}=\{ \eta \in \Omega _F:\eta |_K=\omega |_K\} \]

o cilindro determinado por \(\omega \) em \(K\).

Dizemos que \(K\) certifica um evento \(A\subset \Omega _F\) na configuração \(\omega \) quando \(C_{\omega ,K}\subset A\).

Definição 5.1
Dados eventos \(A,B\subset \Omega _F\), sua ocorrência disjunta é
\[ A\circ B = \{ \omega :\exists K,L\subset F,\ K\cap L=\varnothing , \ C_{\omega ,K}\subset A,\ C_{\omega ,L}\subset B\} . \]

Para eventos de conexão, \(A\circ B\) significa que as duas ocorrências podem ser realizadas por conjuntos disjuntos de arestas. Por exemplo, se \(A\) e \(B\) especificam duas conexões em um subgrafo finito, então \(A\circ B\) exige caminhos abertos disjuntos em arestas que certifiquem essas conexões.

Teorema 5.1 (Desigualdade BK)
Se \(A\) e \(B\) são eventos crescentes que dependem apenas das arestas de um conjunto finito \(F\), então
\[ \P _p(A\circ B)\le \P _p(A)\P _p(B). \]

A prova por indução em \(|F|\) usa a seguinte descrição de \(A\circ B\) em termos de configurações com suportes disjuntos.

Para configurações \(\omega ,\eta \in \Omega _F\) com suportes disjuntos, escrevemos \(\omega +\eta \) para a configuração cuja coordenada em \(e\) é \(\omega (e)+\eta (e)\).

Lema 5.2
Se \(A\) e \(B\) são crescentes, então
\[ A\circ B = \{ \omega +\eta :\operatorname {supp}(\omega )\cap \operatorname {supp}(\eta )=\varnothing , \ \omega \in A,\ \eta \in B\} . \]

Demonstração ▼

Suponha primeiro que \(\xi \in A\circ B\) e escolha certificados disjuntos \(K,L\subset F\). Defina

\[ \omega (e)=\begin{cases} 0,& e\in L,\\ \xi (e),& e\notin L, \end{cases} \qquad \eta (e)=\begin{cases} \xi (e),& e\in L,\\ 0,& e\notin L. \end{cases} \]

Então \(\xi =\omega +\eta \) e os suportes são disjuntos. Como \(K\cap L=\varnothing \), a configuração \(\omega \) coincide com \(\xi \) em \(K\), logo \(\omega \in C_{\xi ,K}\subset A\); do mesmo modo, \(\eta \in C_{\xi ,L}\subset B\).

Reciprocamente, suponha \(\xi =\omega +\eta \) com suportes disjuntos, \(\omega \in A\) e \(\eta \in B\). Tome \(K=\operatorname {supp}(\omega )\) e \(L=\operatorname {supp}(\eta )\). Se uma configuração coincide com \(\omega \) em \(K\), ela é maior ou igual a \(\omega \); como \(A\) é crescente, \(K\) certifica \(A\). Analogamente, \(L\) certifica \(B\). Logo \(\xi \in A\circ B\).

Prova da desigualdade BK ▼

O caso \(|F|\le 1\) é imediato. Suponha o resultado conhecido para \(|F|-1\) arestas e escolha \(e\in F\). Ponha \(F'=F\setminus \{ e\} \). Para um evento \(C\subset \Omega _F\) e \(j\in \{ 0,1\} \), defina sua seção

\[ C_j=\{ \omega \in \Omega _{F'}:\omega _{j,e}\in C\} , \]

onde \(\omega _{j,e}\) é obtida acrescentando a coordenada \(e\) com valor \(j\).

Se \(C\) é crescente, então \(C_0\subset C_1\) e ambas as seções são crescentes. Escreva \(D=A\circ B\). Do Lema 5.2 obtemos

\[ D_0\subset A_0\circ B_0 \]

e

\[ D_1\subset (A_0\circ B_1)\cup (A_1\circ B_0). \]

Além disso, como \(A_0\subset A_1\) e \(B_0\subset B_1\),

\[ D_0\subset (A_0\circ B_1)\cap (A_1\circ B_0), \qquad D_1\subset A_1\circ B_1. \]

Pela hipótese de indução,

\[ \P _p(D_0)\le \P _p(A_0)\P _p(B_0), \qquad \P _p(D_1)\le \P _p(A_1)\P _p(B_1). \]

Para a estimativa cruzada, ponha

\[ E=A_0\circ B_1, \qquad H=A_1\circ B_0. \]

As inclusões acima dão \(D_0\subset E\cap H\) e \(D_1\subset E\cup H\). Portanto,

\begin{align*} \P _p(D_0)+\P _p(D_1) & \le \P _p(E\cap H)+\P _p(E\cup H)\\ & =\P _p(E)+\P _p(H)\\ & \le \P _p(A_0)\P _p(B_1)+\P _p(A_1)\P _p(B_0), \end{align*}

onde a última desigualdade usa novamente a hipótese de indução.

Usando

\[ \P _p(A)=(1-p)\P _p(A_0)+p\P _p(A_1) \]

e a fórmula análoga para \(B\), expandimos o produto e aplicamos as três estimativas anteriores:

\begin{align*} \P _p(A)\P _p(B) & =(1-p)^2\P _p(A_0)\P _p(B_0)\\ & \quad +p(1-p)\bigl[\P _p(A_0)\P _p(B_1)+\P _p(A_1)\P _p(B_0)\bigr]\\ & \quad +p^2\P _p(A_1)\P _p(B_1)\\ & \ge (1-p)^2\P _p(D_0)+p(1-p)\bigl[\P _p(D_0)+\P _p(D_1)\bigr]+p^2\P _p(D_1)\\ & =\bigl[(1-p)^2+p(1-p)\bigr]\P _p(D_0) +\bigl[p(1-p)+p^2\bigr]\P _p(D_1)\\ & =(1-p)\P _p(D_0)+p\P _p(D_1)\\ & =\P _p(D). \end{align*}

Passagem para grafos infinitos.

A desigualdade se estende a eventos de conexão que possuem testemunhos finitos — por exemplo, \(\{ x\leftrightarrow y\} \) ou \(\{ A\leftrightarrow B\} \) com \(A\) e \(B\) finitos. Para isso, escolhe-se uma exaustão por subgrafos finitos \(G_1\subset G_2\subset \cdots \) e restringem-se os caminhos a \(G_n\). Os eventos assim obtidos crescem para o evento de conexão original, e o mesmo vale para a ocorrência disjunta. Aplicando BK em cada \(G_n\) e passando ao limite por continuidade crescente da probabilidade, obtemos a desigualdade correspondente no grafo infinito. Eventos sem testemunho finito, como \(\{ x\leftrightarrow \infty \} \), exigem uma aproximação específica antes de aplicar esse argumento.

5.2 Fórmula de Russo

Seja \(X:\Omega _F\to \mathbb R\) uma variável aleatória. Para \(e\in F\), defina

\[ \partial _eX(\omega )=X(\omega _{1,e})-X(\omega _{0,e}). \]

A quantidade \(\mathbf{E}_p[\partial _eX]\) é a influência da aresta \(e\) sobre \(X\).

Teorema 5.3 (Fórmula de Russo–Margulis)
Se \(X\) depende apenas de um conjunto finito \(F\) de arestas, então
\[ \frac{d}{dp}\mathbf{E}_p[X] = \sum _{e\in F}\mathbf{E}_p[\partial _eX]. \]

Demonstração ▼

É útil permitir parâmetros distintos em cada aresta. Escreva \(F=\{ e_1,\dots ,e_n\} \) e, para \(\mathbf p=(p_1,\dots ,p_n)\), seja \(\P _{\mathbf p}\) a medida produto com

\[ \P _{\mathbf p}(\omega (e_j)=1)=p_j. \]

Defina \(f(\mathbf p)=\mathbf{E}_{\mathbf p}[X]\).

Fixe \(j\) e condicione nos estados de todas as arestas exceto \(e_j\). Para cada configuração das demais coordenadas, a esperança condicional de \(X\) é uma função afim de \(p_j\):

\[ p_jX(\omega _{1,e_j})+(1-p_j)X(\omega _{0,e_j}). \]

Logo

\[ \frac{\partial f}{\partial p_j}(\mathbf p) = \mathbf{E}_{\mathbf p}[\partial _{e_j}X]. \]

Aplicando a regra da cadeia à diagonal \(p_1=\cdots =p_n=p\),

\[ \frac d{dp}\mathbf{E}_p[X] = \frac d{dp}f(p,\ldots ,p) = \sum _{j=1}^n\frac{\partial f}{\partial p_j}(p,\ldots ,p) = \sum _{j=1}^n\mathbf{E}_p[\partial _{e_j}X], \]

que é a fórmula desejada.

Para um evento \(A\), dizemos que \(e\) é pivotal na configuração \(\omega \) quando mudar apenas o estado de \(e\) altera a ocorrência de \(A\). Equivalentemente,

\[ e\text{ é pivotal para }A \quad \Longleftrightarrow \quad \mathbf1_A(\omega _{1,e})\ne \mathbf1_A(\omega _{0,e}). \]

Lema 5.4
Se \(A\) é crescente, então
\[ \partial _e\mathbf1_A(\omega ) = \mathbf1_{\{ e\text{ é pivotal para }A\} }(\omega ). \]
Consequentemente,
\[ \mathbf{E}_p[\partial _e\mathbf1_A] = \P _p(e\text{ é pivotal para }A). \]

Demonstração ▼

Como \(A\) é crescente,

\[ \mathbf1_A(\omega _{1,e})\ge \mathbf1_A(\omega _{0,e}). \]

A diferença entre os dois indicadores é, portanto, \(1\) exatamente quando forçar \(e\) a aberta faz \(A\) ocorrer e forçar \(e\) a fechada faz \(A\) falhar, isto é, exatamente quando \(e\) é pivotal.

Teorema 5.5 (Fórmula de Russo para eventos crescentes)
Se \(A\) é crescente e depende apenas de um conjunto finito \(F\) de arestas, então
\[ \frac{d}{dp}\P _p(A) = \sum _{e\in F}\P _p(e\text{ é pivotal para }A). \]

Demonstração ▼

Aplique a fórmula de Russo–Margulis a \(X=\mathbf1_A\) e use o Lema 5.4.