Limite de Chernoff

O limite genérico de Chernoff para uma variável aleatória X {\displaystyle X} é obtido aplicando a desigualdade de Markov a e t X {\displaystyle e^{tX}} (por isso, às vezes é chamado de "limite de Markov exponencial" ou "limite de momentos exponenciais"). Para t > 0 {\displaystyle t>0} , isso fornece um limite para a cauda direita [en] de X {\displaystyle X} em termos de sua função geradora de momentos [en] M ( t ) = E ⁡ ( e t X ) {\displaystyle M(t)=\operatorname {E} (e^{tX})} : Como esse limite é válido para todo t > 0 {\displaystyle t>0} , podemos tomar o ínfimo: Realizando a mesma análise com t < 0 {\displaystyle t<0} , obtemos um limite semelhante para a cauda esquerda: A quantidade M ( t ) e − t a {\displaystyle M(t)e^{-ta}} pode ser expressa como o valor esperado E ⁡ ( e t X ) e − t a {\displaystyle \operatorname {E} (e^{tX})e^{-ta}} , ou equivalentemente E ⁡ ( e t ( X − a ) ) {\displaystyle \operatorname {E} (e^{t(X-a)})} .

Quando X é a soma de n variáveis aleatórias independentes X1, ..., Xn, a função geradora de momentos de X é o produto das funções geradoras de momentos individuais, resultando em: Limites específicos de Chernoff são obtidos calculando a função geradora de momentos E ⁡ [ e − t ⋅ X i ] {\displaystyle \operatorname {E} \left[e^{-t\cdot X_{i}}\right]} para instâncias específicas das variáveis aleatórias X i {\displaystyle X_{i}} . Quando as variáveis aleatórias também são identicamente distribuídas (iid), o limite de Chernoff para a soma reduz-se a uma simples reescala do limite de Chernoff de uma única variável. Ou seja, o limite de Chernoff para a média de n variáveis iid é equivalente à n-ésima potência do limite de Chernoff de uma única variável (veja teorema de Cramér [en]).

Os limites de Chernoff também podem ser aplicados a somas gerais de variáveis aleatórias independentes e limitadas, independentemente de sua distribuição; isso é conhecido como desigualdade de Hoeffding [en]. A prova segue uma abordagem semelhante aos outros limites de Chernoff, mas aplicando o lema de Hoeffding [en] para limitar as funções geradoras de momentos.

Os limites nas seções seguintes para variáveis de Bernoulli são derivados usando que, para uma variável de Bernoulli X i {\displaystyle X_{i}} com probabilidade p de ser igual a 1, Pode-se encontrar várias formas de limites de Chernoff: a forma aditiva original (que fornece um limite para o erro absoluto) ou a forma multiplicativa mais prática (que limita o erro relativo à média).

Os limites de Chernoff têm aplicações úteis em balanceamento de conjuntos [en] e roteamento de pacotes em redes esparsas [en]. O problema de balanceamento de conjuntos surge ao projetar experimentos estatísticos. Tipicamente, ao projetar um experimento estatístico, dadas as características de cada participante, precisamos saber como dividir os participantes em dois grupos disjuntos de modo que cada característica seja aproximadamente equilibrada entre os dois grupos. Os limites de Chernoff também são usados para obter limites apertados para problemas de roteamento de permutação, que reduzem o congestionamento de rede [en] ao rotear pacotes em redes esparsas. Os limites de Chernoff são utilizados na teoria do aprendizado computacional para provar que um algoritmo de aprendizado é provavelmente aproximadamente correto [en], ou seja, com alta probabilidade, o algoritmo tem pequeno erro em um conjunto de dados de treinamento suficientemente grande.

Rudolf Ahlswede e Andreas Winter introduziram um limite de Chernoff para variáveis aleatórias com valores matriciais. A seguinte versão da desigualdade pode ser encontrada no trabalho de Tropp. Seja M1, ..., Mt variáveis aleatórias independentes com valores matriciais tais que M i ∈ C d 1 × d 2 {\displaystyle M_{i}\in \mathbb {C} ^{d_{1}\times d_{2}}} e E [ M i ] = 0 {\displaystyle \mathbb {E} [M_{i}]=0} . Denote por ‖ M ‖ {\displaystyle \lVert M\rVert } a norma de operador da matriz M {\displaystyle M} . Se ‖ M i ‖ ≤ γ {\displaystyle \lVert M_{i}\rVert \leq \gamma } for válido quase certamente para todo i ∈ { 1 , … , t } {\displaystyle i\in \{1,\ldots ,t\}} , então, para todo ε > 0, Note que, para concluir que o desvio de 0 é limitado por ε com alta probabilidade, precisamos escolher um número de amostras t {\displaystyle t} proporcional ao logaritmo de d 1 + d 2 {\displaystyle d_{1}+d_{2}} . Em geral, infelizmente, uma dependência em log ⁡ ( min ( d 1 , d 2 ) ) {\displaystyle \log(\min(d_{1},d_{2}))} é inevitável: considere, por exemplo, uma matriz de sinal aleatório diagonal de dimensão d × d {\displaystyle d\times d} . A norma de operador da soma de t amostras independentes é precisamente o desvio máximo entre d caminhadas aleatórias independentes de comprimento t. Para alcançar um limite fixo no desvio máximo com probabilidade constante, é fácil ver que t deve crescer logaritmicamente com d neste cenário.

A seguinte variante do limite de Chernoff pode ser usada para limitar a probabilidade de que uma maioria em uma população se torne uma minoria em uma amostra, ou vice-versa. Suponha que haja uma população geral A e uma subpopulação B ⊆ A. Marque o tamanho relativo da subpopulação (|B|/|A|) por r. Suponha que escolhamos um inteiro k e uma amostra aleatória S ⊂ A de tamanho k. Marque o tamanho relativo da subpopulação na amostra (|B∩S|/|S|) por rS. Em particular, se B for uma maioria em A (ou seja, r > 0.5), podemos limitar a probabilidade de que B permaneça maioria em S (rS > 0.5) tomando: d = 1 − 1/(2r): Esse limite não é, de forma alguma, apertado. Por exemplo, quando r = 0.5, obtemos um limite trivial Prob > 0.