Método de probabilidades condicionales

En matemáticas y ciencias de la computación , el método de probabilidades condicionales ^{[1] [2]} es un método sistemático para convertir pruebas de existencia probabilísticas no constructivas en algoritmos deterministas eficientes que construyen explícitamente el objeto deseado. ^[3]

A menudo, el método probabilístico se utiliza para demostrar la existencia de objetos matemáticos con algunas propiedades combinatorias deseadas. Las pruebas de ese método funcionan mostrando que un objeto aleatorio, elegido de alguna distribución de probabilidad, tiene las propiedades deseadas con probabilidad positiva. En consecuencia, no son constructivas : no describen explícitamente un método eficiente para calcular los objetos deseados.

El método de probabilidades condicionales convierte una prueba de este tipo, en un "sentido muy preciso", en un algoritmo determinista eficiente , que garantiza el cálculo de un objeto con las propiedades deseadas. Es decir, el método desaleatoriza la prueba. La idea básica es reemplazar cada elección aleatoria en un experimento aleatorio por una elección determinista, de modo de mantener la probabilidad condicional de fracaso, dadas las elecciones realizadas hasta el momento, por debajo de 1.

El método es particularmente relevante en el contexto del redondeo aleatorio (que utiliza el método probabilístico para diseñar algoritmos de aproximación ).

Al aplicar el método de probabilidades condicionales, el término técnico "estimador pesimista" se refiere a una cantidad utilizada en lugar de la verdadera probabilidad condicional (o expectativa condicional) subyacente a la prueba.

Descripción general

Raghavan ^[2] da esta descripción:

Primero mostramos la existencia de una solución aproximada demostrablemente buena utilizando el método probabilístico ... [Luego] mostramos que la prueba de existencia probabilística se puede convertir, en un sentido muy preciso, en un algoritmo de aproximación determinista.

Raghavan analiza el método en el contexto del redondeo aleatorio , pero funciona con el método probabilístico en general.

El método de probabilidades condicionales

Para aplicar el método a una prueba probabilística, el objeto elegido aleatoriamente en la prueba debe ser seleccionable mediante un experimento aleatorio que consiste en una secuencia de elecciones aleatorias "pequeñas".

He aquí un ejemplo trivial para ilustrar el principio.

Lema: Es posible lanzar tres monedas tal que el número de cruces sea al menos 2.

Demostración probabilística. Si se lanzan tres monedas al azar, el número esperado de cruces es 1,5. Por lo tanto, debe haber algún resultado (forma de lanzar las monedas) tal que el número de cruces sea al menos 1,5. Como el número de cruces es un número entero, en tal resultado hay al menos 2 cruces. QED

En este ejemplo, el experimento aleatorio consiste en lanzar tres monedas al aire. El experimento se ilustra con el árbol con raíces del diagrama adyacente. Hay ocho resultados, cada uno de los cuales corresponde a una hoja del árbol. Una prueba del experimento aleatorio corresponde a un recorrido aleatorio desde la raíz (el nodo superior del árbol, donde no se han lanzado monedas) hasta una hoja. Los resultados exitosos son aquellos en los que al menos dos monedas salieron cruz. Los nodos interiores del árbol corresponden a resultados parcialmente determinados, donde hasta el momento solo se han lanzado 0, 1 o 2 de las monedas.

Para aplicar el método de probabilidades condicionales, nos centramos en la probabilidad condicional de fracaso, dadas las opciones a medida que el experimento avanza paso a paso. En el diagrama, cada nodo está etiquetado con esta probabilidad condicional. (Por ejemplo, si solo se ha lanzado la primera moneda y sale cruz, eso corresponde al segundo hijo de la raíz. Condicionada a ese estado parcial, la probabilidad de fracaso es 0,25.)

El método de probabilidades condicionales reemplaza el recorrido aleatorio de raíz a hoja en el experimento aleatorio por un recorrido determinista de raíz a hoja, donde cada paso se elige para mantener inductivamente la siguiente invariante:

La probabilidad condicional de fallo, dado el estado actual, es menor que 1.

