El Método Probabilístico

Todo aquel que se haya enfrentado a problemas matemáticos más allá de los problemas de preparatoria habrá visto problemas de existencia. Es decir, se enuncia una propiedad bajo algún conjunto axiomático y se cuestiona la existencia de algún elemento con dicha propiedad.

Un ejemplo muy básico con la aritmética que todos conocemos y algunos aman es si dado un entero "x", existe otro entero "y" tal que y > x. La respuesta en este caso es que sí existe y basta con decir sea: "y = x + 1".

Estos problemas de existencia por lo regular son resueltos por construcción. Es decir, se exhibe un elemento que cumpla dicha condición (como en el ejemplo anterior, donde a partir de x, se construye y = x + 1).

En otras palabras, si se quiere demostrar que existen los unicornios rosas, siguiendo este estilo de demostraciones se debería mostrar al menos un uniocornio rosa.

Dicho esto, la pregunta que surge naturalmente es si siempre es necesario construir o mostrar un elemento que cumpla con las hipótesis que se piden para completar la demostración.

La respuesta es que no siempre es necesario. Un ejemplo también muy básico es el que da el principio del palomar (también conocido como el principio de Dirichlet). El principio dice que si se tienen n palomares, m palomas y hay más palomas que palomares (es decir m > n), entonces, si todas las palomas están en uno de estos palomares, en algún palomar hay más de una paloma.

En este ejemplo, jamás se exhibió el palomar que tiene más de una paloma para demostrar su existencia.

El método probabilístico es una generalización del principo del palomar. Lo que dice es que si algo tiene probabilidad positiva de existir, entonces existe.

Recuerdese que la probabilidad de que un evento ocurra (en el caso finito), es la cantidad de casos en el que el evento ocurre entre el número total de casos. Por ejemplo, imagine a un mono escribiendo letras al azar con una máquina de escribir. La probabilidad de que el mono escriba una "a" o una "b" es 2/26 (esta máquina de escribir no tiene "ñ"), puesto que los casos favorables son que escriba una "a" o una "b" y la cantidad total de casos son 26.

Para asentar la analogía entre el método probabilístico y el principio de Dirichlet, suponga que P representa la probabilidad de que algún palomar contenga más de una paloma. Ahora sea P1 la probabilidad de que el palomar 1 tenga más de una paloma, P2 la probabilidad de que el palomar 2 tenga más de una paloma, .. , Pn la probabilidad de que el palomar n tenga más de una paloma. Es natural que P1 + P2 + ... + Pn = P (La probabilidad de que algún palomar tenga más de una paloma es la suma de las probabilidades de que el palomar 1 tenga más de una paloma y que el palomar 2 tenga más de una paloma, etc.). Si P = 0, entonces P1 + P2 + ... + Pn = P = 0 y por lo tanto Pi = 0  para todo 1 ≤ i ≤ n  (recuérdese que las probabilidades viven en los números reales entre 0 y 1, incluyendo el 0 y el 1, donde 0 significa que el evento "nunca" ocurre y el 1 que el evento "siempre" ocurre, las comillas están ahí a propósito) Pero si P > 0, entonces P1 + P2 + ... + Pn > 0 y entonces algún Pi > 0. Entonces, dado dicho Pi, debe existir al menos una configuración de palomas en los palomares, en la que el palomar i-ésimo tiene más de una paloma.

En realidad, el problema de construir un objeto conveniente sigue presente (se construye un palomar suficientemente pequeño que contenga suficientes palomas), pero en muchas ocasiones, esto es suficiente para facilitar las demostraciones, que es lo que se busca.

A continuación, un par de ejmplos sobre para qué han sido útiles los métodos probabilísticos.

Un ejemplo entendible es, dado un conjunto finito C de enteros distintos de cero ¿Es posible encontrar un subconjunto A tal que si se suman cualesquiera dos elementos de A el resultado está afuera de A?

La respuesta es obvia y es sí. Tómese el subconjunto A que únicamente contenga a un elemento cualquiera de C y con eso es suficiente. La pregunta verdaderamente interesante es ¿Qué tan grande puede ser este subconjunto?

Utilizando el método probabilístico, Erdös demostró que siempre existe un subconjunto A con dicha propiedad que tiene estrictamente más elementos que la tercera parte de C.

Otro resultado interesante y muy importante tiene que ver con teoría de gráficas (véase este post anterior donde se habla sobre teoría de gráficas).

En teoría de gráficas se define una buena coloración como una manera de colorear los vértices de una gráfica tal que ningún par de vértices adyacentes tengan el mismo color. El número cromático de una gráfica es el número de colores más chiquito con el que se puede conseguir una buena coloración. De alguna manera, si el número cromático es grande, esto nos dice que la gráfica está muy "enredada", o que existen muchas conexiones entre los vértices que no permiten utilizar menos colores.

También se define el cuello de una gráfica como el tamaño del ciclo más chiquito que contiene. Un cuello grande, de alguna manera nos dice que la gráfica no está tan "enredada", es decir, se pueden encontrar conjuntos de vértices grandes donde ninguno está conectado con otro.

La conjetura obvia es que si el cuello de una gráfica es grande, entonces su número cromático estaba condenado a no ser muy grande (es decir, si la gráfica no está tan "enredada", entonces se necesitan relativamente pocos colores para "bien colorearla"). Lo que Erdös logró demostrar utilizando el método probabilístico es que esta conjetura es falsa y que dados dos números cualesquiera n y m, se podía encontrar una gráfica con cuello más grande que n y número cromático más grande que m.

Si alguien quiere aprender más sobre el método probabilístico, le recomiendo buscar el libro de
Noga Alon y Joel H. Spencer  titulado "The Probabilistic Method".

Y para aquellos que están estudiando en fismat, tal vez consigan que Malú les dé un curso al respecto.