En matemáticas e informática , el método probabilístico se utiliza para probar la existencia de objetos matemáticos con propiedades combinatorias deseadas. Las demostraciones son probabilísticas: funcionan mostrando que un objeto aleatorio, elegido de alguna distribución de probabilidad, tiene las propiedades deseadas con probabilidad positiva. En consecuencia, no son constructivos , no describen explícitamente un método eficiente para calcular los objetos deseados.
El método de probabilidades condicionales ( Spencer 1987 ), ( Raghavan 1988 ) convierte tal demostración, en un "sentido muy preciso", en un algoritmo determinista eficiente , uno que está garantizado para calcular 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, para mantener la probabilidad condicional de falla, dadas las opciones hasta ahora, 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 probabilidad condicional verdadera (o expectativa condicional) subyacente a la prueba.
Descripción general
( Raghavan 1988 ) da esta descripción:
- Primero mostramos la existencia de una solución aproximada probablemente buena usando 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 está discutiendo el método en el contexto del redondeo aleatorio , pero funciona con el método probabilístico en general).
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/8/86/Method_of_conditional_probabilities.png/450px-Method_of_conditional_probabilities.png)
Para aplicar el método a una prueba probabilística, el objeto elegido al azar en la prueba debe ser elegible mediante un experimento aleatorio que consiste en una secuencia de elecciones aleatorias "pequeñas".
Aquí hay un ejemplo trivial para ilustrar el principio.
- Lema: Es posible lanzar tres monedas para que el número de colas sea al menos 2.
- Prueba probabilística. Si las tres monedas se lanzan al azar, el número esperado de colas es 1,5. Por lo tanto, debe haber algún resultado (forma de lanzar las monedas) para que el número de colas sea al menos 1.5. Dado que el número de colas es un número entero, en tal resultado hay al menos 2 colas. QED
En este ejemplo, el experimento aleatorio consiste en lanzar tres monedas justas. El experimento se ilustra con el árbol enraizado en el diagrama adyacente. Hay ocho resultados, cada uno correspondiente a una hoja del árbol. Una prueba del experimento aleatorio corresponde a dar un paseo aleatorio desde la raíz (el nodo superior del árbol, donde no se han lanzado monedas) a una hoja. Los resultados exitosos son aquellos en los que al menos dos monedas salieron cruz. Los nodos interiores en el árbol corresponden a resultados parcialmente determinados, donde hasta ahora solo se han lanzado 0, 1 o 2 de las monedas.
Para aplicar el método de probabilidades condicionales, uno se enfoca en la probabilidad condicional de falla, dadas las opciones hasta donde 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. Condicionado en ese estado parcial, la probabilidad de falla es 0.25).
El método de probabilidades condicionales reemplaza la caminata aleatoria de raíz a hoja en el experimento aleatorio por una caminata determinista de raíz a hoja, donde cada paso se elige para mantener inductivamente el siguiente invariante:
- la probabilidad condicional de falla, 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 mantiene 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 es menor que 1 tiene al menos un hijo cuya probabilidad condicional es menor que 1. Por lo tanto, de cualquier nodo interior, siempre se puede elegir algún hijo al que caminar de manera que para mantener el invariante. Dado que el invariante se mantiene al final, cuando la caminata 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 la moneda, sino que se extendió a n voltea para grandes n .
En el caso ideal, dado un estado parcial (un nodo en el árbol), la probabilidad condicional de falla (la etiqueta en el nodo) se puede calcular de manera eficiente y exacta. (El ejemplo anterior es así). Si es así, entonces el algoritmo puede seleccionar el siguiente nodo al que ir calculando las probabilidades condicionales en cada uno de los hijos del nodo actual, luego pasar a cualquier hijo cuya probabilidad condicional sea menor que 1. Como se discutió anteriormente, se garantiza que existe tal nodo.
Desafortunadamente, en la mayoría de las aplicaciones, la probabilidad condicional de falla no es fácil de calcular de manera eficiente. Hay dos técnicas estándar y relacionadas para lidiar con esto:
- 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 el umbral, y esto y (ii) implica que hay un resultado exitoso. (En el ejemplo anterior, Q es el número de colas, que debe ser al menos el umbral 1,5. En muchas aplicaciones, Q es el número de eventos "malos" (no necesariamente inconexos) que ocurren en un resultado dado, donde cada uno evento 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 falla por debajo de 1, basta con mantener la expectativa condicional de Q por debajo (o por encima) del umbral. Para hacer esto, en lugar de calcular la probabilidad condicional de falla, el algoritmo calcula la expectativa condicional de Q y procede en consecuencia: en cada nodo interior, hay algún niño cuya expectativa condicional es como máximo (al menos) la expectativa condicional del nodo; el algoritmo se mueve desde el nodo actual a dicho hijo, manteniendo así la expectativa condicional por debajo (por encima) del umbral.
- Uso de un estimador pesimista: en algunos casos, como un sustituto de la expectativa condicional exacta de la cantidad Q , se usa un límite estrictamente apropiado 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 usando expectativas condicionales
Este ejemplo demuestra el método de probabilidades condicionales utilizando una expectativa condicional.
Lema de corte máximo
Dado cualquier gráfico no dirigido G = ( V , E ), el problema de corte máximo es colorear cada vértice del gráfico con uno de dos colores (digamos negro o blanco) para maximizar el número de bordes cuyos extremos tienen colores diferentes. (Digamos que tal borde está cortado ).
Lema de corte máximo: en cualquier gráfico G = ( V , E ), al menos | Se pueden cortar los bordes E | / 2.
Prueba probabilística. Colorea cada vértice en blanco o negro lanzando una moneda justa. Por cálculo, para cualquier borde e en E , la probabilidad de que se corte es 1/2. Por lo tanto, por linealidad de expectativa , el número esperado de bordes cortados es | E | / 2. Por 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 modele 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 que hay | V | pasos).
Luego, reemplace la elección aleatoria en cada paso por una elección determinista, para mantener la probabilidad condicional de falla, dados los vértices coloreados hasta ahora, por debajo de 1. (Aquí falla 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 calculó la probabilidad de falla directamente; en cambio, la prueba funcionó mostrando que el número esperado de bordes cortados era al menos | E | / 2.
Sea la variable aleatoria Q el número de bordes cortados. Para mantener la probabilidad condicional de falla 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 todavía alcanzable donde Q sea al menos | E | / 2, por lo que la probabilidad condicional de alcanzar tal resultado es positivo.) Para mantener la expectativa condicional de Q en | E | / 2 o superior, el algoritmo, en cada paso, el color del vértice en cuestión con el fin de maximizar la esperanza condicional resultante de Q . Esto es suficiente, porque debe haber algún niño 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 bordes cortados es
- la cantidad de bordes cuyos extremos están coloreados de manera diferente hasta ahora
- + (1/2) * ( el número de aristas con al menos un punto final aún sin colorear ).
Algoritmo
El algoritmo colorea cada vértice para maximizar el valor resultante de la expectativa condicional anterior. Esto está garantizado para mantener la expectativa condicional en | E | / 2 o superior, por lo que se garantiza que la probabilidad condicional de falla se mantenga por debajo de 1, lo que a su vez garantiza un resultado exitoso. Por 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, colorea u blanco. 4. De lo contrario, colorea u negro.
Debido a su derivación, se garantiza que este algoritmo determinista corta al menos la mitad de los bordes del gráfico dado. (Esto lo convierte en un algoritmo de aproximación 0.5 para Max-cut ).
Ejemplo usando 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 gráfico G = ( V , E ) contiene un conjunto independiente de tamaño al menos | V | / ( D +1), donde D = 2 | E | / | V | es el grado medio del gráfico.
Prueba probabilística del teorema de Turán
Considere 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 están en S , añadir u de S 4. Volver S .
Claramente, el proceso calcula un conjunto independiente. Cualquier vértice u que se considera antes de que todos sus vecinos se añadirá a S . Por lo tanto, si d ( u ) denota 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
(La desigualdad anterior 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 aún no considerado y agrega u a S si aún no se ha agregado ninguno de sus vecinos. Deje variable aleatoria Q es el número de vértices añadidos a S . La prueba muestra que E [ Q ] ≥ | V | / ( D +1).
Reemplazaremos cada paso aleatorio por un paso determinista que mantiene la expectativa condicional de Q en o por encima de | V | / ( D +1). Esto asegurará un resultado exitoso, es decir, uno en el que el conjunto independiente S tenga un tamaño de al menos | V | / ( D +1), al darse cuenta de la cota en el teorema de Turán.
Dado que se han dado los primeros t pasos, denote S ( t ) los vértices añadidos hasta ahora. Sea R ( t ) los 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 demostración original, cualquier vértice dado w en R ( t ) tiene una probabilidad condicional de al menos 1 / ( d ( w ) +1) de ser sumado a S , por lo que la expectativa condicional de Q es al menos
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 (0) ≥ | 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 ) por cada t . Dado que el estimador pesimista es un límite inferior de la expectativa condicional, esto asegurará que la expectativa condicional se mantenga por encima de | V | / ( D +1), que a su vez asegurará 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 suma a S y (mediante la inspección de Q ( t ) ), el estimador pesimista no cambia. Si u qué no tienen un vecino en S , entonces T se añade a S .
Por cálculo, si u se elige al azar de los vértices restantes, el aumento esperado en el estimador pesimista no es negativo. [ El cálculo. Condicional a elegir 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 de 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 tanto, debe existir alguna elección de u que evite que el estimador pesimista disminuya.
Algoritmo que maximiza el estimador pesimista
El siguiente algoritmo elige cada vértice u para maximizar el estimador pesimista resultante. Por 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. Si bien existe un vértice u no considerado todavía sin vecino en S :3. Agregue tal vértice u a S donde u minimiza.4. Volver S .
Algoritmos que no maximizan el estimador pesimista
Para que el método de probabilidades condicionales funcione, es suficiente si el algoritmo evita que el estimador pesimista disminuya (o aumente, según corresponda). El algoritmo no necesariamente tiene que maximizar (o minimizar) el estimador pesimista. Esto proporciona cierta flexibilidad para derivar el algoritmo. Los dos algoritmos siguientes ilustran esto.
1. Inicialice S para que sea el conjunto vacío.2. Si bien existe un vértice u en la gráfica sin vecino en S :3. Agregue dicho vértice u a S , donde u minimiza d ( u ) (el grado inicial de u ).4. Volver S .
1. Inicialice S para que sea el conjunto vacío.2. Si bien el gráfico restante no está vacío:3. Suma un vértice u a S , donde u tiene un grado mínimo en el gráfico restante .4. Elimina uy todos sus vecinos del gráfico.5. Volver S .
Cada algoritmo se analiza con el mismo estimador pesimista que antes. Con cada paso de cualquiera de los algoritmos, el aumento neto del estimador pesimista es
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 ,
- ,
donde d ( u ) es el grado de u en la gráfica original.
Para el segundo algoritmo, el aumento neto no es negativo porque, por la elección de u ,
- ,
donde d ′ ( u ) es el grado de u en el gráfico restante.
Ver también
Referencias
- Spencer, Joel H. (1987), Diez conferencias sobre el método probabilístico , SIAM, ISBN 978-0-89871-325-1
- Raghavan, Prabhakar (1988), "Construcción probabilística de algoritmos deterministas: aproximación de programas de empaquetamiento entero", Journal of Computer and System Sciences , 37 (2): 130-143, doi : 10.1016 / 0022-0000 (88) 90003-7.
Otras lecturas
- Alon, Noga ; Spencer, Joel (2008). El método probabilístico . Serie Wiley-Interscience en Matemáticas Discretas y Optimización (Tercera ed.). Hoboken, Nueva Jersey: John Wiley and Sons. págs. 250 y siguientes. ISBN 978-0-470-17020-5. Señor 2437651 . (páginas citadas en la 2a edición, ISBN 9780471653981 )
- Motwani, Rajeev ; Raghavan, Prabhakar (25 de agosto de 1995). Algoritmos aleatorios . Prensa de la Universidad de Cambridge . págs. 120–. ISBN 978-0-521-47465-8.
- Vazirani, Vijay (5 de diciembre de 2002), algoritmos de aproximación , Springer Verlag , págs. 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.