Existe um limite reverso de Chernoff que limita que a probabilidade de cauda seja pelo menos tanta.
ou seja, se são variáveis aleatórias binomiais independentes e . Então podemos provar para alguma função .
pr.probability
chernoff-bound
Ashwinkumar BV
fonte
fonte
Respostas:
Aqui está uma prova explícita de que um limite de Chernoff padrão é restrito a fatores constantes no expoente para uma faixa específica dos parâmetros. (Em particular, sempre que as variáveis forem 0 ou 1, e 1 com probabilidade 1/2 ou menos eϵ∈(0,1/2) , e o limite superior de Chernoff for menor que uma constante.)
Se você encontrar algum erro, entre em contato.
Lema 1. (tensão do limite de Chernoff) SejaX a média de k variáveis independentes, 0/1 aleatórias (rv). Para qualquer ϵ∈(0,1/2] e p∈(0,1/2] , assumindo ϵ2pk≥3 ,
(i) Se cada rv é 1 com probabilidade no máximop , então
(ii) Se cada rv for 1 com probabilidade pelo menosp , então
Prova. Usamos a seguinte observação:
Reivindicação 1. Se ,1≤ℓ≤k−1 (kℓ) ≥ 1e2πℓ−−−√(kℓ)ℓ(kk−ℓ)k−ℓ
Prova de reivindicação 1. Pela aproximação de Stirling, ondei!=2πi−−−√(i/e)ieλ λ∈[1/(12i+1),1/12i].
Portanto, , que é , é pelo menos QED(kℓ) k!ℓ!(k−ℓ)!
Prova do Lema 1 Parte (i). Sem perda de generalidade, assuma que cada variável aleatória 0/1 na soma é 1 com probabilidade exatamente . Nota é igual à soma e .X p Pr[X≤(1−ϵ)p] ∑⌊(1−ϵ)pk⌋i=0Pr[X=i/k] Pr[X=i/k]=(ki)pi(1−p)k−i
Corrija . Os termos na soma estão aumentando; portanto, os termos com o índice têm valor pelo menos ; portanto, sua soma tem valor total pelo menos . Para concluir a prova, mostramos queℓ=⌊(1−2ϵ)pk⌋+1 i≥ℓ Pr[X=ℓ/k] (ϵpk−2)Pr[X=ℓ/k]
As suposições e fornecem ; portanto, o lado esquerdo acima é pelo menos . Usando a Reivindicação 1, para vincular , isso é pelo menos onde eϵ2pk≥3 ϵ≤1/2 ϵpk≥6 23ϵpk(kℓ)pℓ(1−p)k−ℓ (kℓ) AB A=23eϵpk/2πℓ−−−√ B=(kℓ)ℓ(kk−ℓ)k−ℓpℓ(1−p)k−ℓ.
Para finalizar, mostramos e .A≥exp(−ϵ2pk) B≥exp(−8ϵ2pk)
Reivindicação 2.A≥exp(−ϵ2pk)
Prova da reivindicação 2. As suposições e implicam (i) .ϵ2pk≥3 ϵ≤1/2 pk≥12
Por definição, . Por (i), . Assim, (ii) .ℓ≤pk+1 pk≥12 ℓ≤1.1pk
Substituir o lado direito de (ii) para em fornece (iii) .ℓ A A≥23eϵpk/2.2π−−−−−−√
A suposição, , implica , que com (iii) fornece (iv) .ϵ2pk≥3 ϵpk−−√≥3–√ A≥23e3/2.2π−−−−−−√≥0.1
A partir de , segue-se que (v) .ϵ2pk≥3 exp(−ϵ2pk)≤exp(−3)≤0.04
(iv) e (v) juntos dão a reivindicação. QED
Reivindicação 3. .B≥exp(−8ϵ2pk)
Prova de reivindicação 3. Corrija modo que . A escolha de implica , portanto a reivindicação permanecerá enquanto . Levar cada lado dessa última desigualdade ao poder e simplificar, é equivalente a Substituindo e simplificando, é equivalente aδ ℓ=(1−δ)pk
ℓ δ≤2ϵ B≥exp(−2δ2pk) −1/ℓ
As reivindicações 2 e 3 implicam . Isso implica parte (i) do lema.AB≥exp(−ϵ2pk)exp(−8ϵ2pk)
Prova do Lema 1 Parte (ii). Sem perda de generalidade, assuma que cada variável aleatória é com probabilidade exatamente .1 p
Nota . Corrija .Pr[X≥(1+ϵ)p]=∑ni=⌈(1−ϵ)pk⌉Pr[X=i/k] ℓ^=⌈(1+2ϵ)pk⌉−1
Os últimos termos na soma total pelo menos , que é pelo menos . (A prova disso é a mesma que para (i), exceto com substituído por e substituído por modo que .) QEDϵpk (ϵpk−2)Pr[X=ℓ^/k] exp(−9ϵ2pk) ℓ ℓ^ δ −δ^ ℓ^=(1+δ^)pk
fonte
O teorema de Berry-Esseen pode fornecer limites mais baixos à probabilidade da cauda, desde que sejam maiores que .n−1/2
Outra ferramenta que você pode usar é a desigualdade de Paley-Zygmund . Isso implica que, para qualquer número inteiro par e qualquer variável aleatória com valor real ,k X
Juntamente com o teorema multinomial, para uma soma de variáveis aleatórias rademacher, Paley-Zygmund pode obter limites inferiores bastante fortes. Também funciona com variáveis aleatórias de independência limitada. Por exemplo, você obtém facilmente que a soma das variáveis aleatórias independentes 4 é com probabilidade constante.X n n ±1 Ω(n−−√)
fonte
Se você realmente concorda com as somas delimitadoras dos ensaios de Bernoulli (e não, digamos, com variáveis aleatórias delimitadas), o que se segue é bastante rígido.
(Tratando o argumento para como transformando o padrão normal, isso concorda exatamente com o que o CLT diz a você; de fato, ele nos diz que os binômios que satisfazem as condições do teorema dominam seus gaussianos correspondentes nas caudas superiores.)Φ
A partir daqui, você pode usar limites em para obter algo melhor. Por exemplo, no primeiro livro de Feller, na seção Gaussians, é mostrado para cada que que é a densidade de um normal padrão. Existem limites semelhantes no artigo da Wikipedia para "função Q" também.Φ z>0
Fora isso, e o que outras pessoas disseram, você também pode tentar usar o Binomial diretamente, talvez com alguns Stirling.
(*) Algumas afirmações mais recentes da desigualdade de Slud deixam de fora algumas dessas condições; Eu reproduzi o do jornal de Slud.
fonte
O Teorema de Moivre-Laplace mostra que variáveis como, depois de ser adequadamente normalizado e sob certas condições, convergirá na distribuição para uma distribuição normal. Isso é suficiente se você deseja limites inferiores constantes.|T∩S1|
Para limites inferiores como , você precisa de uma ferramenta um pouco mais fina. Aqui está uma referência que eu conheço (mas apenas por acidente - nunca tive a oportunidade de usar essa desigualdade). Alguns limites inferiores explícitos das probabilidades caudais das distribuições binomiais são dados no Teorema 1.5 do livro Gráficos Aleatórios de Béla Bollobás, Cambridge, 2ª edição, onde referências adicionais são dadas a Uma introdução à probabilidade e suas aplicações por Feller e Foundations of Probability por Rényi.n−c
fonte
O Teorema Generalizado de Littlewood-Offord não é exatamente o que você deseja, mas fornece o que eu considero um "Chernoff reverso", mostrando que é improvável que a soma de variáveis aleatórias caia dentro de um pequeno intervalo em torno de qualquer valor específico (incluindo a expectativa). Talvez seja útil.
Formalmente, o teorema é o seguinte.
Teorema generalizado de Littlewood-Offord : Seja e sejam números reais tais que para deixe serem variáveis aleatórias independentes que possuem valores zero e um. Para , suponha que para todos os . Então, para qualquer , Onde é uma constante, dependendo apenas da .a1,…,an s>0 |ai|≥s 1≤i≤n X1,…,Xn 0<p≤12 p≤Pr[Xi=0]≤1−p 1≤i≤n r∈R
fonte
O expoente no limite padrão de Chernoff, como declarado na Wikipedia, é pequeno para variáveis aleatórias com valor de 1/1. Deixe que e deixar ser uma sequência de variáveis aleatórias independentes de tal modo que para cada , e . Então, para cada ,0<p<1 X1,X2,… i Pr[Xi=1]=p Pr[Xi=0]=1−p ε>0
Aqui, , que é a divergência de Kullback-Leibler entre Bernoulli variáveis com os parâmetros e .D(x∥y)=xlog2(x/y)+(1−x)log2((1−x)/(1−y)) x y
Como mencionado, o limite superior da desigualdade acima é comprovado na Wikipedia ( https://en.wikipedia.org/wiki/Chernoff_bound ) sob o nome "Teorema de Chernoff-Hoeffding, forma aditiva". O limite inferior pode ser comprovado usando, por exemplo, o "método dos tipos". Veja Lema II.2 em [1]. Além disso, isso é abordado no livro clássico sobre teoria da informação por Cover e Thomas.
[1] Imre Csiszár: O método dos tipos. Transações IEEE sobre Teoria da Informação (1998). http://dx.doi.org/10.1109/18.720546
fonte