Un algoritmo de este tipo no especula con el resultado, sino que determina los recursos a utilizar en su computación.

De la misma manera que el método de Montecarlo, la probabilidad de encontrar una solución correcta aumenta con el tiempo empleado en obtenerla y el número de muestreos utilizado. Un algoritmo tipo Las Vegas se utiliza sobre todo en problemas NP-completos, que serían intratables con métodos determinísticos.

Existe un riesgo de no encontrar solución debido a que se hacen elecciones de rutas aleatorias que pueden no llevar a ningún sitio. El objetivo es minimizar la probabilidad de no encontrar la solución, tomando decisiones aleatorias con inteligencia, pero minimizando también el tiempo de ejecución al aplicarse sobre el espacio de información aleatoria.

La clase de complejidad de los problemas de decisión de estos algoritmos con ejecución polinómica es ZPP.

${\displaystyle ZPP=RP*no-RP}$ 

Su esquema de implementación se parece al de los algoritmos de Montecarlo, pero se diferencian de ellos en que incluyen una variable booleana para saber si se ha encontrado la solución correcta.

En informática, un algoritmo de Las Vegas es un algoritmo aleatorio que siempre da resultados correctos, es decir, que siempre produce el resultado correcto o informa acerca del fallo (es decir, que no se ha hallado la solución buscada). Sin embargo, el tiempo de ejecución de un algoritmo de Las Vegas difiere dependiendo de la entrada. Su definición usual incluye la restricción de que el tiempo de ejecución esperado sea finito, donde la expectativa se lleva a cabo sobre el espacio de información aleatoria, o entropía, usada en el algoritmo. Una definición alternativa requiere que un algoritmo de Las Vegas siempre termine (porque se trata de un método efectivo), pero puede dar como resultado un símbolo que no forma parte del espacio de la solución, para indicar el fallo en encontrarla.^[1]​ La naturaleza de los algoritmos de Las Vegas los hace adecuados en situaciones donde el número de posibles soluciones es limitado, y donde verificar la corrección de una solución candidata es relativamente fácil, mientras que encontrar una solución es complejo.

Los métodos de búsqueda sistemática para problemas computacionalmente complejos, como algunas variantes del algoritmo de Davis-Putnam para la satisfacibilidad proposicional (SAT), también utilizan decisiones no deterministas y, por lo tanto, pueden considerarse algoritmos de Las Vegas.^[2]​

Los algoritmos de Las Vegas fueron introducidos por László Babai en 1979, en el contexto del problema de isomorfismo de grafos, como un dual de los algoritmos del tipo del método de Monte Carlo.^[3]​ Babai^[4]​ introdujo el término "algoritmo de Las Vegas" junto con un ejemplo de lanzamientos de moneda: el algoritmo depende de una serie de lanzamientos de moneda independientes y existe una pequeña probabilidad de fallo (ningún resultado). Sin embargo, a diferencia de los algoritmos de Monte Carlo, el algoritmo de Las Vegas puede garantizar la exactitud de cualquier resultado obtenido.

// Algoritmo de Las Vegas, suponiendo que A es una matriz de longitud n.
n = A.length
repeat:
    k = RandInt(n)
    if A[k] == 1,
        return k;

Como se mencionó anteriormente, los algoritmos de Las Vegas siempre devuelven resultados correctos. El código anterior ilustra esta propiedad. Una variable k se genera aleatoriamente; después de generar k, k se utiliza para indexar la matriz A. Si este índice contiene el valor 1, se devuelve k; de lo contrario, el algoritmo repite este proceso hasta encontrar 1. Aunque este algoritmo de Las Vegas garantiza encontrar la respuesta correcta, no tiene un tiempo de ejecución fijo; debido a la aleatorización (en la línea 4 del código anterior), es posible que transcurra un tiempo arbitrario antes de que el algoritmo finalice.

En esta sección se describen las condiciones que caracterizan a un algoritmo de tipo de Las Vegas.

Un algoritmo A es un algoritmo de Las Vegas para la clase de problema X, si^[5]​

