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 .
Si cada objeto de una colección de objetos no tiene una propiedad determinada, entonces la probabilidad de que un objeto aleatorio elegido 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 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 .
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 ) .
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:
(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
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 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
(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.
Un artículo de Erdős de 1959 (ver la referencia citada a continuación) abordó el siguiente problema en la teoría de grafos : dados los números enteros positivos g y k , ¿existe un grafo G que contenga solo 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:
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
y cada uno de ellos está presente en G con probabilidad p i . Por lo tanto, por la desigualdad de Markov tenemos
Demostración. Sea Y el tamaño del conjunto independiente más grande en G. Claramente, tenemos
cuando
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 .
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.
![{\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)
