Método probabilístico

En matemáticas, el método probabilístico es un procedimiento no constructivo, utilizado principalmente en combinatoria y desarrollado por Paul Erdős, para demostrar la existencia de un tipo prescrito de objeto matemático.^[1]​ Funciona probando que, si se eligen aleatoriamente objetos de una clase específica, la probabilidad de que el resultado sea del tipo prescrito es estrictamente mayor que cero. Aunque la demostración utiliza probabilidad, la conclusión final se determina con certeza, sin posibilidad de error.

Este método se ha aplicado a otras áreas de las matemáticas, como la teoría de números, el álgebra lineal y el análisis real, así como en ciencias de la computación (como por ejemplo, en el redondeo aleatorio) y en la teoría de la información.

Si ningún objeto de una colección posee una propiedad determinada, la probabilidad de que un objeto elegido aleatoriamente posea dicha propiedad es cero. Por lo tanto, mediante contraposición lógica, si la probabilidad de que un objeto aleatorio elegido del conjunto posea esa propiedad es distinta de cero, entonces algún objeto del conjunto debe poseerla.

De igual manera, demostrar que la probabilidad es (estrictamente) menor que 1 puede utilizarse para demostrar la existencia de un objeto que no satisface las propiedades prescritas.

Otra forma de utilizar el método probabilístico es calculando el valor esperado de alguna variable aleatoria. Si se puede demostrar que la variable aleatoria puede tomar un valor menor que el valor esperado, esto demuestra que la variable aleatoria también puede tomar un valor mayor que el valor esperado.

Alternativamente, el método probabilístico también puede utilizarse para garantizar la existencia de un elemento deseado en un espacio muestral con un valor mayor o igual que el valor esperado calculado, ya que la inexistencia de dicho elemento implicaría que todos los elementos del espacio muestral son menores que el valor esperado, lo cual constituye una contradicción.

Las herramientas comunes utilizadas en el método probabilístico incluyen la desigualdad de Márkov, las cotas de Chernoff^[2]​ y el lema local de Lovász.

Aunque otros matemáticos demostraron antes que Erdős teoremas mediante el método probabilístico (como por ejemplo, el resultado de Szele de 1943 de que en teoría de grafos existen torneos que contienen un gran número de ciclos hamiltonianos), muchas de las demostraciones más conocidas que utilizan este método se deben a Erdös. El primer ejemplo a continuación describe un resultado de 1947 que proporciona una demostración de una cota inferior para el número de Ramsey R(r, r).

Supóngase que se tiene un grafo completo sobre n vértices. Se quiere demostrar (para valores suficientemente pequeños de n) que es posible colorear las aristas del grafo con dos colores (por ejemplo, rojo y azul) de modo que no exista un subgrafo completo sobre r vértices que sea monocromático (cada arista coloreada del mismo color).

Para ello, se colorea el grafo aleatoriamente, cada arista independientemente con la probabilidad 1/2 de ser rojo y de 1/2 de ser azul. Ahora, se calcula el número esperado de subgrafos monocromáticos sobre r vértices de la siguiente manera:

Para cualquier conjunto ${\displaystyle S_{r}}$ de ${\displaystyle r}$ vértices del grafo analizado, defínase la variable ${\displaystyle X(S_{r})}$ como 1 si todas las aristas entre los ${\displaystyle r}$ vértices son del mismo color, y como 0 en caso contrario. Nótese que el número de subgrafos ${\displaystyle r}$ monocromáticos es la suma de ${\displaystyle X(S_{r})}$ sobre todos los ${\displaystyle S_{r}}$ subconjuntos posibles. Para cualquier conjunto ${\displaystyle S_{r}^{i}}$, el valor esperado de ${\displaystyle X(S_{r}^{i})}$ es simplemente la probabilidad de que todas las aristas ${\displaystyle C(r,2)}$ en ${\displaystyle S_{r}^{i}}$ sean del mismo color:

${\displaystyle E[X(S_{r}^{i})]=2\cdot 2^{-{r \choose 2}}}$

(el factor 2 se obtiene porque hay dos colores posibles).

Esto es válido para cualquiera de los subconjuntos ${\displaystyle C(n,r)}$ posibles que se pudieran haber elegido, es decir, ${\displaystyle i}$ va de 1 a ${\displaystyle C(n,r)}$. Así, la suma de ${\displaystyle E[X(S_{r}^{i})]}$ sobre todos los ${\displaystyle S_{r}^{i}}$ es:

${\displaystyle \sum _{i=1}^{C(n,r)}E[X(S_{r}^{i})]={n \choose r}2^{1-{r \choose 2}}.}$

La suma de las expectativas es la esperanza de la suma (independientemente de si las variables son independientes), por lo que la esperanza de la suma (el número esperado de todos los subgrafos ${\displaystyle r}$ monocromáticos) es:

${\displaystyle E[X(S_{r})]={n \choose r}2^{1-{r \choose 2}}.}$

Considérese qué sucede si este valor es menor que 1. Dado que el número esperado de r subgrafos monocromáticos es estrictamente menor que 1, existe una coloración que cumple la condición de que el número de r subgrafos monocromáticos sea estrictamente menor que 1. El número de subgrafos r monocromáticos en esta coloración aleatoria es un número entero no negativo. Por lo tanto, debe ser 0 (0 es el único entero no negativo menor que 1). De ello se deduce que si

${\displaystyle E[X(S_{r})]={n \choose r}2^{1-{r \choose 2}}<1}$