1. Siempre que para una instancia dada del problema x∈X devuelva una solución s, se garantiza que s sea una solución válida de x
2. En cada instancia dada x, el tiempo de ejecución de A es una variable aleatoria RT_A,x

Existen tres nociones de completitud para los algoritmos de Las Vegas:

• Se puede garantizar que los algoritmos de Las Vegas completos solucienen cada problema resoluble dentro del tiempo de ejecución tmax,, donde tmax es una constante dependiente de la instancia.

Sea P(RT_A,x = t) la probabilidad de que A encuentre una solución para una instancia resoluble x en un tiempo t. Entonces, A es completo exactamente si para cada x existe algún tmax tal que P(RT_A,x = t_max) = 1.

• Los algoritmos de Las Vegas aproximadamente completos resuelven cada problema con una probabilidad que converge a 1 a medida que el tiempo de ejecución se acerca al infinito. Por lo tanto, A es aproximadamente completo si, para cada instancia x, lim_t→∞ P(RT_A,x = t) = 1.
• Los algoritmos de Las Vegas esencialmente incompletos son aquellos que no son aproximadamente completos.

La completitud aproximada es principalmente de interés teórico, ya que los plazos para encontrar soluciones suelen ser demasiado largos para su uso práctico.

Los algoritmos de Las Vegas tienen diferentes criterios de evaluación según el problema. Estos criterios se dividen en tres categorías con diferentes límites de tiempo, ya que los algoritmos de Las Vegas no tienen una complejidad temporal definida. A continuación, se presentan algunos posibles escenarios de aplicación:

• Tipo 1: No hay límites de tiempo, lo que significa que el algoritmo se ejecuta hasta encontrar la solución.
• Tipo 2: Hay un límite de tiempo t_max para encontrar el resultado.
• Tipo 3: La utilidad de una solución está determinada por el tiempo necesario para encontrarla.

(Los tipos 1 y 2 son casos especiales del tipo 3).

Para el tipo 1, donde no hay límite de tiempo, el tiempo de ejecución promedio puede representar el comportamiento en tiempo de ejecución. No ocurre lo mismo para el tipo 2.

Aquí, P(RT = t_max), que es la probabilidad de encontrar una solución dentro del tiempo, describe su comportamiento en tiempo de ejecución.

En el caso del Tipo 3, su comportamiento en tiempo de ejecución solo puede representarse mediante la función de distribución de tiempo de ejecución rtd: R → [0,1], definida como rtd(t) = P(RT = t) o su aproximación.

La distribución de tiempo de ejecución (RTD) es la forma distintiva de describir el comportamiento en tiempo de ejecución de un algoritmo de Las Vegas.

Con estos datos, se pueden obtener fácilmente otros criterios como el tiempo de ejecución medio, la desviación estándar, la mediana, los percentiles o las probabilidades de éxito P(RT = t) para límites de tiempo arbitrarios t.

Los algoritmos Las Vegas surgen con frecuencia en problemas de búsqueda, como es el caso de alguien que busca una información en línea podría requerir la información deseada en sitios web relacionados. La complejidad temporal varía, por lo tanto, desde tener suerte y encontrar el contenido inmediatamente, hasta tener mala suerte y dedicar mucho tiempo hasta encontrarlo. Una vez encontrado el sitio web correcto, no hay posibilidad de error.^[6]​

INPUT: 
    # A es una matriz de n elementos
def randomized_quicksort(A):
    if n == 1:
        return A  # A está ordenada
    else:
        i = random.randrange(1, n)  # Will take a random number in the range 1~n
        X = A[i]  # El elemento pivote
    """Repartir A en los elementos <x, x y >x #, como se muestra en la figura anterior.
Ejecutar Quicksort en A[1 a i-1] y A[i+1 a n].
Combinar las respuestas para obtener una matriz ordenada."""

Un ejemplo sencillo es el quicksort aleatorio, donde el pivote se elige aleatoriamente y divide los elementos en tres particiones: elementos menores que el pivote, elementos iguales al pivote y elementos mayores que el pivote. El ordenamiento rápido siempre genera la solución, que en este caso es la matriz ordenada. Desafortunadamente, la complejidad temporal no es tan obvia. Resulta que el tiempo de ejecución depende del elemento que se elija como pivote.