De esta forma se garantiza llegar a una hoja con etiqueta 0, es decir, un resultado exitoso.

El invariante se cumple inicialmente (en la raíz), porque la prueba original mostró que la probabilidad (incondicionada) de falla es menor que 1. La probabilidad condicional en cualquier nodo interior es el promedio de las probabilidades condicionales de sus hijos. La última propiedad es importante porque implica que cualquier nodo interior cuya probabilidad condicional sea menor que 1 tiene al menos un hijo cuya probabilidad condicional es menor que 1. Por lo tanto, desde cualquier nodo interior, uno siempre puede elegir algún hijo hacia el cual caminar de modo de mantener el invariante. Dado que el invariante se cumple al final, cuando el paseo llega a una hoja y se han determinado todas las opciones, el resultado alcanzado de esta manera debe ser exitoso.

Eficiencia

En una aplicación típica del método, el objetivo es poder implementar el proceso determinista resultante mediante un algoritmo razonablemente eficiente (la palabra "eficiente" generalmente significa un algoritmo que se ejecuta en tiempo polinomial ), aunque normalmente el número de resultados posibles es enorme (exponencialmente grande). Por ejemplo, considere la tarea de lanzar una moneda, pero extendida a n lanzamientos para un valor grande de n .

En el caso ideal, dado un estado parcial (un nodo en el árbol), la probabilidad condicional de falla (la etiqueta del nodo) se puede calcular de manera eficiente y exacta. (El ejemplo anterior es así). Si esto es así, entonces el algoritmo puede seleccionar el próximo nodo al que ir calculando las probabilidades condicionales en cada uno de los hijos del nodo actual, y luego pasar a cualquier hijo cuya probabilidad condicional sea menor que 1. Como se mencionó anteriormente, se garantiza que existe dicho nodo.

Lamentablemente, en la mayoría de las aplicaciones, la probabilidad condicional de falla no es fácil de calcular de manera eficiente. Existen dos técnicas estándar y relacionadas para abordar este problema:

Usando una expectativa condicional

Muchas pruebas probabilísticas funcionan de la siguiente manera: definen implícitamente una variable aleatoria Q , muestran que (i) la expectativa de Q es como máximo (o al menos) algún valor umbral, y (ii) en cualquier resultado donde Q es como máximo (al menos) este umbral, el resultado es un éxito. Entonces (i) implica que existe un resultado donde Q es como máximo (al menos) el umbral, y esto y (ii) implican que hay un resultado exitoso. (En el ejemplo anterior, Q es el número de colas, que debería ser al menos el umbral 1,5. En muchas aplicaciones, Q es el número de eventos "malos" (no necesariamente disjuntos) que ocurren en un resultado dado, donde cada evento malo corresponde a una forma en que el experimento puede fallar, y el número esperado de eventos malos que ocurren es menor que 1).

En este caso, para mantener la probabilidad condicional de fallo por debajo de 1, basta con mantener la expectativa condicional de Q por debajo (o por encima) del umbral. Para ello, en lugar de calcular la probabilidad condicional de fallo, el algoritmo calcula la expectativa condicional de Q y procede en consecuencia: en cada nodo interior, hay algún hijo cuya expectativa condicional es como máximo (al menos) la expectativa condicional del nodo; el algoritmo se desplaza desde el nodo actual hasta ese hijo, manteniendo así la expectativa condicional por debajo (por encima) del umbral.

Utilizando un estimador pesimista

En algunos casos, como proxy de la expectativa condicional exacta de la cantidad Q , se utiliza un límite adecuadamente ajustado llamado estimador pesimista . El estimador pesimista es una función del estado actual. Debe ser un límite superior (o inferior) para la expectativa condicional de Q dado el estado actual, y debe ser no creciente (o no decreciente) en expectativa con cada paso aleatorio del experimento. Por lo general, un buen estimador pesimista se puede calcular deconstruyendo con precisión la lógica de la prueba original.

Ejemplo de uso de expectativas condicionales

Este ejemplo demuestra el método de probabilidades condicionales utilizando una expectativa condicional.

Lema de corte máximo

