Una técnica no constructiva en combinatoria y matemáticas discretas que prueba la existencia de un objeto o estima su tamaño mostrando que una construcción aleatoria apropiada tiene probabilidad positiva de poseer la propiedad deseada.

Principio

Definir un espacio de probabilidad de estructuras candidatas y usar esperanza, varianza, desigualdades de concentración o lemas de dependencia para demostrar que el evento 'la estructura tiene la propiedad P' ocurre con probabilidad positiva; por tanto existe un objeto con P.

Demostración

Para probar que existe un grafo con girth grande y alto número cromático, considerar un modelo de grafo aleatorio con probabilidad de arista adecuada, calcular esperanzas del número de ciclos cortos y de coloraciones, y emplear cotas probabilísticas para concluir una probabilidad positiva de evitar demasiados ciclos cortos mientras se requieren muchas colores.

Aplicación incorrecta

Tratar una afirmación de alta probabilidad como si diera una construcción explícita o ignorar las condiciones de independencia/dependencia al aplicar desigualdades de concentración; afirmar constructibilidad algorítmica a partir de una prueba de existencia probabilística sin trabajo adicional.

Consecuencia

Provee pruebas de existencia y con frecuencia cotas cuantitativas (esperanzas, umbrales) cuando las construcciones explícitas son difíciles; orienta la búsqueda de versiones constructivas e informa sobre el comportamiento típico de objetos combinatorios.

Inversión

Un método combinatorio constructivo que produce un ejemplo explícito o un algoritmo determinista que construye el objeto con la propiedad deseada, en oposición a probar mera existencia mediante la aleatoriedad.

Límite

Se aplica a estructuras combinatorias finitas o sus modelos probabilísticos; por sí mismo no produce algoritmos explícitos ni certificados sin técnicas de desaleatorización; presupone un espacio de probabilidad bien definido y estimaciones probabilísticas verificables.

Tensión semántica

Tensión entre la existencia no constructiva (probabilidad positiva de existencia) y las demandas constructivas (ejemplo explícito o algoritmo eficiente), y entre afirmaciones típicas en un modelo aleatorio y requisitos en el peor caso.

Síntesis

El Método Probabilístico reúne razonamiento probabilístico y enumeración combinatoria: al seleccionar aleatoriamente un objeto según una distribución adecuada y controlar su comportamiento típico, se transforman cotas probabilísticas en pruebas deterministas de existencia o estimaciones de tamaño de estructuras discretas.