Variáveis Aleatórias e Esperança

Uma variável aleatória é uma função do espaço amostral nos reais. Ela traduz resultados qualitativos em números, permitindo calcular médias e dispersões.

Definição

$X: \Omega \to \mathbb{R}$. Para o lançamento de dois dados, $X$ pode ser a soma, o máximo ou a diferença — variáveis diferentes sobre o mesmo espaço.

Discreta: assume valores num conjunto enumerável, descrita pela função de massa $p(x) = P(X=x)$.

Contínua: descrita por densidade $f$, com $P(a \le X \le b) = \int_a^b f$.

Esperança

$$E[X] = \sum_x x,p(x) \qquad \text{ou} \qquad E[X] = \int x f(x),dx$$

É a média ponderada pelos pesos de probabilidade — o valor em torno do qual a média amostral se estabiliza quando o número de repetições cresce (lei dos grandes números).

Nem toda variável tem esperança finita. A distribuição de Cauchy é o exemplo clássico, e o paradoxo de São Petersburgo é a versão discreta.

Linearidade da esperança

$$E[aX + bY] = aE[X] + bE[Y]$$

Vale sempre, mesmo com $X$ e $Y$ dependentes. Esta é a propriedade mais útil de toda a probabilidade aplicada, e a que resolve problemas que pareceriam intratáveis.

Para produtos, porém, a igualdade $E[XY] = E[X]E[Y]$ exige independência.

A técnica dos indicadores

Combinar linearidade com variáveis indicadoras é o truque mais produtivo da análise de algoritmos.

Uma indicadora $I_A$ vale 1 se o evento $A$ ocorre e 0 caso contrário. Então $E[I_A] = P(A)$.

Para contar ocorrências, escreva o total como soma de indicadoras e aplique linearidade. Cada probabilidade individual costuma ser fácil, e a dependência entre elas não importa.

Exemplo: pontos fixos de uma permutação aleatória. Seja $X$ o número de elementos que ficam na posição original. Escreva $X = \sum_{i=1}^n I_i$, com $I_i$ indicando que o elemento $i$ ficou no lugar. Como $P(I_i = 1) = 1/n$:

$$E[X] = \sum_{i=1}^n \frac1n = 1$$

Independentemente de $n$, espera-se exatamente um ponto fixo. As indicadoras são claramente dependentes, e isso não afeta o cálculo.

Exemplo: colecionador de cupons. Para coletar todos os $n$ cupons, o tempo esperado é

$$E[T] = n\sum_{k=1}^{n}\frac1k \approx n\ln n$$

decompondo o tempo total na soma dos tempos de espera por cada cupom novo. É o resultado que dimensiona testes aleatórios e amostragem por cobertura.

Variância e desvio padrão

$$\operatorname{Var}(X) = E[(X-\mu)^2] = E[X^2] - (E[X])^2$$

$$\sigma = \sqrt{\operatorname{Var}(X)}$$

Propriedades:

$$\operatorname{Var}(aX+b) = a^2\operatorname{Var}(X)$$

$$\operatorname{Var}(X+Y) = \operatorname{Var}(X) + \operatorname{Var}(Y) \quad \text{se independentes}$$

A segunda exige independência, ao contrário da esperança. No caso geral aparece o termo de covariância:

$$\operatorname{Var}(X+Y) = \operatorname{Var}(X)+\operatorname{Var}(Y)+2\operatorname{Cov}(X,Y)$$

A fórmula $E[X^2] - (E[X])^2$ é matematicamente correta e numericamente perigosa: subtrair dois números grandes e próximos causa cancelamento catastrófico. Para calcular variância em código, use o algoritmo de Welford, que atualiza incrementalmente:

def welford(dados):
    n = 0
    media = 0.0
    m2 = 0.0
    for x in dados:
        n += 1
        delta = x - media
        media += delta / n
        m2 += delta * (x - media)
    return media, m2 / (n - 1)

Covariância e correlação

$$\operatorname{Cov}(X,Y) = E[(X-\mu_X)(Y-\mu_Y)]$$

$$\rho = \frac{\operatorname{Cov}(X,Y)}{\sigma_X\sigma_Y} \in [-1,1]$$

Independência implica covariância nula; a recíproca é falsa. Se $X$ é simétrica em torno de zero e $Y = X^2$, a covariância é zero e as variáveis são fortemente dependentes. Correlação mede apenas relação linear.

Exemplo trabalhado

Lançamento de um dado justo:

$$E[X] = \frac{1+2+3+4+5+6}{6} = 3{,}5$$

$$E[X^2] = \frac{1+4+9+16+25+36}{6} = \frac{91}{6}$$

$$\operatorname{Var}(X) = \frac{91}{6} - 3{,}5^2 = 15{,}1\overline{6} - 12{,}25 \approx 2{,}92$$

Para a soma de dois dados independentes: $E = 7$ e $\operatorname{Var} \approx 5{,}83$.

Aplicações em computação

Análise de algoritmos. O número esperado de comparações do quicksort sai de indicadoras: $I_{ij}$ indica se os elementos de posições $i$ e $j$ são comparados, com $P = 2/(j-i+1)$.

Tabelas hash. Comprimento esperado de lista, número esperado de colisões.

Dimensionamento. Filas, taxas de chegada e tempos de espera são análises de esperança.

Aprendizado de máquina. A decomposição viés-variância do erro de generalização é literalmente esta variância.

Amostragem. Estimadores não viesados são aqueles cuja esperança é o parâmetro verdadeiro; a variância determina quantas amostras são necessárias.

Erros comuns

• Exigir independência para a linearidade da esperança. Não é necessária.
• Somar variâncias de variáveis dependentes.
• Concluir independência a partir de correlação nula.
• Calcular variância pela fórmula ingênua e sofrer cancelamento.
• Confundir a média amostral com a esperança. Uma é estatística, a outra é parâmetro.

Leituras recomendadas

• Mitzenmacher e Upfal, capítulos 2 e 3 — esperança e a técnica dos indicadores aplicadas a algoritmos.
• Ross, capítulos 4 a 7 — variáveis aleatórias com muitos exemplos.
• Motwani e Raghavan, capítulo 3 — momentos e desvios em algoritmos aleatorizados.

Michael Mitzenmacher and Eli Upfal (2017). Probability and Computing: Randomization and Probabilistic Techniques. Cambridge University Press. ISBN 9781107154889. Sheldon M. Ross (2014). A First Course in Probability. Pearson. ISBN 9781292024929. Rajeev Motwani and Prabhakar Raghavan (1995). Randomized Algorithms. Cambridge University Press. DOI: 10.1017/cbo9780511814075.

Referências

1. Michael Mitzenmacher; Eli Upfal (2017). Probability and Computing: Randomization and Probabilistic Techniques. Cambridge University Press.
2. Sheldon M. Ross (2014). A First Course in Probability. Pearson.
3. Rajeev Motwani; Prabhakar Raghavan (1995). Randomized Algorithms. Cambridge University Press.