Algoritmo aleatorizado

Parte de una serie sobre
Estructuras de datos probabilísticas
Filtro de floración Esbozo de conteo mínimo Filtro de cociente Lista de omisión
Árboles aleatorios
Árbol binario aleatorio Treap Árbol aleatorio de exploración rápida
Relacionados
Algoritmo aleatorizado HyperLogLog
v t mi

"Algoritmos aleatorios" vuelve a dirigir aquí. No debe confundirse con la aleatoriedad algorítmica .

Un algoritmo aleatorizado es un algoritmo que emplea cierto grado de aleatoriedad como parte de su lógica. El algoritmo normalmente usa bits uniformemente aleatorios como entrada auxiliar para guiar su comportamiento, con la esperanza de lograr un buen rendimiento en el "caso medio" sobre todas las posibles opciones de azar determinadas por los bits aleatorios; por lo tanto, el tiempo de ejecución o la salida (o ambos) son variables aleatorias.

Hay que distinguir entre algoritmos que utilizan la entrada aleatoria para que siempre terminen con la respuesta correcta, pero donde el tiempo de ejecución esperado es finito ( algoritmos de Las Vegas , por ejemplo Quicksort ^[1] ), y algoritmos que tienen la posibilidad de producir un resultado incorrecto ( algoritmos de Monte Carlo , por ejemplo, el algoritmo de Monte Carlo para el problema MFAS ^[2] ) o no produce un resultado al señalar una falla o al no terminar. En algunos casos, los algoritmos probabilísticos son el único medio práctico de resolver un problema. ^[3]

En la práctica común, los algoritmos aleatorios se aproximan utilizando un generador de números pseudoaleatorios en lugar de una fuente verdadera de bits aleatorios; tal implementación puede desviarse del comportamiento teórico esperado.

Motivación

Como ejemplo motivador, considere el problema de encontrar una ' a ' en una matriz de n elementos.

Entrada : una matriz de n ≥2 elementos, en la que la mitad son " a " y la otra mitad son " b ".

Salida : busque una ' a ' en la matriz.

Damos dos versiones del algoritmo, un algoritmo de Las Vegas y un algoritmo de Monte Carlo .

Algoritmo de Las Vegas:

findingA_LV ( matriz  A ,  n ) empezar  la repetición  aleatoriamente  seleccionar  un  elemento  fuera  de  n  elementos .  hasta  'a'  se  encuentran final

Este algoritmo tiene éxito con probabilidad 1. El número de iteraciones varía y puede ser arbitrariamente grande, pero el número esperado de iteraciones es

${\displaystyle \lim _{n\to \infty }\sum _{i=1}^{n}{\frac {i}{2^{i}}}=2}$

Dado que es constante, el tiempo de ejecución esperado en muchas llamadas es . (Ver notación Big O )${\displaystyle \Theta (1)}$

Algoritmo de Monte Carlo:

findingA_MC ( matriz  A ,  n ,  k ) Comienzo  i = 0  repetición  aleatoriamente  seleccionar  un  elemento  fuera  de  n  elementos .  i  =  i  +  1  hasta que  i = k  o  'a'  se  encuentre final

Si se encuentra una ' a ', el algoritmo tiene éxito, de lo contrario, el algoritmo falla. Después de k iteraciones, la probabilidad de encontrar una ' a ' es:

${\displaystyle \Pr[\mathrm {find~a} ]=1-(1/2)^{k}}$

Este algoritmo no garantiza el éxito, pero el tiempo de ejecución está limitado. El número de iteraciones es siempre menor o igual que k. Tomando k como constante, el tiempo de ejecución (esperado y absoluto) es .${\displaystyle \Theta (1)}$

Los algoritmos aleatorios son particularmente útiles cuando se enfrenta a un "adversario" o atacante malintencionado que deliberadamente intenta alimentar una entrada incorrecta al algoritmo (consulte la complejidad del peor de los casos y el análisis competitivo (algoritmo en línea) ), como en el dilema del prisionero . Es por esta razón que la aleatoriedad es omnipresente en la criptografía . En aplicaciones criptográficas, no se pueden utilizar números pseudoaleatorios, ya que el adversario puede predecirlos, haciendo que el algoritmo sea efectivamente determinista. Por lo tanto, se requiere una fuente de números verdaderamente aleatorios o un generador de números pseudoaleatorios criptográficamente seguro . Otra área en la que la aleatoriedad es inherente esComputación cuántica .