• El peor caso T(n²) se produce cuando el pivote es el elemento más pequeño o el más grande.

${\displaystyle T(n)=T(0)+T(n-1)+\Theta (n)}$ 

${\displaystyle T(n)=\Theta (1)+T(n-1)+\Theta (n)}$ 

${\displaystyle T(n)=T(n-1)+\Theta (n)}$ 

${\displaystyle T(n)=\Theta (n^{2})}$ 

• Sin embargo, mediante la aleatorización, donde el pivote se selecciona aleatoriamente y siempre tendrá un valor exactamente situado en la media, el QuickSort se puede realizar en T(nlogn).

${\displaystyle T(n)\leq 2*T(n/2)+\Theta (n)}$ 

${\displaystyle T(n)=\Theta (n\log(n))}$ 

El tiempo de ejecución del quicksort depende en gran medida de la precisión con la que se seleccione el pivote. Si un valor del pivote es demasiado grande o demasiado pequeño, la partición estará desequilibrada, lo que resulta en una baja eficiencia de ejecución. Sin embargo, si el valor del pivote está cerca del centro de la matriz, la división estará razonablemente equilibrada, lo que resulta en un tiempo de ejecución más rápido. Dado que el pivote se selecciona aleatoriamente, el tiempo de ejecución será bueno la mayor parte del tiempo y malo ocasionalmente.

En el caso del promedio, es difícil de determinar, ya que el análisis no depende de la distribución de entrada, sino de las elecciones aleatorias que realiza el algoritmo. El promedio del quicksort se calcula sobre todas las posibles elecciones aleatorias que el algoritmo podría realizar al elegir el pivote.

Aunque el tiempo de ejecución en el peor de los casos es T(n²), el tiempo de ejecución en el caso promedio es T(nlogn). Resulta que el peor de los casos no ocurre con frecuencia. Para valores grandes de n, el tiempo de ejecución es T(nlogn) con una alta probabilidad.

Obsérvese que la probabilidad de que el pivote sea el elemento de valor medio cada vez es de una entre n números, lo cual es muy poco común. Sin embargo, el tiempo de ejecución sigue siendo el mismo cuando la división es del 10% al 90% en lugar del 50% al 50%, ya que la profundidad del árbol de recursión seguirá siendo O(logn), con O(n) veces tomadas en cada nivel de recursión.

El problema de las ocho reinas suele resolverse con un algoritmo de retroceso. Sin embargo, se puede aplicar un algoritmo de Las Vegas, y de hecho, es más eficiente que el algoritmo de retroceso.

Consiste en colocar 8 reinas en un tablero de ajedrez, de manera que ninguna ataque a otra. Debe recordarse que una reina ataca a otras piezas en la misma fila, columna y diagonales.

Supóngase que k filas, 0 ≤ k ≤ 8, están ocupadas con éxito por reinas.

Si k = 8, se detiene con éxito. De lo contrario, procede a ocupar la fila k + 1.

Calcula todas las posiciones en esta fila no atacadas por reinas existentes. Si no hay ninguna, falla. De lo contrario, elige una al azar, incrementa k y repite.

Debe tenerse en cuenta que el algoritmo simplemente falla si no se puede colocar una reina. Sin embargo, el proceso puede repetirse y cada vez generará una disposición diferente.^[7]​

La clase de complejidad de los problemas de decisión que tienen algoritmos de Las Vegas con tiempo de ejecución polinómico esperado es tiempo polinómico probabilístico de error cero (ZPP).

Resulta que: ${\displaystyle {\textsf {ZPP}}={\textsf {RP}}\cap {\textsf {co-RP}}}$ 

