Método probabilístico en combinatoria

Primero se declara una familia de objetos y una distribución de elecciones. Si la propiedad deseada tiene probabilidad positiva, existe al menos un resultado que la cumple. Una probabilidad pequeña pero positiva basta para existencia; no garantiza que un intento cualquiera funcione.

El método no exige uniformidad sobre todos los objetos imaginables. Sí exige que la distribución usada y los cálculos correspondan. Si elegimos cada vértice de un grafo independientemente entre dos lados con probabilidad 1/2, queda definido un espacio de particiones concreto.

Un indicador vale uno si ocurre A y cero si no. Su esperanza es P(A).

Si X cuenta cuántas propiedades ocurren, X=Σ y E[X]=ΣP(A).

Esta linealidad no requiere independencia.

La independencia puede necesitarse antes para calcular P(A), por ejemplo al combinar elecciones de dos vértices. Eso es diferente de sumar esperanzas ya conocidas. La dependencia vuelve a importar al calcular varianza o probabilidades conjuntas.

Si todos los valores fueran estrictamente menores que la media, su promedio también lo sería: contradicción. Cuando X es entero, una media r garantiza un valor de al menos ⌈r⌉.

Una media grande no significa que casi todos los resultados sean grandes. Tampoco identifica el máximo exacto. Para demostrar un máximo se necesita además una cota superior para todos los objetos.

Trabajamos con grafos finitos simples no dirigidos. Cada vértice recibe lado cero o uno de forma independiente y equilibrada. Para una arista, las parejas de lados 00,01,10,11 son equiprobables y dos cruzan: P(cruce)=1/2.

Sumando indicadores, E[X]=m/2; por la media, existe un corte de al menos ⌈m/2⌉ aristas. El triángulo permite comprobar toda la prueba enumerando solo cuatro asignaciones si fijamos el primer vértice: cambiar todos los lados conserva el corte.

Si A₁,…, son eventos malos, . Si la suma es menor que uno, el complemento tiene probabilidad positiva y existe un objeto sin fallos. La cota de unión no requiere independencia.

También, para un número entero no negativo X de fallos, P(X≥1)≤E[X].

La condición estricta importa: esperanza igual a uno es compatible con tener exactamente un fallo siempre.

Para X≥0, E[X]>0 y E[X²]<∞, Cauchy–Schwarz aplicado a X·I_{X>0} da .

Una esperanza positiva ya implica positividad en algún resultado; esta cota proporciona además una probabilidad mínima.

En una suma de indicadores, E[X²] contiene términos . Aquí sí aparecen las dependencias. Var(X)=E[X²]−E[X]² incluye covarianzas; ignorarlas puede dar una cota falsa.

Una forma simétrica del lema local de Lovász dice: si cada evento malo tiene probabilidad como máximo p, un grafo de dependencias tiene grado máximo d y ep(d+1)≤1, entonces hay probabilidad positiva de evitar todos los fallos.

El grafo debe garantizar que cada evento es independiente de la colección conjunta de eventos no vecinos, incluidos sus complementos. La independencia solo por pares no basta. En modelos de variables independientes, conectar los eventos que comparten variables proporciona un grafo de dependencias válido.

Antes de decidir un color equilibrado, la esperanza actual es el promedio de las dos esperanzas tras fijarlo. Al menos una opción no la reduce. Si podemos calcularlas, elegimos esa y seguimos. Al final ya no queda azar y la esperanza coincide con el recuento real.

Para el corte, una arista con ambos extremos fijados aporta cero o uno; una con al menos un extremo pendiente sigue aportando 1/2. Eso permite actualizar la esperanza. El método garantiza al menos la media inicial, no necesariamente el corte máximo.

La demostración probabilística cubre la familia indicada mediante desigualdades. Un algoritmo necesita además representar los objetos y ejecutar sus decisiones. Una simulación ilustra resultados, pero unas cuantas muestras no prueban por sí solas una garantía para todo grafo.

Los ejemplos pequeños sirven para verificar fórmulas y detectar dependencias. Después se explica qué razonamiento se mantiene cuando crece el tamaño. Esa separación permite usar el azar con rigor y convertirlo en construcción cuando se dispone de las herramientas necesarias.