Dado cualquier grafo no dirigido G = ( V , E ), el problema de corte máximo es colorear cada vértice del grafo con uno de dos colores (por ejemplo, negro o blanco) de modo de maximizar la cantidad de aristas cuyos puntos finales tienen diferentes colores. (Digamos que dicha arista es cortada ).

Lema de corte máximo: en cualquier grafo G = ( V , E ), se pueden cortar al menos | E |/2 aristas.

Prueba probabilística. Colorea cada vértice de negro o blanco lanzando una moneda al aire. Por cálculo, para cualquier arista e en E , la probabilidad de que sea cortada es 1/2. Por lo tanto, por linealidad de expectativa , el número esperado de aristas cortadas es | E |/2. Por lo tanto, existe una coloración que corta al menos | E |/2 aristas. QED

El método de probabilidades condicionales con expectativas condicionales

Para aplicar el método de probabilidades condicionales, primero modelamos el experimento aleatorio como una secuencia de pequeños pasos aleatorios. En este caso, es natural considerar que cada paso es la elección del color para un vértice en particular (por lo tanto, hay | V | pasos).

A continuación, sustituya la elección aleatoria en cada paso por una elección determinista, de modo de mantener la probabilidad condicional de fallo, dados los vértices coloreados hasta ahora, por debajo de 1. (Aquí, fallo significa que finalmente se cortan menos de | E |/2 aristas).

En este caso, la probabilidad condicional de falla no es fácil de calcular. De hecho, la prueba original no calculaba la probabilidad de falla directamente; en cambio, la prueba funcionaba mostrando que el número esperado de bordes cortados era al menos | E |/2.

Sea la variable aleatoria Q el número de aristas cortadas. Para mantener la probabilidad condicional de fallo por debajo de 1, basta con mantener la expectativa condicional de Q en o por encima del umbral | E |/2. Esto se debe a que, siempre que la expectativa condicional de Q sea al menos | E |/2, debe haber algún resultado aún alcanzable donde Q sea al menos | E |/2, por lo que la probabilidad condicional de alcanzar dicho resultado es positiva. Para mantener la expectativa condicional de Q en | E |/2 o por encima, el algoritmo, en cada paso, coloreará el vértice en consideración de modo de maximizar la expectativa condicional resultante de Q. Esto es suficiente, porque debe haber algún hijo cuya expectativa condicional sea al menos la expectativa condicional del estado actual (y, por lo tanto, al menos | E |/2).

Dado que algunos de los vértices ya están coloreados, ¿cuál es esta expectativa condicional? Siguiendo la lógica de la prueba original, la expectativa condicional del número de aristas cortadas es

la cantidad de aristas cuyos puntos finales están coloreados de manera diferente hasta el momento

+ (1/2)*( el número de aristas con al menos un punto final aún no coloreado ).

Algoritmo

El algoritmo colorea cada vértice para maximizar el valor resultante de la expectativa condicional anterior. Esto garantiza que la expectativa condicional se mantenga en | E |/2 o superior, y por lo tanto garantiza que la probabilidad condicional de falla se mantenga por debajo de 1, lo que a su vez garantiza un resultado exitoso. Mediante el cálculo, el algoritmo se simplifica a lo siguiente:

1. Para cada vértice u en V (en cualquier orden): 2. Considere los vértices vecinos ya coloreados de u . 3. Entre estos vértices, si hay más negros que blancos, entonces colorea u de blanco. 4. De lo contrario, coloréalo de negro.

Debido a su derivación, se garantiza que este algoritmo determinista cortará al menos la mitad de los bordes del gráfico dado. Esto lo convierte en un algoritmo de aproximación de 0,5 para Max-cut .

Ejemplo utilizando estimadores pesimistas

El siguiente ejemplo demuestra el uso de estimadores pesimistas.

Teorema de Turán

Una forma de enunciar el teorema de Turán es la siguiente:

Cualquier grafo G = ( V , E ) contiene un conjunto independiente de tamaño al menos | V |/( D +1), donde D = 2| E |/| V | es el grado promedio del grafo.

Demostración probabilística del teorema de Turán

Consideremos el siguiente proceso aleatorio para construir un conjunto independiente S :

