Algoritmos Aleatorizados

Los algoritmos aleatorizados toman decisiones aleatorias durante la ejecución para obtener eficiencia, simplicidad o robustez, con un rendimiento y una corrección expresados como garantías probabilísticas en lugar de certezas en el peor de los casos.

Definition

Un algoritmo aleatorizado es un algoritmo que utiliza una fuente de bits aleatorios para tomar algunas de sus decisiones, de modo que su tiempo de ejecución, su salida o ambos son variables aleatorias analizadas por su expectativa o distribución de probabilidad.

Scope

Este tema abarca los algoritmos que utilizan la aleatoriedad como un recurso computacional: el modelo de Las Vegas (siempre correcto, tiempo de ejecución aleatorizado) y el modelo de Monte Carlo (tiempo de ejecución fijo, probabilidad de error acotada), ejemplos canónicos como el quicksort aleatorizado, la selección aleatorizada, las pruebas de primalidad y las estructuras de datos aleatorizadas como las listas de salto (skip lists), y las herramientas de análisis probabilístico (expectativa, varianza, desigualdades de cola y concentración) utilizadas para razonar sobre ellos.

Core questions

• ¿Cómo puede la introducción de la aleatoriedad hacer que un algoritmo sea más rápido o más simple que cualquier otro determinista conocido?
• ¿Cuál es la distinción entre los algoritmos de Las Vegas y Monte Carlo?
• ¿Cómo se analiza el tiempo de ejecución esperado o la probabilidad de error?
• ¿Cómo limitan las desigualdades de concentración la probabilidad de resultados adversos?
• ¿Cómo se puede reducir el error de un algoritmo de Monte Carlo mediante la repetición?

Key concepts

• bits aleatorios como recurso
• algoritmo de Las Vegas
• algoritmo de Monte Carlo
• tiempo de ejecución esperado
• probabilidad de error y amplificación
• desigualdades de concentración
• quicksort aleatorizado
• listas de salto

Key theories

Las Vegas versus Monte Carlo

Los algoritmos de Las Vegas siempre producen un resultado correcto, pero tienen un tiempo de ejecución aleatorizado (analizado en expectativa), mientras que los algoritmos de Monte Carlo se ejecutan en un tiempo fijo, pero pueden producir un resultado incorrecto con una probabilidad acotada, que la repetición puede reducir.

Pruebas de primalidad probabilísticas

Las pruebas aleatorizadas, como la de Miller-Rabin, certifican la primalidad con alta confianza en tiempo polinomial al verificar testigos aleatorios; un número compuesto es expuesto por la mayoría de los testigos, por lo que las pruebas repetidas hacen que la probabilidad de error sea insignificante.

Clinical relevance

Los algoritmos aleatorizados se implementan ampliamente: la prueba de primalidad de Miller-Rabin sustenta la criptografía de clave pública, el hashing aleatorizado y el equilibrio de carga mantienen la eficiencia de los sistemas distribuidos, el quicksort y el quickselect aleatorizados ofrecen un rendimiento esperado robusto, y el muestreo y el esbozo aleatorizados permiten el procesamiento de flujos de datos masivos.

History

Los algoritmos probabilísticos cobraron importancia en la década de 1970 con las pruebas de primalidad de Solovay-Strassen y Miller-Rabin, que hicieron de la aleatoriedad una herramienta computacional respetable. Las décadas de 1980 y 1990 vieron estructuras de datos aleatorizadas (listas de salto, treaps), algoritmos gráficos y geométricos aleatorizados, y la teoría sistemática codificada en el libro de texto de Motwani y Raghavan de 1995.

Key figures

• Michael Rabin
• Robert Solovay
• Volker Strassen
• Rajeev Motwani
• Prabhakar Raghavan

Seminal works

• motwani1995
• rabin1980
• cormen2009

Frequently asked questions

¿Cómo se puede confiar en un algoritmo de Monte Carlo si puede ser incorrecto?

Su probabilidad de error está acotada y es conocida, y para los algoritmos de error unilateral se puede hacer arbitrariamente pequeña ejecutando el algoritmo varias veces con aleatoriedad independiente. Después de suficientes repeticiones, la probabilidad de una respuesta incorrecta es mucho menor que la probabilidad de un fallo de hardware.

¿Por qué se prefiere el quicksort aleatorizado al quicksort determinista?

El quicksort determinista puede alcanzar su peor caso de O(n al cuadrado) en entradas adversas o ya ordenadas debido a malas elecciones de pivote. La elección aleatoria de pivotes hace que ese peor caso sea extremadamente improbable, independientemente de la entrada, lo que proporciona un rendimiento esperado de O(n log n) en cada entrada.