En el ejemplo anterior, el algoritmo de Las Vegas siempre genera la respuesta correcta, pero su tiempo de ejecución es una variable aleatoria. Se garantiza que el algoritmo de Monte Carlo (relacionado con el método de simulación de Monte Carlo ) se completará en un período de tiempo que puede estar limitado por una función al tamaño de entrada y su parámetro k , pero permite una pequeña probabilidad de error . Observe que cualquier algoritmo de Las Vegas se puede convertir en un algoritmo de Monte Carlo (a través de la desigualdad de Markov), al hacer que genere una respuesta arbitraria, posiblemente incorrecta, si no se completa dentro de un tiempo especificado. Por el contrario, si existe un procedimiento de verificación eficiente para comprobar si una respuesta es correcta, entonces un algoritmo de Monte Carlo se puede convertir en un algoritmo de Las Vegas ejecutando el algoritmo de Monte Carlo repetidamente hasta que se obtenga una respuesta correcta.

Complejidad computacional

La teoría de la complejidad computacional modela algoritmos aleatorios como máquinas probabilísticas de Turing . Tanto Las Vegas y algoritmos de Monte Carlo se consideran, y varias clases de complejidad se estudian. La clase de complejidad aleatorizada más básica es RP , que es la clase de problemas de decisión para los que existe un algoritmo aleatorizado eficiente (tiempo polinomial) (o máquina de Turing probabilística) que reconoce instancias de NO con absoluta certeza y reconoce instancias de SI con una probabilidad de al menos 1/2. La clase de complemento para RP es co-RP. Clases de problemas que tienen algoritmos (posiblemente no terminales) con tiempo polinomialSe dice que el tiempo medio de ejecución de casos cuya salida es siempre correcta está en ZPP .

La clase de problemas para los que se permite identificar tanto las instancias SÍ como NO con algún error se denomina BPP . Esta clase actúa como el equivalente aleatorio de P , es decir, BPP representa la clase de algoritmos aleatorios eficientes.

Historia

Históricamente, el primer algoritmo aleatorio fue un método desarrollado por Michael O. Rabin para el problema de pares más cercanos en geometría computacional . ^[4] El estudio de algoritmos aleatorios fue impulsado por el descubrimiento en 1977 de una prueba de primalidad aleatoria (es decir, determinar la primordialidad de un número) por Robert M. Solovay y Volker Strassen . Poco después, Michael O. Rabin demostró que la prueba de primalidad de Miller de 1976 se puede convertir en un algoritmo aleatorio. En ese momento, no se conocía ningún algoritmo determinista práctico para la primalidad.

El test de primalidad de Miller-Rabin se basa en una relación binaria entre dos números enteros positivos k y n que puede expresarse diciendo que k "es un testimonio de la compositeness de" n . Se puede demostrar que

• Si hay un testigo de la composición de n , entonces n es compuesto (es decir, n no es primo ), y
• Si n es compuesto, al menos tres cuartas partes de los números naturales menores que n son testigos de su composición, y
• Existe un algoritmo rápido que, dada k y n , comprueba si k es un testimonio de la compositeness de n .

Observe que esto implica que el problema de la primacía está en Co- RP .

Si uno elige aleatoriamente 100 números menos que un número compuesto n , entonces la probabilidad de no encontrar tal "testigo" es (1/4) ^100, por lo que para la mayoría de los propósitos prácticos, esta es una buena prueba de primalidad. Si n es grande, es posible que no haya otra prueba que sea práctica. La probabilidad de error se puede reducir a un grado arbitrario realizando suficientes pruebas independientes.

Por lo tanto, en la práctica, no existe ninguna penalización asociada con la aceptación de una pequeña probabilidad de error, ya que con un poco de cuidado la probabilidad de error puede reducirse astronómicamente. De hecho, a pesar de que desde entonces se ha encontrado una prueba de primalidad determinista en tiempo polinómico (ver prueba de primalidad AKS ), no ha reemplazado las pruebas probabilísticas más antiguas en software criptográfico ni se espera que lo haga en el futuro previsible.

