Método probabilístico

Método no constructivo para demostraciones matemáticas

En matemáticas , el método probabilístico es un método no constructivo , utilizado principalmente en combinatoria y desarrollado por Paul Erdős , para demostrar la existencia de un tipo prescrito de objeto matemático. Funciona demostrando que si uno elige objetos al azar de una clase específica, la probabilidad de que el resultado sea del tipo prescrito es estrictamente mayor que cero. Aunque la prueba utiliza la probabilidad, la conclusión final está determinada con certeza , sin ningún error posible.

Este método ahora 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 la informática (por ejemplo, el redondeo aleatorio ) y la teoría de la información .

Introducción

Si cada objeto de una colección de objetos no tiene una propiedad determinada, entonces la probabilidad de que un objeto elegido al azar de la colección tenga esa propiedad es cero.

De manera similar, demostrar que la probabilidad es (estrictamente) menor que 1 puede usarse 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 al valor esperado calculado, ya que la inexistencia de dicho elemento implicaría que cada elemento en el espacio muestral es menor que el valor esperado, una contradicción.

Las herramientas comunes utilizadas en el método probabilístico incluyen la desigualdad de Markov , el límite de Chernoff y el lema local de Lovász .

Dos ejemplos debidos a Erdős

Aunque otros antes que él demostraron teoremas mediante el método probabilístico (por ejemplo, el resultado de Szele de 1943 de que existen torneos que contienen una gran cantidad 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 un límite inferior para el número de Ramsey R ( r , r ) .

Primer ejemplo

Supongamos que tenemos un grafo completo de n vértices . Queremos demostrar (para valores suficientemente pequeños de n ) que es posible colorear los bordes del grafo con dos colores (por ejemplo, rojo y azul) de modo que no exista ningún subgrafo completo de r vértices que sea monocromático (cada borde coloreado del mismo color).

Para ello, coloreamos el gráfico de forma aleatoria. Coloreamos cada arista de forma independiente con una probabilidad de 1/2 de ser roja y 1/2 de ser azul. Calculamos el número esperado de subgrafos monocromáticos en r vértices de la siguiente manera:

Para cualquier conjunto de vértices de nuestro gráfico, defina la variable como 1 si cada arista entre los vértices es del mismo color y 0 en caso contrario. Tenga en cuenta que la cantidad de subgrafos monocromáticos es la suma de todos los subconjuntos posibles . Para cualquier conjunto individual , el valor esperado de es simplemente la probabilidad de que todas las aristas en sean del mismo color: ${\displaystyle S_{r}}$ ${\displaystyle r}$ ${\displaystyle X(S_{r})}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle X(S_{r})}$ ${\displaystyle S_{r}}$ ${\displaystyle S_{r}^{i}}$ ${\displaystyle X(S_{r}^{i})}$ ${\displaystyle C(r,2)}$ ${\displaystyle S_{r}^{i}}$

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

(el factor 2 viene porque hay dos colores posibles).

Esto es válido para cualquiera de los subconjuntos posibles que podríamos haber elegido, es decir, los que van desde 1 hasta . Por lo tanto, tenemos que la suma de todos es ${\displaystyle C(n,r)}$ ${\displaystyle i}$ ${\displaystyle C(n,r)}$ ${\displaystyle E[X(S_{r}^{i})]}$ ${\displaystyle S_{r}^{i}}$

${\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 expectativa de la suma ( independientemente de si las variables son independientes ), por lo que la expectativa de la suma (el número esperado de todos los subgrafos monocromáticos) es ${\displaystyle r}$

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

Considere lo que sucede si este valor es menor que 1. Dado que el número esperado de subgrafos r monocromáticos es estrictamente menor que 1 , existe una coloración que satisface la condición de que el número de subgrafos r monocromáticos sea estrictamente menor que 1. El número de subgrafos r monocromáticos en esta coloración aleatoria es un 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 es válido, por ejemplo, para n = 5 y r = 4 ), debe existir una coloración en la que no haya r -subgrafos monocromáticos. ^[a]

Por definición del número 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 . Aunque demuestra (por ejemplo) que casi todas las coloraciones del grafo completo en (1.1) ^r vértices no contienen ningún r -subgrafo monocromático , no da ningún ejemplo explícito de tal coloración. El problema de encontrar tal coloración ha estado abierto durante más de 50 años.

