Algoritmos Probabilísticos

En muchos casos, al introducir elecciones aleatorias en un algoritmo se pueden obtener mejores rendimientos que al aplicar el algoritmo determinístico puro.

Un algoritmo tipo Montecarlo asegura un tiempo fijo de ejecución, pero no está garantizado que la respuesta sea correcta, aunque lo puede ser con alta probabilidad.

Un algoritmo tipo Las Vegas siempre entrega la respuesta correcta, pero no garantiza el tiempo total de ejecución, aunque con alta probabilidad éste será bajo.

Ejemplo: algoritmo tipo Montecarlo para verificar la multiplicación de dos matrices.

Sean A, B, C matrices de N x N. Se desea chequear si . Determinísticamente, esto toma tiempo O(n³) usando el algoritmo estándar.

Probabilísticamente, se puede chequear si en tiempo O(n²) con baja probabilidad de error. El algoritmo es el siguiente:

for (i=1; i<=k; i++)
{
  Generar un vector aleatorio de N x 1 con entradas en {-1, 1};
  if (A*(Bx) != Cx)
    return false; // A*B != C
}
return true; // A*B = C con alta probabilidad

La complejidad de este algoritmo es . A continuación se muestra que para este algoritmo:

Sea . Si para algún i, j, entonces , donde x' es el vector donde se cambia x_j por -x_j. Por lo tanto, en cada iteración del algoritmo se tiene que , y dado que se realizan k iteraciones se tiene que .

Ejemplo: algoritmo tipo Las Vegas para colorear conjuntos.

Sean k conjuntos C₁, ..., C_k con r elementos cada uno (no disjuntos), y . Se pide colorear los elementos de color rojo o azul, tal que ningún C_i sea homogeneo.

Algoritmo:

while (true)
{
  Colorear los elementos aleatoriamente;
  if (ningún Ci es homogeneo)
    break;
}

¿Cuántas veces es necesario repetir el ciclo para obtener una respuesta?

Pr(C_i homogeneo) = Pr(todos los elementos de C_i rojos) + Pr(todos los elementos de C_i azules) = 1/2^r + 1/2^r = 1/2^r-1

=> Pr(algún C_i homogeneo) = k/2^r-1 <= 1/2 (ya que k<=2^r-2).

Esto implica que en promedio el ciclo se ejecuta 2 veces => O(k*r).