Ejemplos

Clasificación rápida

Quicksort es un algoritmo familiar y de uso común en el que la aleatoriedad puede ser útil. Muchas versiones deterministas de este algoritmo requieren O ( n ² ) tiempo para ordenar n números para alguna clase bien definida de entradas degeneradas (como una matriz ya ordenada), con la clase específica de entradas que generan este comportamiento definido por el protocolo para selección de pivote. Sin embargo, si el algoritmo selecciona elementos pivote de manera uniforme al azar, tiene una probabilidad demostrablemente alta de terminar en un tiempo O ( n  log  n ) independientemente de las características de la entrada.

Construcciones incrementales aleatorias en geometría

En geometría computacional , una técnica estándar para construir una estructura como un casco convexo o triangulación de Delaunay es permutar aleatoriamente los puntos de entrada y luego insertarlos uno por uno en la estructura existente. La aleatorización asegura que el número esperado de cambios en la estructura causados ​​por una inserción sea pequeño, por lo que el tiempo de ejecución esperado del algoritmo puede limitarse desde arriba. Esta técnica se conoce como construcción incremental aleatoria . ^[5]

Corte mínimo

Artículo principal: algoritmo de Karger

Entrada : un gráfico G ( V , E )

Salida : Un corte particionar los vértices en L y R , con el número mínimo de bordes entre L y R .

Recuerde que la contracción de dos nodos, u y v , en un (multi) gráfico produce un nuevo nodo u 'con aristas que son la unión de las aristas incidentes en u o v , excepto en cualquier arista que conecte u y v . La Figura 1 da un ejemplo de contracción de vértice A y B . Después de la contracción, el gráfico resultante puede tener bordes paralelos, pero no contiene bucles propios.

Figura 2: Ejecución exitosa del algoritmo de Karger en un gráfico de 10 vértices. El corte mínimo tiene la talla 3 y está indicado por los colores de los vértices.

Figura 1: Contracción de los vértices A y B

Algoritmo básico de Karger ^[6] :

empezar i = 1 repetir  repetir Tome una arista aleatoria (u, v) ∈ E en G reemplace uyv con la contracción u ' hasta que solo queden 2 nodos obtener el resultado de corte correspondiente C i yo = yo + 1 hasta que yo = m emite el corte mínimo entre C 1 , C 2 , ..., C m .final

En cada ejecución del bucle externo, el algoritmo repite el bucle interno hasta que solo quedan 2 nodos, se obtiene el corte correspondiente. El tiempo de ejecución de una ejecución es , y n denota el número de vértices. Después de m veces ejecuciones del ciclo externo, generamos el corte mínimo entre todos los resultados. La figura 2 da un ejemplo de una ejecución del algoritmo. Después de la ejecución, obtenemos un corte de tamaño 3.${\displaystyle O(n)}$

Lema 1 : Sea k el tamaño de corte mínimo y sea C = { e ₁ , e ₂ , ..., e _k } el corte mínimo. Si, durante la iteración i , ningún borde e ∈ C se selecciona para la contracción, a continuación, C _i = C .

Prueba : si G no está conectado, entonces G se puede dividir en L y R sin ningún borde entre ellos. Entonces, el corte mínimo en un gráfico desconectado es 0. Ahora, suponga que G está conectado. Sea V = L ∪ R la partición de V inducida por C  : C  = {{ u , v } ∈ E  : u ∈ L , v ∈ R } (bien definida ya que G está conectado). Considere una ventaja { u ,v } de C . Inicialmente, u , v son vértices distintos. Mientras tomamos una ventaja , u y v no lo hacen quedan fusionadas.${\displaystyle f\neq e}$ Por lo tanto, al final del algoritmo, tenemos dos nodos compuestos que cubren todo el gráfico, uno que consiste en los vértices de L y la otra que consiste en los vértices de R . Como en la figura 2, el tamaño del corte mínimo es 1 y C = {( A , B )}. Si no seleccionamos ( A , B ) para la contracción, podemos obtener el corte mínimo.

Lema 2 : Si G es un multigraph con p vértices y cuyo corte mínimo tiene tamaño k , entonces G tiene al menos pk / 2 aristas.

