Método Probabilístico

Teoría

El Método Probabilístico es una técnica de demostración no constructiva que vas a usar principalmente en combinatoria, impulsada en gran parte por Paul Erdős. La filosofía central es poco intuitiva pero muy poderosa: para demostrar que existe un objeto matemático con una propiedad específica, defines un espacio de probabilidad sobre un conjunto de objetos candidatos y demuestras que la probabilidad de que un objeto tenga esa propiedad es estrictamente mayor a cero. O también, puedes mostrar que la probabilidad de que un objeto no tenga la propiedad es estrictamente menor a uno. Esto implica que el conjunto de objetos válidos no está vacío, lo que demuestra su existencia sin necesidad de dar un algoritmo para construir el objeto explícitamente.

Este método es súper importante en Teoría de Ramsey, teoría de gráficas y teoría combinatoria de números. Lo vas a usar seguido cuando las construcciones explícitas sean demasiado complejas o de plano no se conozcan. El método generalmente se divide en dos enfoques principales: el de la "Cota de la Unión" (mostrar que la suma de las probabilidades de eventos "malos" es menor a 1) y el de la "Linealidad de la Esperanza" (mostrar que si el valor esperado de una variable aleatoria es $E$, tiene que existir al menos un resultado donde la variable sea al menos $E$ y otro donde sea a lo más $E$).

La idea clave es que el azar simplifica el manejo de dependencias complejas. Por ejemplo, al usar la Linealidad de la Esperanza, puedes calcular