Linealidad de la esperanza y sus aplicaciones

La linealidad de la esperanza: trivial y profunda

La linealidad de la esperanza afirma que para cualesquiera variables aleatorias $X_1, X_2, \ldots, X_m$ (definidas sobre el mismo espacio, sin hipótesis de independencia ni distribución):

$\mathbb{E}\left[\sum_{i=1}^{m} X_i\right] = \sum_{i=1}^{m} \mathbb{E}[X_i]$.

Que esto valga sin independencia es el punto crucial y no intuitivo. Normalmente pensar en valores esperados requiere describir la distribución conjunta completa. La linealidad dice: no importa cómo estén correlacionadas las $X_i$ entre sí, la esperanza de la suma es la suma de las esperanzas.

Combinada con variables indicadoras — $X_i = \mathbf{1}_{\mathcal{A}_i}$ que vale 1 si ocurre el evento $\mathcal{A}_i$ y 0 si no — la linealidad convierte el cálculo de $\mathbb{E}[X]$ en una suma de probabilidades: $\mathbb{E}[X] = \sum_i \Pr[\mathcal{A}_i]$. El número de "instancias de la propiedad" en un objeto aleatorio es simplemente la suma de las probabilidades de cada posible instancia.

La cota de Turán para el número de independencia

El Teorema de Turán para conjuntos independientes (también llamado cota de Turán por el método probabilístico, o cota de Turán-Ramachandran) afirma: para todo grafo $G$ con $n$ vértices y $m$ aristas,

$\alpha(G) \ge \displaystyle\sum_{v \in V} \frac{1}{d(v)+1} \ge \frac{n}{\bar{d}+1}$

donde $\bar{d} = 2m/n$ es el grado medio. Esta cota es óptima asintóticamente para grafos aleatorios.

Prueba por método probabilístico. Tomamos una permutación uniformemente aleatoria $\sigma$ de los vértices $V$. Definimos $S = \{v \in V : v \text{ viene antes que todos sus vecinos en } \sigma\}$. Afirmamos que $S$ es siempre un conjunto independiente. En efecto, si $u, v \in S$ son adyacentes, entonces $u$ viene antes de todos sus vecinos (incluyendo $v$) y $v$ viene antes de todos sus vecinos (incluyendo $u$): pero entonces $u$ viene antes de $v$ y $v$ antes de $u$, contradicción.

Calculamos $\mathbb{E}[|S|]$ por linealidad: $\mathbb{E}[|S|] = \sum_v \Pr[v \in S]$. El vértice $v$ pertenece a $S$ si y solo si $v$ es el primero entre $v$ y sus $d(v)$ vecinos en $\sigma$. Como los $d(v)+1$ vértices en $\{v\} \cup N(v)$ son igualmente probables de ser el primero en $\sigma$, $\Pr[v \in S] = 1/(d(v)+1)$. Luego $\mathbb{E}[|S|] = \sum_v 1/(d(v)+1) \ge n/(\bar{d}+1)$. Como $|S| \le \alpha(G)$ siempre (S es independiente), concluimos $\alpha(G) \ge \mathbb{E}[|S|] \ge n/(\bar{d}+1)$.

Torneos y caminatas hamiltonianas

Un torneo es un grafo completo con cada arista orientada. Una caminata hamiltoniana es un ordenamiento $v_1, v_2, \ldots, v_n$ de todos los vértices tal que $v_i \to v_{i+1}$ para todo $i$.

Teorema. Todo torneo tiene al menos una caminata hamiltoniana.

Prueba por método probabilístico. Sea $T$ un torneo con $n$ vértices. Tomamos una permutación aleatoria $\sigma = (v_1, v_2, \ldots, v_n)$ uniformemente aleatoria. Definimos $X$ = número de índices $i$ donde $v_i \to v_{i+1}$ (arcos "correctos"). Tenemos $X = \sum_{i=1}^{n-1} \mathbf{1}_{v_i \to v_{i+1}}$, y por linealidad $\mathbb{E}[X] = \sum_{i=1}^{n-1} \Pr[v_i \to v_{i+1}] = (n-1)/2$ (pues por simetría cada arco en $\sigma$ es correcto con probabilidad $1/2$).

Esto solo dice que la permutación aleatoria tiene en promedio $(n-1)/2$ arcos correctos, lo que no es suficiente para construir una caminata hamiltoniana. La prueba completa por inducción es más limpia: ordena los vértices como $v_1, v_2, \ldots, v_n$; si $v_i \to v_{i+1}$ para todo $i$, terminamos. Si no, hay un $j$ con $v_{j+1} \to v_j$; entonces podemos intercambiar e iterar. Esta prueba constructiva es mejor aquí, pero el cálculo de esperanza sirve para determinar cuántas caminatas hamiltonianas existen en promedio en un torneo aleatorio.

