Esta página dá um exemplo simples de análise probabilística de um algoritmo aleatorizado (= randomized). O problema usado como exemplo é o de encontar o máximo de um vetor com elementos dosi a dois distintos.
O texto é baseada no capítulo 5 de CLRS. Veja também o capítulo 13 de KT e o verbete Randomized algorithm na Wikipedia.
Suponha dado um vetor A[1..n] que contém uma permutação de 1..n. (Poderíamos igualmente bem usar qualquer vetor com n números estritamente positivos distintos dois a dois.) Considere o problema de encontrar o máximo do vetor A[1..n]. O seguinte algoritmo resolve o problema:
| Máximo (A, n) |
| 1 _ max ← 0 |
| 2 _ para i crescendo de 1 até n faça |
| 3 ____ se A[i] > max |
| 4 _______ então max ← A[i] |
| 5 _ devolva max |
(O algoritmo sempre devolve n.) Quantas vezes a linha 4 é executada? No pior caso, n vezes. No melhor caso, uma vez. Quantas vezes a linha 4 é executada em média? Será que é n/2?
(No CLRS, o problema de determinar o número médio de execuções de linha 4 é denominado Hiring problem. O livro imagina que os números 1,…,n são candidatos a um emprego e que A[i] é a qualidade do candidato i. O empregador examina um candidato por semana. Se o candidato for melhor que o que está contratado atualmente, o empregado atual é demitido e o novo é contratado.)
Seja X a variável aleatória que dá o número total de execuções da linha 4 quando A[1..n] é uma permutação aleatória uniforme de 1..n (cada permutação tem probabilidade 1/n!). Queremos calcular a esperança
E[X]
da variável X. (Por definição, essa esperança é a soma ∑1≤k≤n k Pr[X=k], sendo Pr[X=k] a probabilidade de que a linha 4 seja executada exatamente k vezes. Mas é mais fácil fazer os cálculos a partir das variáveis Xi definidas a seguir.) A variável X é igual à soma X1 + … + Xn, sendo cada Xi a variável aleatória definida assim:
se "max ← A[i]" é executado então Xi = 1 senão Xi = 0.
O valor esperado de Xi é igual à probabilidade de que A[i] seja máximo em A[1..i]:
E[Xi] = 1/i.
Pela linearidade da esperança,
| E[X] | = | E[X1] + E[X2] + … + E[Xn] |
| = | 1/1 + 1/2 + … + 1/n |
(Ou seja, para todo n fixo, a média do número de execuções da linha 4 para as n! permutações de 1..n é exatamente 1/1+1/2+…+1/n.) Como 1/1+1/2+…+1/n fica entre ln n e ln n + 1,
| 1,2,3,4 | 4 |
| 1,2,4,3 | 3 |
| 1,3,2,4 | 3 |
| 1,3,4,2 | 3 |
| 1,4,2,3 | 2 |
| 1,4,3,2 | 2 |
| 2,1,3,4 | 3 |
| 2,1,4,3 | 2 |
| 2,3,1,4 | 3 |
| 2,3,4,1 | 3 |
| 2,4,1,3 | 2 |
| 2,4,3,1 | 2 |
| 3,1,2,4 | 2 |
| 3,1,4,2 | 2 |
| 3,2,1,4 | 2 |
| 3,2,4,1 | 2 |
| 3,4,1,2 | 2 |
| 3,4,2,1 | 2 |
| 4,1,2,3 | 1 |
| 4,1,3,2 | 1 |
| 4,2,1,3 | 1 |
| 4,2,3,1 | 1 |
| 4,3,1,2 | 1 |
| 4,3,2,1 | 1 |
EXEMPLO: A tabela dá o número de execuções da linha 4 para cada uma das 24 permutações de 1,2,3,4. Como se vê, o número médio de execuções da linha 4 é 50/24 . Compare com 1/1 + 1/2 + 1/3 + 1/4.
A análise acima supõe que A[1..n] é uma permutação aleatória uniforme de 1..n. Para garantir que essa hipótese está satisfeita, basta permutar os elementos do vetor antes de invocar o algoritmo:
| Máximo-Aleatorizado (A, n) |
| 1 _ Permute (A, n) |
| 2 _ devolva Máximo (A, n) |
A linha 1 permuta os elementos de A[1..n] de modo que cada uma das permutações tenha probabilidade 1/n!. Eis como isso pode ser feito:
| Permute (A, n) |
| 1 _ para i crescendo de 1 até n faça |
| 2 ____ j ← Random (i, n) |
| 3 ____ troque A[ j] ↔ A[i] |
O comando Random (i,n) produz um elemento do conjunto {i,i+1,…,n} com probabilidade 1/(n−i+1) para cada elemento.
Para verificar que o algoritmo Permute produz uma permutação aleatória uniforme de A[1..n], observe o seguinte invariante: no início de cada iteração, para qualquer permutação P de 1 .. i−1,
A[1 .. i−1] coincide com P com probabilidade (n−i+1)!/n! .
No início da última iteração, quando i = n+1, o vetor A[1..n] tem probabilidade 1/n! de conter qualquer uma das permutações de 1..n.
| Permute-sem-Identidade (A, n) |
| 1 _ para i crescendo de 1 até n faça |
| 2 ____ j ← Random (i+1, n) |
| 3 ____ troque A[ j] ↔ A[i] |
| Permute-com-Todos (A, n) |
| 1 _ para i crescendo de 1 até n faça |
| 2 ____ j ← Random (1, n) |
| 3 ____ troque A[ j] ↔ A[i] |