lo cual está íntimamente relacionado con la forma en que a veces se construyen los algoritmos de Las Vegas. La clase RP comprende todos los problemas de decisión para los que existe un algoritmo aleatorio de tiempo polinómico que siempre responde correctamente cuando la respuesta correcta es no, pero que puede equivocarse con una probabilidad acotada de uno cuando la respuesta es sí. Cuando dicho algoritmo existe tanto para un problema como para su complemento (con las respuestas sí y no intercambiadas), ambos algoritmos pueden ejecutarse de forma simultánea y repetida: cada uno se ejecuta durante un número constante de pasos, turnándose, hasta que uno de ellos devuelva una respuesta definitiva. Esta es la forma estándar de construir un algoritmo de Las Vegas que se ejecuta en el tiempo polinómico esperado. Cabe destacar que, en general, no existe un límite superior en el peor de los casos para el tiempo de ejecución de un algoritmo de Las Vegas.

Para que un algoritmo de Las Vegas sea óptimo, el tiempo de ejecución esperado debe minimizarse. Esto se puede lograr mediante:

1. El algoritmo de Las Vegas A(x) se ejecuta repetidamente durante un número t₁ de pasos. Si A(x) se detiene durante la ejecución, A(x) se completa; de lo contrario, se repite el proceso desde el principio para otros t₂ pasos, y así sucesivamente.
2. Diseño de una estrategia óptima entre todas las estrategias para A(x), dada la información completa sobre la distribución de T_A(x).

La existencia de la estrategia óptima puede ser una observación teórica fascinante. Sin embargo, no es práctica en la vida real porque no es fácil encontrar la información de la distribución de T_A(x). Además, no es necesario ejecutar el experimento repetidamente para obtener información sobre la distribución, ya que la mayoría de las veces, la respuesta solo se necesita una vez para cualquier x.^[8]​

Los algoritmos de Las Vegas se pueden contrastar con los algoritmos de Monte Carlo, en los que los recursos utilizados están limitados, pero la respuesta puede ser incorrecta con un valor de probabilidad determinado (normalmente pequeño). Un algoritmo de Las Vegas se puede convertir en un algoritmo de Monte Carlo ejecutándolo durante un tiempo determinado y generando una respuesta aleatoria cuando no termina. Mediante la aplicación de la desigualdad de Markov, se puede establecer el límite de probabilidad de que el algoritmo de Las Vegas supere el límite establecido.

A continuación se muestra una tabla que compara los algoritmos de Las Vegas y de Monte Carlo:^[9]​

Si se dispone de un método determinista para comprobar la corrección, es posible convertir un algoritmo de Monte Carlo en un algoritmo de Las Vegas. Sin embargo, es difícil convertir un algoritmo de Monte Carlo en un algoritmo de Las Vegas sin una forma de probarlo. Por otro lado, cambiar un algoritmo de Las Vegas a un algoritmo de Monte Carlo es sencillo. Esto se puede lograr ejecutando un algoritmo de Las Vegas durante un período específico, determinado por el parámetro de confianza. Si el algoritmo encuentra la solución dentro del tiempo establecido, se considera un éxito; si no, el resultado puede ser simplemente lo siento.

Este es un ejemplo para comparar los algoritmos de Las Vegas y de Monte Carlo:^[10]​

Supóngase que existe una matriz con una longitud n par. La mitad de las entradas de la matriz son 0 y la otra mitad son 1. El objetivo es encontrar un índice que contenga un 1.

// A es una matriz de longitud n.
n = A.length

// Algoritmo de Las Vegas
repeat:
    k = RandInt(n);
    if A[k] == 1,
        return k;
        
// Algoritmo de Monte Carlo
repeat 300 times:
    k = RandInt(n);
    if A[k] == 1,
        return k;
return "Fallo";

Dado que el algoritmo de Las Vegas no finaliza hasta encontrar un 1 en la matriz, no se juega con la exactitud, sino con el tiempo de ejecución. Por otro lado, el algoritmo de Monte Carlo se ejecuta 300 veces, lo que significa que es imposible saber si encontrará un 1 en la matriz dentro de 300 bucles hasta que realmente ejecute el código. Podría encontrar la solución o no. Por lo tanto, a diferencia del algoritmo de Las Vegas, el de Monte Carlo no juega con el tiempo de ejecución, sino con la corrección del resultado.

• Método de Montecarlo
• Algoritmo de Montecarlo
• Algoritmo de Atlantic City
• Aleatoriedad