## [Método Probabilístico](/es/node/60321) Definición 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 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 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 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 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 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 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 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 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.