En matemáticas , el método probabilístico es un método no constructivo , utilizado principalmente en combinatoria y del que fue pionero Paul Erdős , para demostrar la existencia de un tipo prescrito de objeto matemático. Funciona mostrando que si uno elige aleatoriamente objetos 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 se determina con certeza , sin ningún posible error.
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 informática (p. ej., redondeo aleatorio ) y teoría de la información .
Si cada objeto de una colección de objetos no tiene una determinada propiedad, 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 probar 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 prueba que la variable aleatoria también puede tomar un valor mayor que el valor esperado.
Alternativamente, el método probabilístico también se puede utilizar 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 no existencia de dicho elemento implicaría que todos los elementos del espacio muestral 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 , la cota de Chernoff y el lema local de Lovász .
Aunque otros antes que él demostraron teoremas mediante el método probabilístico (por ejemplo, el resultado de Szele en 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 siguiente describe uno de esos resultados de 1947 que proporciona una prueba de un límite inferior para el número de Ramsey R ( r , r ) .
Supongamos que tenemos una gráfica completa en n vértices . Deseamos mostrar (para valores suficientemente pequeños de n ) que es posible colorear los bordes del gráfico en dos colores (por ejemplo, rojo y azul) de modo que no haya un subgrafo completo en r vértices que sea monocromático (cada borde coloreó el el mismo color).
Para ello, coloreamos el gráfico al azar. Colorea cada borde de forma independiente con una probabilidad de 1/2 de ser rojo 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 borde entre los vértices es del mismo color y 0 en caso contrario. Tenga en cuenta que el número 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 todos los bordes sean del mismo color:
(el factor de 2 viene porque hay dos colores posibles).
Esto es válido para cualquiera de los posibles subconjuntos que podríamos haber elegido, es decir, oscila entre 1 y . Entonces tenemos que la suma de todo es
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
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 número entero no negativo , por lo tanto debe ser 0 ( 0 es el único número entero no negativo menor que 1 ). Se deduce que si
(que 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 no es nada constructivo . Aunque demuestra (por ejemplo) que casi todos los colores del gráfico completo en (1.1) r vértices no contienen ningún subgrafo r monocromático , no da ningún ejemplo explícito de tal coloración. El problema de encontrar ese color está abierto desde hace más de 50 años.
Un artículo de Erdős de 1959 (ver referencia citada a continuación) abordó el siguiente problema en teoría de grafos : dados enteros positivos g y k , ¿existe un gráfico G que contenga solo ciclos de longitud al menos g , tal que el número cromático de G esté en menos k ?
Se puede demostrar que dicha gráfica existe para cualquier g y k , y la demostración es razonablemente simple. Sea n muy grande y considere un gráfico 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:
Prueba. Sea X el número de ciclos de longitud menor que g . El número de ciclos de longitud i en el gráfico completo en n vértices es
y cada uno de ellos está presente en G con probabilidad p i . Por tanto, por la desigualdad de Markov tenemos
Prueba. Sea Y el tamaño del conjunto independiente más grande en G. Claramente, tenemos
cuando
Para n suficientemente grande , la probabilidad de que una gráfica de la distribución tenga ambas propiedades es positiva, ya que los eventos de estas propiedades no pueden ser disjuntos (si lo fueran, sus probabilidades sumarían más de 1).
Aquí viene el truco: dado que G tiene estas dos propiedades, podemos eliminar como máximo n /2 vértices de G para obtener un nuevo gráfico G′ en vértices que contenga solo ciclos de longitud al menos g . Podemos ver que este nuevo gráfico no tiene un conjunto de tamaño independiente . G′ solo puede dividirse en al menos k conjuntos independientes y, por tanto, tiene un número cromático de al menos k .
Este resultado da una idea 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 aún puede ser arbitrariamente grande.
![{\displaystyle E[X(S_{r}^{i})]=2\cdot 2^{-{r \choose 2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/55f2a3968a735e2d03d22b083795f908fcb9d76c)
![{\displaystyle E[X(S_{r}^{i})]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/acb8e55c98477c024f04c7aa0ec08dc65a82d725)
![{\displaystyle \sum _{i=1}^{C(n,r)}E[X(S_{r}^{i})]={n \choose r}2^{1-{r \choose 2}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a73c9df0fd5abe02b4fb746dde2c462809f46a17)
![{\displaystyle E[X(S_{r})]={n \choose r}2^{1-{r \choose 2}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87fa5008b48a895148e9f07d5851496e8877921b)
![{\displaystyle E[X(S_{r})]={n \elija r}2^{1-{r \elija 2}}<1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9350681c2759e6d12c9ad85d6233d51fad057a07)
![{\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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/47f8b2c929ed4d0df7f4f46606d4dd8b2556ab62)