(lo cual se cumple, por ejemplo, para n = 5 y r = 4), debe existir una coloración en la que no haya r subgrafos monocromáticos.^[3]​

Según el teorema de Ramsey, esto implica que R(r, r) debe ser mayor que n. En particular, R(r, r) debe crecer al menos exponencialmente con r.

Una debilidad de este argumento es que es completamente no constructivo. Si bien prueba (por ejemplo) que casi ninguna coloración del grafo completo en los vértices de (1.1)^r contiene ningún r subgrafo monocromático, no ofrece un ejemplo explícito de dicha coloración. El problema de encontrar dicha coloración ha estado abierto durante más de 50 años.

Un artículo de Erdős de 1959 (véase la referencia citada más abajo) abordó el siguiente problema en teoría de grafos: dados los enteros positivos g y k, ¿existe un grafo G que contenga solo ciclos con una longitud de al menos g, tal que el número cromático de G sea al menos k?

Se puede demostrar que dicho grafo existe para cualquier g y k, y la demostración es bastante sencilla. Sea n muy grande y considérese un grafo aleatorio G con n vértices, donde cada arista en G existe con probabilidad p = n^1/g−1. Se demuestra que, con probabilidad positiva, G satisface las dos propiedades siguientes:

Propiedad 1: G contiene como máximo n/2 ciclos de longitud menor que g.

Demostración: sea X el número de ciclos de longitud menor que g. El número de ciclos de longitud i en el grafo completo con vértices n es

${\displaystyle {\frac {n!}{2\cdot i\cdot (n-i)!}}\leq {\frac {n^{i}}{2}}}$

y cada uno de ellos está presente en G con probabilidad pⁱ. Por lo tanto, por la desigualdad de Márkov, se tiene que

${\displaystyle \Pr \left(X>{\tfrac {n}{2}}\right)\leq {\frac {2}{n}}E[X]\leq {\frac {1}{n}}\sum _{i=3}^{g-1}p^{i}n^{i}={\frac {1}{n}}\sum _{i=3}^{g-1}n^{\frac {i}{g}}\leq {\frac {g}{n}}n^{\frac {g-1}{g}}=gn^{-{\frac {1}{g}}}=o(1).}$

Por lo tanto, para un n suficientemente grande, la propiedad 1 se cumple con una probabilidad mayor que 1/2.

Propiedad 2: G no contiene ningún conjunto independiente de tamaño ${\displaystyle \lceil {\tfrac {n}{2k}}\rceil }$.

Demostración: sea Y el tamaño del mayor conjunto independiente en G. Claramente, se tiene que

${\displaystyle \Pr(Y\geq y)\leq {n \choose y}(1-p)^{\frac {y(y-1)}{2}}\leq n^{y}e^{-{\frac {py(y-1)}{2}}}=e^{-{\frac {y}{2}}\cdot (py-2\ln n-p)}=o(1),}$

cuando

${\displaystyle y=\left\lceil {\frac {n}{2k}}\right\rceil \!.}$

Por lo tanto, para un n suficientemente grande, la propiedad 2 se cumple con una probabilidad mayor que 1/2.

Para un n suficientemente grande, la probabilidad de que un grafo de la distribución tenga ambas propiedades es positiva, ya que los eventos para estas propiedades no pueden ser disjuntos (si lo fueran, sus probabilidades sumarían más de 1).

Aquí viene el truco: como G tiene estas dos propiedades, se puede eliminar como máximo n/2 vértices de G para obtener un nuevo grafo G′ sobre ${\displaystyle n'\geq n/2}$ vértices que contenga solo ciclos de longitud al menos g. Se puede ver que este nuevo grafo no tiene un conjunto independiente de tamaño ${\displaystyle \left\lceil {\frac {n'}{k}}\right\rceil }$. G′ solo se puede dividir en al menos k conjuntos independientes y, por lo tanto, tiene un número cromático al menos k.

Este resultado da una pista de por qué el cálculo del número cromático de un grafo es tan difícil: incluso cuando no existen razones locales (como ciclos pequeños) para que un grafo requiera muchos colores, el número cromático puede ser arbitrariamente grande.

• IP (clase de complejidad)
• Algoritmo de Las Vegas
• Grafo aleatorio

• Alon, Noga; Spencer, Joel H. (2000). The probabilistic method (2ed). New York: Wiley-Interscience. ISBN 0-471-37046-0.
• Erdős, P. (1959). «Graph theory and probability». Can. J. Math. 11: 34-38. MR 0102081. S2CID 122784453. doi:10.4153/CJM-1959-003-9. 
• Erdős, P. (1961). «Graph theory and probability, II». Can. J. Math. 13: 346-352. MR 0120168. S2CID 15134755. doi:10.4153/CJM-1961-029-9. «citeseerx: 10.1.1.210.6669». 
• J. Matoušek, J. Vondrak. The Probabilistic Method. Lecture notes.
• Alon, N and Krivelevich, M (2006). Extremal and Probabilistic Combinatorics
• Elishakoff I., Probabilistic Methods in the Theory of Structures: Random Strength of Materials, Random Vibration, and Buckling, World Scientific, Singapore, ISBN 978-981-3149-84-7, 2017
• Elishakoff I., Lin Y.K. and Zhu L.P., Probabilistic and Convex Modeling of Acoustically Excited Structures, Elsevier Science Publishers, Amsterdam, 1994, VIII + pp. 296; ISBN 0 444 81624 0

• Probabilistic Methods in Combinatorics, MIT OpenCourseWare

• Portal:Matemática. Contenido relacionado con Matemática.