1. Inicialice S para que sea el conjunto vacío. 2. Para cada vértice u en V en orden aleatorio: 3. Si no hay vecinos de u en S , agregue u a S 4. Devuelva S .

Claramente, el proceso calcula un conjunto independiente. Cualquier vértice u que se considere antes que todos sus vecinos se agregará a S. Por lo tanto, dejando que d ( u ) denote el grado de u , la probabilidad de que u se agregue a S es al menos 1/( d ( u )+1). Por linealidad de la expectativa , el tamaño esperado de S es al menos

${\displaystyle \sum _{u\in V}{\frac {1}{d(u)+1}}~\geq ~{\frac {|V|}{D+1}}.}$

(La desigualdad anterior se sigue porque 1/( x +1) es convexo en x , por lo que el lado izquierdo se minimiza, sujeto a que la suma de los grados se fije en 2| E |, cuando cada d ( u ) = D = 2| E |/| V |.) QED

El método de probabilidades condicionales utilizando estimadores pesimistas

En este caso, el proceso aleatorio tiene | V | pasos. Cada paso considera algún vértice u que aún no se ha considerado y suma u a S si ninguno de sus vecinos ha sido agregado aún. Sea la variable aleatoria Q el número de vértices agregados a S . La prueba muestra que E [ Q ] ≥ | V |/( D +1).

Reemplazaremos cada paso aleatorio por un paso determinista que mantenga la esperanza condicional de Q en o por encima de | V |/( D +1). Esto garantizará un resultado exitoso, es decir, uno en el que el conjunto independiente S tenga un tamaño de al menos | V |/( D +1), lo que cumple con el límite del teorema de Turán.

Dado que se han dado los primeros t pasos, sea S ^{( t )} los vértices añadidos hasta ahora. Sea R ^{( t )} aquellos vértices que aún no se han considerado, y que no tienen vecinos en S ^{( t )} . Dados los primeros t pasos, siguiendo el razonamiento de la prueba original, cualquier vértice w en R ^{( t )} tiene una probabilidad condicional de al menos 1/( d ( w )+1) de ser añadido a S , por lo que la esperanza condicional de Q es al menos

${\displaystyle |S^{(t)}|~+~\sum _{w\in R^{(t)}}{\frac {1}{d(w)+1}}.}$

Sea Q ^{( t )} la cantidad anterior, que se denomina estimador pesimista de la expectativa condicional.

La prueba mostró que el estimador pesimista es inicialmente al menos | V |/( D +1). (Es decir, Q ⁽⁰⁾ ≥ | V |/( D +1).) El algoritmo hará cada elección para evitar que el estimador pesimista disminuya, es decir, de modo que Q ^{( t +1)} ≥ Q ^{( t )} para cada t . Dado que el estimador pesimista es un límite inferior de la expectativa condicional, esto garantizará que la expectativa condicional se mantenga por encima de | V |/( D +1), lo que a su vez garantizará que la probabilidad condicional de falla se mantenga por debajo de 1.

Sea u el vértice considerado por el algoritmo en el siguiente paso (( t +1)-st).

Si u ya tiene un vecino en S , entonces u no se agrega a S y (por inspección de Q ^{( t )} ), el estimador pesimista no cambia. Si u no tiene un vecino en S , entonces u se agrega a S .

Por cálculo, si u se elige aleatoriamente de los vértices restantes, el aumento esperado en el estimador pesimista no es negativo. [ El cálculo. Condicionado a la elección de un vértice en R ^{( t )} , la probabilidad de que un término dado 1/( d ( w )+1) se elimine de la suma en el estimador pesimista es como máximo ( d ( w )+1)/| R ^{( t )} |, por lo que la disminución esperada en cada término en la suma es como máximo 1/| R ^{( t )} |. Hay términos R ^{( t )} en la suma. Por lo tanto, la disminución esperada en la suma es como máximo 1. Mientras tanto, el tamaño de S aumenta en 1.]

Por lo tanto, debe existir alguna elección de u que evite que el estimador pesimista disminuya.

Algoritmo que maximiza el estimador pesimista