La prueba correcta por el método probabilístico del teorema de torneos es vía la perspectiva del máximo: en cualquier permutación, se puede ver que el número de inversiones se puede reducir, pero aquí el método probabilístico se usa en la dirección contraria: para probar que el torneo aleatorio tiene un número de caminatas hamiltonianas que crece como $n!/2^{n-1}$, se usa que la permutación es hamiltoniana con probabilidad $1/2^{n-1}$, y el torneo aleatorio tiene $\mathbb{E}[$caminatas$] = n!/2^{n-1}$.

El número de bisección y sparsificación

El número de bisección $b(G)$ de un grafo $G$ con $n$ vértices es el mínimo número de aristas que hay que eliminar para partir $V$ en dos conjuntos de tamaño $n/2$ (o $\lfloor n/2 \rfloor$ y $\lceil n/2 \rceil$). La siguiente cota de Edwards-Erdős:

$b(G) \le \frac{m}{2} + \frac{n-1}{4}$

se demuestra por el método probabilístico. Elegimos la bipartición aleatoriamente: cada vértice va a la parte $A$ o $B$ independientemente con probabilidad $1/2$. El número esperado de aristas cruzadas es $m/2$ (cada arista cruza con probabilidad $1/2$), lo que da la primera parte. El ajuste $+\frac{n-1}{4}$ viene del método de la alteración para balancear las partes.

La cota de max-cut de Edwards. Sea $G$ un grafo con $n$ vértices y $m$ aristas. Existe un corte (bipartición de $V$) con al menos $m/2 + (n-1)/4$ aristas cruzadas. La prueba elegante es por linealidad: el corte aleatorio tiene en promedio $m/2$ aristas cruzadas; para optimizar hacia $(n-1)/4$ extra se usa el método de reordenamiento greedy sobre permutaciones. Esta cota es relevante porque la versión de maximización (encontrar el corte máximo) es un problema $\mathsf{NP}$-difícil en general, pero el método probabilístico da la cota no constructiva de forma inmediata.

El segundo momento: la desigualdad de Chebyshev y el método

Cuando el método del primer momento da $\mathbb{E}[X] \to \infty$ pero queremos demostrar que $X > 0$ con alta probabilidad (no solo con probabilidad positiva), usamos el método del segundo momento: la desigualdad de Paley-Zygmund.

Desigualdad de Paley-Zygmund. Para $X \ge 0$: $\Pr\left[X > 0\right] \ge \dfrac{(\mathbb{E}[X])^2}{\mathbb{E}[X^2]}$.

Si $\mathbb{E}[X^2] = O((\mathbb{E}[X])^2)$, entonces $\Pr[X > 0] = \Omega(1)$, lo que demuestra que $X > 0$ con probabilidad acotada por abajo. Este método es la herramienta para demostrar umbrales en grafos aleatorios: $R(k,k)$ tiene cota inferior $2^{k/2}$ por primer momento, pero la cota superior $4^k$ (que sigue de $R(k,k) \le \binom{2k-2}{k-1} \le 4^k$) requiere argumentos de segundo momento o la recurrencia de Ramsey.

La dicotomía primer/segundo momento es omnipresente: el primer momento demuestra existencia, el segundo momento demuestra alta probabilidad. Para problemas olímpicos, el primer momento es casi siempre suficiente; el segundo momento aparece en problemas donde se pide probar que el número de configuraciones es grande, o estimar con precisión.

Aplicación olímpica: problemas de coloración por esperanza

Problema modelo (IMO Shortlist 2014 C2). Sea $n \ge 2$ y sea $k$ el número mínimo de colores necesarios para colorear los enteros $1, 2, \ldots, n$ de modo que no existan $a, b$ del mismo color con $a + b = 2^t$ para ningún $t$. Prueba que $k \le 1 + \lfloor \log_2 n \rfloor$.

La prueba usando el método probabilístico: consideramos la coloración aleatoria con $c$ colores. El número esperado de pares monocromáticos prohibidos se calcula por linealidad como la suma sobre todos los pares $(a,b)$ con $a + b$ potencia de 2, de $\Pr[\text{mismo color}] = 1/c$. Si $c$ es suficientemente grande para que esta esperanza sea menor que la mitad de la cantidad de colores disponibles, existe una coloración válida. La estimación cuidadosa de cuántos pares prohibidos hay (a lo sumo $n \log_2 n / 2$ pares) y la condición de esperanza $< 1$ dan la cota buscada.

El patrón: (1) colorear aleatoriamente, (2) definir $X$ = número de violaciones, (3) calcular $\mathbb{E}[X]$ por linealidad, (4) pedir $\mathbb{E}[X] < 1$ para obtener existencia. Los detalles combinatorios de cada problema viven en el paso (3), pero la estructura del argumento es siempre la misma.