## 1.4 ANÁLISIS PROBABILÍSTICO Y ALGORITMOS ALEATORIZADOS

Un algoritmo probabilístico es un algoritmo que contiene entre sus operaciones elementales la generación de números aleatorios. Dado que no es un proceso determinístico, algunos autores no los consideran verdaderos “algoritmos”. Su principal característica es que el mismo algoritmo aplicado a la misma instancia varias veces puede dar distintos resultados, y por lo tanto necesitar distinta cantidad de tiempo y espacio. Esto permite que alguna ejecución de un algoritmo probabilístico devuelva un resultado incorrecto, o cicle indefinidamente, siempre y cuando lo haga con una probabilidad baja. En muchos casos se puede aumentar la confianza en el resultado ejecutando el algoritmo varias veces

El análisis de los algoritmos probabilísticos es frecuentemente muy complejo, y requiere herramientas de probabilidad y estadística. Hay que distinguir entre:

- El tiempo promedio de un algoritmo determinístico es el promedio del tiempo que toma el algoritmo cuando cada instancia de un mismo tamaño es igualmente probable.
- El tiempo esperado de un algoritmo probabilístico se define para cada instancia particular: es el tiempo medio que llevaría resolver la instancia varias veces. No depende de ninguna distribución de probabilidades de las instancias; sí de la distribución de probabilidades de los números aleatorios generados.

Tiene sentido entonces hablar del tiempo esperado promedio, y del tiempo esperado en el peor caso de un algoritmo probabilístico para un dado tamaño de instancias.

Clasificación

De acuerdo al resultado que obtienen, los algoritmos probabilísticos se clasifican en:

- Numéricos: dan como resultado un rango de confianza del valor pretendido. Ejemplo: “el valor buscado está en el intervalo [x,y]”. Dos aplicaciones muy importantes son las encuestas y la simulación.
- Monte Carlo: dan como resultado el valor correcto con una probabilidad alta, pero pueden a veces dar valores equivocados. Se puede reducir la incertidumbre ejecutando varias veces el algoritmo.
- Las Vegas: nunca dan un resultado incorrecto, pero a veces pueden detectar que el resultado es imposible de obtener en esa ejecución y devuelven un mensaje de error.

Ejemplo

Para ilustrar esta clasificación, si se tuviera un algoritmo de cada clase que compute el año del descubrimiento de América los resultados en distintas llamadas podrían ser:

Numérico: “entre 1490 y 1500 con 99% de probabilidad”, “entre 1485 y 1495 con 90% de probabilidad”, “entre 1480 y 1490 con 95% de probabilidad”.

Monte Carlo: 1492,1492,1492,1491,1492,32134,1492,1492.

###