El algoritmo que se muestra a continuación elige cada vértice u para maximizar el estimador pesimista resultante. Según las consideraciones anteriores, esto evita que el estimador pesimista disminuya y garantiza un resultado exitoso.

A continuación, N ^{( t )} ( u ) denota los vecinos de u en R ^{( t )} (es decir, vecinos de u que no están en S ni tienen un vecino en S ).

1. Inicialice S para que sea el conjunto vacío.2. Mientras exista un vértice u
aún no considerado sin vecino en S :3. Añade un vértice u a S donde u minimiza . ${\displaystyle \sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1}}}$4. Devolver S .

Algoritmos que no maximizan el estimador pesimista

Para que el método de probabilidades condicionales funcione, basta con que el algoritmo evite que el estimador pesimista disminuya (o aumente, según corresponda). El algoritmo no necesariamente tiene que maximizar (o minimizar) el estimador pesimista. Esto brinda cierta flexibilidad para derivar el algoritmo. Los dos algoritmos siguientes lo ilustran.

1. Inicialice S para que sea el conjunto vacío.2. Mientras exista un vértice u en el grafo sin vecino en S :3. Agregue un vértice u a S , donde u minimiza d ( u ) (el grado inicial de u ).4. Devolver S .

1. Inicialice S para que sea el conjunto vacío.2. Mientras el gráfico restante no esté vacío:3. Agregue un vértice u a S , donde u tiene grado mínimo en el gráfico restante .4. Elimina u y todos sus vecinos del gráfico.5. Devolver S .

Cada algoritmo se analiza con el mismo estimador pesimista que antes. Con cada paso de cada algoritmo, el aumento neto en el estimador pesimista es

${\displaystyle 1-\sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1}},}$

donde N ^{( t )} ( u ) denota los vecinos de u en el gráfico restante (es decir, en R ^{( t )} ).

Para el primer algoritmo, el aumento neto no es negativo porque, por la elección de u ,

${\displaystyle \sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1}}\leq (d(u)+1){\frac {1}{d(u)+1}}=1}$,

donde d ( u ) es el grado de u en el gráfico original.

Para el segundo algoritmo, el aumento neto no es negativo porque, por la elección de u ,

${\displaystyle \sum _{w\in N^{(t)}(u)\cup \{u\}}{\frac {1}{d(w)+1}}\leq (d'(u)+1){\frac {1}{d'(u)+1}}=1}$,

donde d′ ( u ) es el grado de u en el gráfico restante.

Véase también

• Método probabilístico
• Desaleatorización
• Redondeo aleatorio

Referencias

1. Spencer, Joel H. (1987), Diez conferencias sobre el método probabilístico, SIAM, ISBN 978-0-89871-325-1
2. Raghavan, Prabhakar (1988), "Construcción probabilística de algoritmos deterministas: aproximación de programas de empaquetamiento de números enteros", Journal of Computer and System Sciences , 37 (2): 130–143, doi : 10.1016/0022-0000(88)90003-7
3. El método probabilístico — método de probabilidades condicionales, entrada de blog de Neal E. Young, consultado el 19/04/2012 y el 14/09/2023.

Lectura adicional

El método de redondeo condicional se explica en varios libros de texto:

• Alon, Noga ; Spencer, Joel (2008). El método probabilístico. Serie Wiley-Interscience en Matemática discreta y optimización (tercera edición). Hoboken, NJ: John Wiley and Sons. pp. 250 y siguientes. ISBN 978-0-470-17020-5.Sr. 2437651  .(páginas citadas en la 2ª edición, ISBN 9780471653981 ) 

• Motwani, Rajeev ; Raghavan, Prabhakar (25 de agosto de 1995). Algoritmos aleatorios. Cambridge University Press . págs. 120–. ISBN 978-0-521-47465-8.

• Vazirani, Vijay (5 de diciembre de 2002), Algoritmos de aproximación, Springer Verlag , pp. 130–, ISBN 978-3-540-65367-7

Enlaces externos

• El método probabilístico — método de probabilidades condicionales, entrada de blog de Neal E. Young, consultado el 19/04/2012.