Algoritmos aleatorizados

Quicksort con el primer elemento como pivote tiene un peor caso cuadrático que se dispara justamente con arreglos ya ordenados. Elegir el pivote al azar no mejora el peor caso teórico: lo vuelve improbable para cualquier entrada. El azar no hace al algoritmo más rápido, le saca el control al adversario.

Las Vegas y Monte Carlo

Hay dos familias. Los Las Vegas siempre dan la respuesta correcta y su tiempo es variable: quicksort aleatorizado es el ejemplo típico, siempre ordena bien y en promedio tarda $n\log n$.

Los Monte Carlo tardan un tiempo acotado pero pueden equivocarse con probabilidad chica. La diferencia es qué se deja que varíe: el tiempo o la certeza. Un Monte Carlo con error de un lado —que nunca dice que sí cuando es no— es mucho más útil de lo que parece.

Repetir hasta que el error sea despreciable

Lo que vuelve práctico a Monte Carlo es que el error se puede achicar por repetición. Si cada corrida se equivoca con probabilidad a lo sumo $1/2$ y los errores son independientes, $k$ corridas dejan la probabilidad en $2^{-k}$.

Con cuarenta repeticiones el error queda por debajo de un billonésimo: mucho menos probable que

un error de hardware. En ese punto, “puede fallar” deja de ser una objeción práctica.

Miller-Rabin, el caso emblemático

El caso emblemático es la primalidad. Miller-Rabin elige bases al azar y verifica una identidad que todo primo cumple; si falla, el número es compuesto con certeza. Si pasa todas las pruebas, es primo con probabilidad altísima.

Es un Monte Carlo con error de un lado, y es lo que corre cada vez que se genera una clave RSA. Existe un test determinístico polinomial —AKS, de 2002—, pero es tan lento que nadie lo usa: acá el aleatorizado no es un atajo, es la herramienta correcta.

Selección, hashing y estructuras

Hay más. La selección del $k$-ésimo elemento con pivote aleatorio corre en tiempo lineal esperado. El hashing universal elige la función de hash al azar entre una familia, y con eso ninguna entrada particular puede provocar colisiones sistemáticas.

El algoritmo de Karger para corte mínimo contrae aristas al azar: falla seguido, pero repetirlo suficientes veces da la respuesta con alta probabilidad, y es muchísimo más simple que las alternativas determinísticas.

El azar como defensa contra el peor caso

La aleatorización también es una defensa. Un atacante que conozca el algoritmo determinístico puede construir entradas que provoquen el peor caso: claves que colisionen todas en la misma posición de una tabla hash, y con eso un servicio caído por agotamiento de CPU.

Con una semilla aleatoria por proceso, esas entradas dejan de ser reproducibles. Es el motivo por el que los lenguajes modernos aleatorizan el hashing por defecto.

Todo depende del generador

La letra chica es el generador. Todo el análisis asume aleatoriedad genuina; un generador predecible reintroduce el problema que se quería evitar, y en un contexto de seguridad hace falta uno criptográfico, no el del lenguaje.

El otro costo es la reproducibilidad: dos corridas pueden diferir, lo que complica depurar y testear. La práctica habitual es fijar la semilla en desarrollo y dejarla aleatoria en producción.

Dónde el azar es la respuesta correcta

Cierre

El azar compra independencia de la entrada. Las Vegas varía el tiempo y nunca se equivoca; Monte Carlo acota el tiempo y se equivoca con probabilidad que se achica repitiendo. El análisis vale lo que valga el generador, y la reproducibilidad es lo que se paga.