Esperança, variância e testes A/B

E[X] = Σ x · P(X = x)
Var(X) = E[(X − E[X])²] = E[X²] − E[X]²
Linearidade:  E[X + Y] = E[X] + E[Y]   (sempre, mesmo sem independência!)

A linearidade da esperança é a ferramenta mais poderosa da análise de algoritmos aleatorizados. Ela permite quebrar um problema difícil em indicadores simples.

Quicksort aleatório

Os elementos i-ésimo e j-ésimo menores são comparados exatamente quando um deles é o primeiro pivô escolhido entre os j − i + 1 elementos do intervalo. A chance disso é 2/(j − i + 1). Somando sobre todos os pares:

E[comparações] = Σᵢ<ⱼ 2/(j−i+1) ≈ 2n ln n ≈ 1,39 n log₂ n

Testes A/B

Pelo Teorema Central do Limite, a média de muitas amostras é aproximadamente normal, com desvio padrão σ/√n. Para comparar duas taxas de conversão, use o teste z para proporções:

from math import sqrt, erf

def teste_ab(conv_a, n_a, conv_b, n_b):
    pa, pb = conv_a / n_a, conv_b / n_b
    p = (conv_a + conv_b) / (n_a + n_b)
    se = sqrt(p * (1 - p) * (1 / n_a + 1 / n_b))
    z = (pb - pa) / se
    p_valor = 2 * (1 - 0.5 * (1 + erf(abs(z) / sqrt(2))))
    return z, p_valor

print(teste_ab(200, 5000, 245, 5000))   # z ≈ 2,19, p ≈ 0,03