Prueba : Debido a que el corte mínimo es k , cada vértice v debe satisfacer el grado ( v ) ≥ k . Por tanto, la suma de los grados es al menos pk . Pero es bien sabido que la suma de los grados de los vértices es igual a 2 | E |. Sigue el lema.

Análisis de algoritmo

La probabilidad de que el algoritmo tenga éxito es 1: la probabilidad de que todos los intentos fracasen. Por independencia, la probabilidad de que todos los intentos fracasen es

$${\displaystyle \prod _{i=1}^{m}\Pr(C_{i}\neq C)=\prod _{i=1}^{m}(1-\Pr(C_{i}=C)).}$$

Por el lema 1, la probabilidad de que C _i = C es la probabilidad de que no se seleccione ningún borde de C durante la iteración i . Considere el bucle interno y deje que G _j denote la gráfica después de j contracciones de aristas, donde j ∈ {0, 1,…, n - 3} . G _j tiene n - j vértices. Usamos la regla de la cadena de posibilidades condicionales . La probabilidad de que la arista elegida en la iteración j no esté en C , dado que ninguna arista de Cha sido elegido antes, es . Tenga en cuenta que G _j todavía tiene un corte mínimo de tamaño k , por lo que según el Lema 2, todavía tiene al menos bordes.${\displaystyle 1-{\frac {k}{|E(G_{j})|}}}$${\displaystyle {\frac {(n-j)k}{2}}}$

Por lo tanto, .${\displaystyle 1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{n-j}}={\frac {n-j-2}{n-j}}}$

Entonces, por la regla de la cadena, la probabilidad de encontrar el corte mínimo C es

$${\displaystyle \Pr[C_{i}=C]\geq \left({\frac {n-2}{n}}\right)\left({\frac {n-3}{n-1}}\right)\left({\frac {n-4}{n-2}}\right)\ldots \left({\frac {3}{5}}\right)\left({\frac {2}{4}}\right)\left({\frac {1}{3}}\right).}$$

La cancelación da . Por tanto, la probabilidad de que el algoritmo tenga éxito es al menos . Porque esto es equivalente a . El algoritmo encuentra el corte mínimo con probabilidad , en el tiempo .${\displaystyle \Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}}$${\displaystyle 1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}}$${\displaystyle m={\frac {n(n-1)}{2}}\ln n}$${\displaystyle 1-{\frac {1}{n}}}$${\displaystyle 1-{\frac {1}{n}}}$${\displaystyle O(mn)=O(n^{3}\log n)}$

Desaleatorización

La aleatoriedad puede verse como un recurso, como el espacio y el tiempo. La desaleatorización es entonces el proceso de eliminar la aleatoriedad (o usar la menor cantidad posible). Actualmente no se sabe si todos los algoritmos pueden desaleatorizarse sin aumentar significativamente su tiempo de ejecución. Por ejemplo, en la complejidad computacional , se desconoce si P = BPP , es decir, no sabemos si podemos tomar un algoritmo aleatorio arbitrario que se ejecuta en tiempo polinomial con una pequeña probabilidad de error y desaleatorizarlo para que se ejecute en tiempo polinomial sin usar la aleatoriedad. .

Hay métodos específicos que se pueden emplear para desaleatorizar algoritmos aleatorizados particulares:

• el método de probabilidades condicionales , y su generalización, estimadores pesimistas
• teoría de la discrepancia (que se utiliza para desaleatorizar algoritmos geométricos)
• la explotación de la independencia limitada en las variables aleatorias utilizadas por el algoritmo, como la independencia por pares utilizada en el hash universal
• el uso de gráficos expansores (o dispersores en general) para amplificar una cantidad limitada de aleatoriedad inicial (este último enfoque también se conoce como generación de bits pseudoaleatorios a partir de una fuente aleatoria y conduce al tema relacionado de la pseudoaleatoriedad)

Donde la aleatoriedad ayuda

Cuando el modelo de cálculo se restringe a las máquinas de Turing , actualmente es una cuestión abierta si la capacidad de realizar elecciones aleatorias permite resolver algunos problemas en tiempo polinomial que no se pueden resolver en tiempo polinomial sin esta capacidad; esta es la cuestión de si P = BPP. Sin embargo, en otros contextos, hay ejemplos específicos de problemas en los que la aleatorización produce mejoras estrictas.

