Concentração e Algoritmos Aleatorizados

Saber a esperança de uma quantidade aleatória raramente basta. O que se quer, em geral, é uma garantia de que ela não se afasta muito da esperança. As desigualdades de concentração fornecem exatamente isso, e são a base da análise de algoritmos aleatorizados.

Desigualdade de Markov

Para $X \ge 0$ e $a > 0$:

$$P(X \ge a) \le \frac{E[X]}{a}$$

Exige apenas não negatividade e a esperança. É fraca, mas é o ponto de partida de quase todas as outras.

Consequência prática: no máximo $1/k$ da massa de uma variável não negativa está acima de $k$ vezes sua média.

Desigualdade de Chebyshev

$$P(|X - \mu| \ge k\sigma) \le \frac{1}{k^2}$$

Usa a variância e é bem mais forte. Vale para qualquer distribuição com variância finita: no máximo $25%$ da massa está a mais de $2\sigma$ da média, no máximo $11%$ a mais de $3\sigma$.

Compare com a normal, em que apenas $0{,}3%$ ficam além de $3\sigma$: Chebyshev é conservadora justamente por não supor nada sobre a forma.

Limites de Chernoff

Para $X = \sum_{i=1}^n X_i$ soma de variáveis de Bernoulli independentes com $\mu = E[X]$:

$$P(X \ge (1+\delta)\mu) \le e^{-\frac{\delta^2\mu}{2+\delta}}$$

$$P(X \le (1-\delta)\mu) \le e^{-\frac{\delta^2\mu}{2}}$$

O decaimento é exponencial em $\mu$, não polinomial. Essa é a diferença qualitativa: Chebyshev dá $1/k^2$; Chernoff dá $e^{-k}$.

É o que permite afirmações do tipo "com probabilidade $1 - 1/n^{10}$, nenhuma lista da tabela hash excede $O(\log n / \log\log n)$" — garantias fortes o bastante para serem tratadas como certezas práticas.

Amplificação

Se um algoritmo aleatorizado acerta com probabilidade $p > 1/2$, repeti-lo $k$ vezes e tomar a maioria faz o erro cair exponencialmente em $k$.

Para algoritmos unilaterais — que nunca erram ao responder "sim", mas podem errar ao responder "não" — a amplificação é ainda mais simples: $k$ repetições reduzem o erro a $\varepsilon^k$.

É por isso que o teste de primalidade de Miller-Rabin, com erro por rodada de no máximo $1/4$, atinge erro abaixo de $10^{-30}$ com 50 rodadas. Nesse ponto a probabilidade de erro é menor que a de uma falha de hardware, o que é a justificativa prática para usá-lo em criptografia.

Las Vegas e Monte Carlo

Tipo	Resposta	Tempo
Las Vegas	Sempre correta	Aleatório
Monte Carlo	Provavelmente correta	Determinado

Las Vegas: quicksort com pivô aleatório sempre ordena; o que varia é o tempo. Espera-se $O(n\log n)$, e Chernoff garante que o desvio é improvável.

Monte Carlo: Miller-Rabin pode declarar composto como primo, com probabilidade controlada, mas roda em tempo fixo.

Todo Las Vegas pode virar Monte Carlo (interrompendo após um limite de tempo); a recíproca exige verificar a resposta, o que nem sempre é possível.

Por que aleatorizar

Simplicidade. O quicksort aleatorizado é muito mais simples que algoritmos determinísticos com a mesma garantia de pior caso.

Evitar adversários. Uma função de hash fixa pode ser atacada com entradas que colidem propositalmente — um vetor de negação de serviço real, que afetou várias linguagens. Escolher a função aleatoriamente a cada execução torna o ataque impossível: o adversário não conhece a moeda.

Quebrar simetria. Em sistemas distribuídos, backoff aleatório evita que todos os nós retransmitam ao mesmo tempo. Sem aleatoriedade, não há como distinguir processos idênticos.

Tratar dimensão alta. Monte Carlo e projeções aleatórias (Johnson-Lindenstrauss) escapam da maldição da dimensionalidade.

Exemplo trabalhado

Uma moeda justa é lançada 1000 vezes. Qual a probabilidade de sair mais de 600 caras?

$\mu = 500$, $\sigma = \sqrt{1000 \cdot 0{,}25} \approx 15{,}8$.

Chebyshev: $600$ está a $\delta = 100/15{,}8 \approx 6{,}3$ desvios, logo $P \le 1/6{,}3^2 \approx 2{,}5%$.

Chernoff com $\delta = 0{,}2$: $P \le e^{-\frac{0{,}04 \cdot 500}{2{,}2}} \approx e^{-9{,}1} \approx 1{,}1\times10^{-4}$.

O valor verdadeiro é da ordem de $10^{-10}$. Chernoff é conservador, mas dá a ordem de grandeza certa; Chebyshev erra por seis ordens de grandeza. A lição: use a desigualdade mais forte cujas hipóteses você consiga satisfazer.

Aplicações em computação

Tabelas hash. Concentração garante que nenhuma lista fica longa demais.

Balanceamento de carga. A estratégia de "duas escolhas aleatórias" reduz a carga máxima de $\Theta(\log n/\log\log n)$ para $\Theta(\log\log n)$ — uma melhora dramática com uma mudança mínima.

Esboços e amostragem. Count-Min Sketch e HyperLogLog têm garantias de erro derivadas de concentração.

Aprendizado de máquina. Limites de generalização (PAC) são desigualdades de concentração aplicadas ao erro empírico.

Sistemas distribuídos. Backoff exponencial com jitter; escolha aleatória de líder.

Erros comuns

• Aplicar Chernoff sem independência. A hipótese é essencial; para variáveis dependentes existem variantes (Azuma, McDiarmid) com condições próprias.
• Confundir Las Vegas com Monte Carlo.
• Usar gerador previsível em contexto adversarial, anulando a proteção.
• Esquecer que "com alta probabilidade" não é "sempre".
• Não fixar semente e obter experimentos irreprodutíveis.

Leituras recomendadas

• Mitzenmacher e Upfal, capítulos 4 e 5 — Chernoff e o método probabilístico, com aplicações a balanceamento de carga.
• Motwani e Raghavan — a referência clássica de algoritmos aleatorizados.
• Vershynin, High-Dimensional Probability — concentração moderna aplicada a ciência de dados; gratuito online.
• Dubhashi e Panconesi, Concentration of Measure for the Analysis of Randomized Algorithms.

Michael Mitzenmacher and Eli Upfal (2017). Probability and Computing: Randomization and Probabilistic Techniques. Cambridge University Press. ISBN 9781107154889. Rajeev Motwani and Prabhakar Raghavan (1995). Randomized Algorithms. Cambridge University Press. DOI: 10.1017/cbo9780511814075. Roman Vershynin (2018). High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press. DOI: 10.1017/9781108231596.

Referências

1. Michael Mitzenmacher; Eli Upfal (2017). Probability and Computing: Randomization and Probabilistic Techniques. Cambridge University Press.
2. Rajeev Motwani; Prabhakar Raghavan (1995). Randomized Algorithms. Cambridge University Press.
3. Roman Vershynin (2018). High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press.