La característica principal de los algoritmos probabilistas es que un mismo algoritmo se puede comportar de forma distinta cuando se aplica dos veces a un mismo caso. Su tiempo de ejecución e incluso el resultado obtenido, pueden variar considerablemente entre usos consecutivos.
Esto se puede explorar de muchas maneras. Por ejemplo, no se permite que un algoritmo determinista pierda el control(bucle infinito, división por cero) porque si hace esto en un caso dado, entonces nunca se podrá resolver ese caso con ese algoritmo. Por contraste, este comportamiento es admisible para un algoritmo probabilístico siempre y cuando se produzca una probabilidad razonablemente pequeña en cualquier caso dado: si el algoritmo se atasca, basta con reiniciarlo para ese mismo caso y dispondremos de una nueva probabilidad de éxito. Otra ventaja de este enfoque es que si hay más de una respuesta correcta, se pueden obtener varias diferentes ejecutando el algoritmo probabilista más de una vez.
Hay muchos algoritmos probabilísticos que dan respuestas probabilistas, esto es, que no son necesariamente exactas. Hay aplicaciones críticas para las cuales no se pueden admitir esas respuestas inciertas. Sin embargo, es frecuente que la probabilidad de error se pueda
hacer descender por debajo de la de un error del equipo físico durante el significativamente mayor tiempo que el necesario para calcular la respuesta de forma determinista. Por tanto, paradójicamente, puede suceder que la respuesta incierta dada por un algoritmo probabilista no sólo se obtenga más deprisa, sino que además podamos confiar más en ella que la respuesta “garantizada” que se obtiene mediante ningún algoritmo(determinista o probabilista) que se pueda dar la respuesta con certeza en una cantidad razonable de tiempo(incluso ignorando posibles errores del equipo físico), y sin embargo hay algoritmos probabilísticos que pueden resolver rápidamente el problema si se admite una pequeña probabilidad de error.
Se pueden distinguir fundamentalmente cuatro grandes categorías.
Algoritmos numéricos
Devuelven una aproximación al resultado, frecuentemente en forma de intervalo. Son útiles cuando la solución exacta es demasiado costosa (o directamente imposible de calcular, como por ejemplo, para números irracionales) y una aproximación es lo suficientemente buena. Considérese que se desea calcular el resultado de una complicada integral de varias dimensiones. Tal vez sólo se necesite una precisión de cuatro decimales, aunque la solución exacta conste de varias decenas de los mismos. Este tipo de algoritmos suelen ofrecer resultados más precisos cuanto mayor tiempo se dedica a su cálculo. El margen de error suele ser inversamente proporcional a la raíz cuadrada de la cantidad de trabajo que se haya efectuado, así que se necesita cien veces más trabajo para obtener un dígito de precisión adicional
Algoritmos Montecarlo
Existen problemas para los cuales no se conoce ningún algoritmo eficiente(probabilista o determinista) que sea capaz de obtener una solución correcta en todas las ocasiones. Los algoritmos Monte Carlo ocasionalmente cometen un error, pero siempre devuelven una solución aunque esta a veces no sea correcta. Son útiles cuando una aproximación no es suficiente (por ejemplo, en un problema de decisión). Cuentan con el inconveniente de no saber con exactitud si la respuesta es acertada, pues sólo existe una cierta probabilidad de éxito. Cuantas más veces se ejecute, más seguro se estará de la corrección de la solución.
Algoritmos Las Vegas
Los algoritmos de las vegas toman decisiones probabilistas como ayuda para guiarse más rápidamente hacia una solución correcta. Similares a los de Montecarlo pero que nunca devuelven una solución errónea, con el inconveniente de que pueden no terminar o devolver solución. Esto garantiza que la respuesta sea la buena, pero no garantiza que el algoritmo funcione. Como en los casos anteriores, cuanto mayor es el tiempo dedicado al cálculo, más fiable es la solución. No debe confundirse este tipo de algoritmos con aquellos deterministas, como el simplex en programación lineal, que son muy eficientes para la mayoría de los posibles datos de entrada pero desastrosos para unos pocos. Nótese que dichos algoritmos siempre devuelven una solución correcta.
Algoritmos Sherwood
Devuelven siempre una respuesta, la cual es forzosamente exacta. Aparecen cuando un algoritmo determinista conocido es más rápido en el caso medio que en el peor. El uso del azar permite reducir, e incluso eliminar, la diferencia entre buenos y malos ejemplares.