• Basado en el ejemplo motivador inicial: dada una cadena exponencialmente larga de 2 ^k caracteres, mitad a y mitad b, una máquina de acceso aleatorio requiere 2 ^{k −1} búsquedas en el peor de los casos para encontrar el índice de una a ; si se le permite hacer elecciones aleatorias, puede resolver este problema en un número polinomio esperado de búsquedas.
• La forma natural de llevar a cabo un cálculo numérico en sistemas embebidos o sistemas ciberfísicos es proporcionar un resultado que se aproxime al correcto con alta probabilidad (o Computación Probablemente Aproximadamente Correcta (PACC)). El difícil problema asociado con la evaluación de la pérdida por discrepancia entre el cálculo aproximado y el correcto se puede abordar eficazmente recurriendo a la aleatorización ^[7].
• En la complejidad de la comunicación , la igualdad de dos cadenas se puede verificar con cierta confiabilidad utilizando bits de comunicación con un protocolo aleatorio. Cualquier protocolo determinista requiere bits si se defiende contra un oponente fuerte. ^[8]${\displaystyle \log n}$${\displaystyle \Theta (n)}$
• El volumen de un cuerpo convexo se puede estimar mediante un algoritmo aleatorio con precisión arbitraria en tiempo polinomial. ^[9] Bárány y Füredi demostraron que ningún algoritmo determinista puede hacer lo mismo. ^[10] Esto es cierto incondicionalmente, es decir, sin depender de ningún supuesto de la teoría de la complejidad, asumiendo que el cuerpo convexo sólo puede consultarse como una caja negra.
• Un ejemplo más complejo-teórico de un lugar donde la aleatoriedad parece ayudar es la clase IP . La propiedad intelectual se compone de todos los lenguajes que pueden ser aceptados (con alta probabilidad) mediante una interacción polinomialmente larga entre un probador todopoderoso y un verificador que implementa un algoritmo BPP. IP = PSPACE . ^[11] Sin embargo, si se requiere que el verificador sea determinista, entonces IP = NP .
• En una red de reacción química (un conjunto finito de reacciones como A + B → 2C + D que operan en un número finito de moléculas), la capacidad de alcanzar un estado objetivo dado desde un estado inicial es decidible, mientras que incluso se aproxima a la probabilidad de llegar a un estado objetivo determinado (utilizando la probabilidad estándar basada en la concentración para la que se producirá la siguiente reacción) es indecidible. Más específicamente, una máquina de Turing limitada se puede simular con una probabilidad arbitrariamente alta de funcionar correctamente durante todo el tiempo, solo si se usa una red de reacción química aleatoria. Con una red de reacción química no determinista simple (cualquier reacción posible puede ocurrir a continuación), el poder computacional se limita a funciones recursivas primitivas . ^[12]

Ver también

• Análisis probabilístico de algoritmos
• Algoritmo de Atlantic City
• Algoritmo de Montecarlo
• Algoritmo de Las Vegas
• Bogosort
• Principio de decisión diferida
• Algoritmos aleatorios como juegos de suma cero
• Hoja de ruta probabilística
• HyperLogLog
• boceto de conteo mínimo
• algoritmo de conteo aproximado

Notas