---

1. El mismo hecho se puede demostrar sin probabilidad, utilizando un simple argumento de conteo:
   • El número total de r -subgrafos es . ${\displaystyle {n \choose r}}$
   • Cada subgrafo r tiene aristas y por lo tanto puede colorearse de diferentes maneras. ${\displaystyle {r \choose 2}}$ ${\displaystyle 2^{r \choose 2}}$
   • De estas coloraciones, solo 2 son "malas" para ese subgrafo (las coloraciones en las que todos los vértices son rojos o todos los vértices son azules).
   • Por lo tanto, el número total de coloraciones que son malas para algún subgrafo (al menos uno) es como máximo . ${\displaystyle 2{n \choose r}2^{{n \choose 2}-{r \choose 2}}}$
   • Por lo tanto, si , debe haber al menos una coloración que no sea "mala" para ningún subgrafo. ${\displaystyle 2{n \choose r}2^{{n \choose 2}-{r \choose 2}}<2^{n \choose 2}\Leftrightarrow {n \choose r}2^{1-{r \choose 2}}<1}$

Segundo ejemplo

Un artículo de Erdős de 1959 (ver referencia citada a continuación) abordó el siguiente problema en teoría de grafos : dados los números enteros positivos g y k , ¿existe un grafo G que contenga sólo ciclos de longitud al menos g , tales que el número cromático de G sea al menos k ?

Se puede demostrar que existe un grafo de este tipo para cualquier g y k , y la prueba es razonablemente sencilla. Sea n muy grande y consideremos un grafo aleatorio G en n vértices, donde cada arista en G existe con probabilidad p = n ^{1/ g  −1} . Demostramos 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 en n vértices 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 Markov tenemos

${\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 valor n suficientemente grande , la propiedad 1 se cumple con una probabilidad de más de 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 conjunto independiente más grande en G . Claramente, tenemos

${\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 de más de 1/2 .

Para un n suficientemente grande , la probabilidad de que un gráfico 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, podemos eliminar como máximo n /2 vértices de G para obtener un nuevo grafo G′ sobre vértices que contiene solo ciclos de longitud al menos g . Podemos ver que este nuevo grafo no tiene un conjunto independiente de tamaño . G′ solo se puede dividir en al menos k conjuntos independientes y, por lo tanto, tiene un número cromático al menos k . ${\displaystyle n'\geq n/2}$ ${\displaystyle \left\lceil {\frac {n'}{k}}\right\rceil }$

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

Véase también

• Portal de matemáticas

• Sistema de prueba interactivo
• Algoritmo de Las Vegas
• Método de incompresibilidad
• Método de probabilidades condicionales
• Pruebas probabilísticas de teoremas no probabilísticos
• Gráfico aleatorio

Recursos adicionales

• Métodos probabilísticos en combinatoria, MIT OpenCourseWare

Referencias

• Alon, Noga; Spencer, Joel H. (2000). El método probabilístico (2.ª edición). Nueva York: Wiley-Interscience. ISBN  0-471-37046-0 .
• Erdős, P. (1959). "Teoría de grafos y probabilidad". Can. J. Math . 11 : 34–38. doi : 10.4153/CJM-1959-003-9 . MR  0102081. S2CID  122784453.
• Erdős, P. (1961). "Teoría de grafos y probabilidad, II". Can. J. Math . 13 : 346–352. CiteSeerX  10.1.1.210.6669 . doi :10.4153/CJM-1961-029-9. MR  0120168. S2CID  15134755.
• J. Matoušek , J. Vondrak. El método probabilístico. Apuntes de conferencias.
• Alon, N y Krivelevich, M (2006). Combinatoria extrema y probabilística
• Elishakoff I., Métodos probabilísticos en la teoría de estructuras: resistencia aleatoria de materiales, vibración aleatoria y pandeo, World Scientific, Singapur, ISBN 978-981-3149-84-7 , 2017 
• Elishakoff I., Lin YK y Zhu LP, Modelado probabilístico y convexo de estructuras acústicamente excitadas, Elsevier Science Publishers, Ámsterdam, 1994, VIII + pp. 296; ISBN 0 444 81624 0 

Notas al pie