Na teoria das probabilidades, um limite de Chernoff é um limite superior exponencialmente decrescente para a cauda de uma variável aleatória, baseado em sua . O mínimo de todos esses limites exponenciais forma o limite de Chernoff-Cramér, que pode decair mais rapidamente que exponencialmente (por exemplo, ). É particularmente útil para somas de variáveis aleatórias independentes, como somas de variáveis de Bernoulli.
O limite é comumente nomeado em homenagem a Herman Chernoff, que descreveu o método em um artigo de 1952, embora Chernoff tenha atribuído o conceito a Herman Rubin. Em 1938, Harald Cramér publicou um conceito quase idêntico, agora conhecido como .
O limite de Chernoff é mais preciso que os limites de cauda baseados no primeiro ou segundo momento, como a ou a desigualdade de Chebyshev, que fornecem apenas limites de decaimento polinomial. No entanto, quando aplicado a somas, o limite de Chernoff exige que as variáveis aleatórias sejam independentes, uma condição não necessária para as desigualdades de Markov ou Chebyshev.
O limite de Chernoff está relacionado às . Também é usado para provar a , a e a .
Limites genéricos de Chernoff
O limite genérico de Chernoff para uma variável aleatória é obtido aplicando a desigualdade de Markov a (por isso, às vezes é chamado de "limite de Markov exponencial" ou "limite de momentos exponenciais").
Para , isso fornece um limite para a de em termos de sua :
Como esse limite é válido para todo , podemos tomar o ínfimo:
Realizando a mesma análise com , obtemos um limite semelhante para a cauda esquerda:
e
A quantidade pode ser expressa como o valor esperado , ou equivalentemente .
Propriedades
A função exponencial é convexa, então, pela desigualdade de Jensen, . Segue-se que o limite para a cauda direita é maior ou igual a um quando , sendo, portanto, trivial; da mesma forma, o limite para a cauda esquerda é trivial para . Assim, podemos combinar os dois ínfimos e definir o limite de Chernoff bilateral:
que fornece um limite superior para a função de distribuição acumulada dobrada de (dobrada na média, não na mediana).
O logaritmo do limite de Chernoff bilateral é conhecido como a (ou "transformada de Cramér") . É equivalente à , ou conjugado convexo, da função geradora de cumulantes , definida como:
A função geradora de momentos é , então, por uma propriedade do conjugado convexo, o limite de Chernoff deve ser . O limite de Chernoff atinge seu máximo na média, , e é invariante sob translação: .
O limite de Chernoff é exato se, e somente se, for uma massa concentrada única (). O limite é apertado apenas nos extremos ou além de uma variável aleatória limitada, onde os ínfimos são atingidos para infinito. Para variáveis aleatórias ilimitadas, o limite não é apertado em nenhum ponto, embora seja assintoticamente apertado até fatores subexponenciais ("exponencialmente apertado"). Momentos individuais podem fornecer limites mais apertados, ao custo de maior complexidade analítica.
Na prática, o limite exato de Chernoff pode ser difícil de avaliar analiticamente, caso em que um limite superior adequado para a função geradora de momentos (ou cumulantes) pode ser usado (por exemplo, uma CGF subparabólica gerando um limite de Chernoff subgaussiano).
+Funções de taxa exatas e limites de Chernoff para distribuições comunsDistribuiçãoDistribuição normalDistribuição de Bernoulli(detalhada abaixo)Bernoulli padrão (H é a )Distribuição gamaDistribuição qui-quadradaDistribuição de Poisson
Limites inferiores a partir da FGM Usando apenas a função geradora de momentos, um limite inferior para as probabilidades de cauda pode ser obtido aplicando a a , resultando em:
(um limite para a cauda esquerda é obtido para ). Diferentemente do limite de Chernoff, esse resultado não é exponencialmente apertado.
Theodosopoulos construiu um limite inferior mais apertado baseado na FGM usando um procedimento de .
Para distribuições específicas (como a binomial), limites inferiores da mesma ordem exponencial do limite de Chernoff estão frequentemente disponíveis.
Somas de variáveis aleatórias independentes Quando é a soma de variáveis aleatórias independentes , a função geradora de momentos de é o produto das funções geradoras de momentos individuais, resultando em:
e:
Limites específicos de Chernoff são obtidos calculando a função geradora de momentos para instâncias específicas das variáveis aleatórias .
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 ).
Somas de variáveis aleatórias independentes limitadas 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 . A prova segue uma abordagem semelhante aos outros limites de Chernoff, mas aplicando o para limitar as funções geradoras de momentos.
Suponha que sejam variáveis aleatórias independentes tomando valores em Seja sua soma e o valor esperado da soma. Então, para qualquer ,
Somas de variáveis aleatórias de Bernoulli independentes Os limites nas seções seguintes para variáveis de Bernoulli são derivados usando que, para uma variável de Bernoulli 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).
Forma multiplicativa (erro relativo) Limite de Chernoff multiplicativo. Suponha que sejam variáveis aleatórias independentes tomando valores em Seja sua soma e o valor esperado da soma. Então, para qualquer ,
Uma estratégia de prova semelhante pode ser usada para mostrar que, para ,
A fórmula acima é frequentemente difícil de usar na prática, então os seguintes limites mais soltos, mas mais convenientes, são frequentemente usados, que seguem da desigualdade da lista de desigualdades logarítmicas:
Note que os limites são triviais para .
Além disso, com base na expansão de Taylor para a função W de Lambert,
Forma aditiva (erro absoluto) O seguinte teorema é devido a Wassily Hoeffding e, portanto, é chamado de teorema de Chernoff–Hoeffding.
Teorema de Chernoff–Hoeffding. Suponha que sejam variáveis aleatórias i.i.d. tomando valores em Seja e .
onde
é a divergência de Kullback–Leibler entre variáveis aleatórias de Bernoulli com parâmetros x e y, respectivamente. Se então , o que implica
Um limite mais simples segue relaxando o teorema usando , que decorre da convexidade de e do fato de que
Esse resultado é um caso especial da desigualdade de Hoeffding. Às vezes, os limites
que são mais fortes para também são usados.
Aplicações Os limites de Chernoff têm aplicações úteis em e roteamento de pacotes em redes .
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.Consulte esta seção do livro para mais informações sobre o problema.
Os limites de Chernoff também são usados para obter limites apertados para problemas de roteamento de permutação, que reduzem o 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 é , ou seja, com alta probabilidade, o algoritmo tem pequeno erro em um conjunto de dados de treinamento suficientemente grande.
Os limites de Chernoff podem ser usados efetivamente para avaliar o "nível de robustez" de uma aplicação/algoritmo ao explorar seu espaço de perturbação com randomização. O uso do limite de Chernoff permite abandonar a forte—e majoritariamente irrealista—hipótese de pequena perturbação (a magnitude da perturbação é pequena). O nível de robustez pode ser usado para validar ou rejeitar uma escolha algorítmica específica, uma implementação de hardware ou a adequação de uma solução cujos parâmetros estruturais são afetados por incertezas.
Um uso simples e comum dos limites de Chernoff é para "reforçar" algoritmos randomizados. Se um algoritmo produz uma estimativa que é a resposta desejada com probabilidade p > 1/2, pode-se obter uma taxa de sucesso maior executando o algoritmo vezes e retornando a estimativa produzida por mais de n/2 execuções do algoritmo. (Não pode haver mais de uma estimativa.) Assumindo que essas execuções do algoritmo são independentes, a probabilidade de que mais de n/2 das estimativas estejam corretas é igual à probabilidade de que a soma de variáveis aleatórias de Bernoulli independentes que são 1 com probabilidade p seja maior que n/2. Isso pode ser mostrado como sendo pelo menos via o limite de Chernoff multiplicativo (Corolário 13.3 nas notas de aula de Sinclair, ).:
Limite de Chernoff para matrizes 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 variáveis aleatórias independentes com valores matriciais tais que e . Denote por a norma de operador da matriz . Se for válido quase certamente para todo , então, para todo ,
Leonard E. Parker Jr.
Note que, para concluir que o desvio de 0 é limitado por com alta probabilidade, precisamos escolher um número de amostras proporcional ao logaritmo de . Em geral, infelizmente, uma dependência em é inevitável: considere, por exemplo, uma matriz de sinal aleatório diagonal de dimensão . 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.
Teorema sem dependência nas dimensões Seja e M uma matriz simétrica real aleatória com e quase certamente. Suponha que cada elemento no suporte de M tenha no máximo posto r. Defina
Se for válido quase certamente, então
onde são cópias i.i.d. de M.
Variante de amostragem
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.; lemma 6.1
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.
Então, para toda fração d ∈ [0,1]:
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):Veja os gráficos de: o limite como função de r quando k varia e o limite como função de k quando r varia.
Esse limite não é, de forma alguma, apertado. Por exemplo, quando r = 0.5, obtemos um limite trivial Prob > 0.
Provas
Forma multiplicativa Seguindo as condições do limite de Chernoff multiplicativo, sejam variáveis aleatórias de Bernoulli independentes, cuja soma é , cada uma com probabilidade pi de ser igual a 1. Para uma variável de Bernoulli:
Assim, usando () com para qualquer e onde ,
Se simplesmente definirmos de modo que para , podemos substituir e encontrar
Isso prova o resultado desejado.
Teorema de Chernoff–Hoeffding (forma aditiva) Seja . Tomando em (), obtemos:
Agora, sabendo que , temos
Portanto, podemos calcular facilmente o ínfimo usando cálculo:
Igualando a equação a zero e resolvendo, temos
de modo que