1. Hoare, CAR (julio de 1961). "Algoritmo 64: Quicksort". Comun. ACM . 4 (7): 321–. doi : 10.1145 / 366622.366644 . ISSN  0001-0782 .
2. Kudelić, Robert (1 de abril de 2016). "Algoritmo aleatorio de Monte-Carlo para un problema de conjunto de arco de retroalimentación mínima". Soft Computing aplicado . 41 : 235–246. doi : 10.1016 / j.asoc.2015.12.018 .
3. "Al probar la primordialidad de números muy grandes elegidos al azar, la probabilidad de tropezar con un valor que engañe a la prueba de Fermat es menor que la probabilidad de que la radiación cósmica haga que la computadora cometa un error al ejecutar un algoritmo 'correcto'. Considerar que un algoritmo es inadecuado por la primera razón, pero no por la segunda, ilustra la diferencia entre matemáticas e ingeniería ". Hal Abelson y Gerald J. Sussman (1996). Estructura e interpretación de programas informáticos . MIT Press , sección 1.2 .
4. Smid, Michiel. Problemas de punto más cercano en geometría computacional. Max-Planck-Institut für Informatik | año = 1995
5. Seidel R. Análisis hacia atrás de algoritmos geométricos aleatorios .
6. AA Tsay, WS Lovejoy, David R. Karger, Muestreo aleatorio en problemas de diseño de corte, flujo y red , Matemáticas de la investigación de operaciones, 24 (2): 383-413, 1999.
7. Alippi, Cesare (2014), Inteligencia para sistemas integrados , Springer, ISBN 978-3-319-05278-6.
8. Kushilevitz, Eyal; Nisan, Noam (2006), Complejidad de la comunicación , Cambridge University Press, ISBN 9780521029834. Para el límite inferior determinista, véase la p. 11; para el límite superior logarítmico aleatorizado, véanse las págs. 31-32.
9. Dyer, M .; Frieze, A .; Kannan, R. (1991), "Un algoritmo de tiempo polinómico aleatorio para aproximar el volumen de cuerpos convexos" (PDF) , Journal of the ACM , 38 (1): 1-17, doi : 10.1145 / 102782.102783
10. Füredi, Z .; Bárány, I. (1986), "Calcular el volumen es difícil", Proc. XVIII Simposio ACM sobre Teoría de la Computación (Berkeley, California, 28 al 30 de mayo de 1986) (PDF) , Nueva York, NY: ACM, págs. 442–447, CiteSeerX 10.1.1.726.9448 , doi : 10.1145 / 12130.12176 , ISBN   0-89791-193-8
11. Shamir, A. (1992), "IP = PSPACE", Journal of the ACM , 39 (4): 869–877, doi : 10.1145 / 146585.146609
12. Cook, Matthew ; Soloveichik, David; Winfree, Erik ; Bruck, Jehoshua (2009), "Programabilidad de redes de reacción química", en Condon, Anne ; Harel, David ; Kok, Joost N .; Salomaa, Arto ; Winfree, Erik (eds.), Bioprocesos algorítmicos (PDF) , Serie de computación natural, Springer-Verlag, págs. 543–584, doi : 10.1007 / 978-3-540-88869-7_27 .

Referencias

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , segunda edición. MIT Press y McGraw-Hill, 1990. ISBN 0-262-03293-7 . Capítulo 5: Análisis probabilístico y algoritmos aleatorios, págs. 91-122. 
• Dirk Draheim. " Semántica del cálculo lambda probabilístico tipificado (semántica de la cadena de Markov, comportamiento de terminación y semántica denotacional) " . Springer, 2017.
• Jon Kleinberg y Éva Tardos . Diseño de algoritmos . Capítulo 13: "Algoritmos aleatorios".
• Fallis, D. (2000). "La fiabilidad de los algoritmos aleatorios". The British Journal for the Philosophy of Science . 51 (2): 255-271. doi : 10.1093 / bjps / 51.2.255 .
• M. Mitzenmacher y E. Upfal . Probabilidad y computación: algoritmos aleatorios y análisis probabilístico . Cambridge University Press, Nueva York (NY), 2005.
• Rajeev Motwani y P. Raghavan. Algoritmos aleatorios . Cambridge University Press, Nueva York (NY), 1995.
• Rajeev Motwani y P. Raghavan. Algoritmos aleatorios . Una encuesta sobre algoritmos aleatorios.
• Christos Papadimitriou (1993), Computational Complexity (1a ed.), Addison Wesley, ISBN 978-0-201-53082-7 Capítulo 11: Computación aleatoria, págs. 241–278.
• Rabin, Michael O. (1980). "Algoritmo probabilístico para probar la primalidad" . Revista de teoría de números . 12 : 128-138. doi : 10.1016 / 0022-314X (80) 90084-0 .
• AA Tsay, WS Lovejoy, David R. Karger, Muestreo aleatorio en problemas de corte, flujo y diseño de redes , Matemáticas de la investigación de operaciones, 24 (2): 383–413, 1999.