Chernoff reverso ligado

31

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 .X1,X2,,Xnμ=E[i=1nXi]Pr[i=1nXi(1+δ)μ]f(μ,δ,n)f

Ashwinkumar BV
fonte
1
Seu exemplo está pedindo demais: com , um limite Chernoff padrão mostra que e \ Pr [| T \ cap S_2 | \ sqrt {1.1} \ leq n ^ {1/3}] estão no máximo \ exp (-cn ^ { 1/3}) para alguns c . p=n2/3Pr[|TS1|1.1n1/3]Pr[|TS2|1.1n1/3]exp(cn1/3)c
Colin McQuillan
Você está certo, fiquei confuso sobre qual termo em chernoff bound tem o quadrado. Mudei a questão para refletir um limite mais fraco. Eu não acho que isso me ajudará no meu aplicativo atual, mas pode ser interessante por outros motivos.
Ashwinkumar BV 25/11/12

Respostas:

28

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) Seja X a média de k variáveis ​​independentes, 0/1 aleatórias (rv). Para qualquer ϵ(0,1/2] e p(0,1/2] , assumindo ϵ2pk3 ,

(i) Se cada rv é 1 com probabilidade no máximo p , então

Pr[X(1ϵ)p]  exp(9ϵ2pk).

(ii) Se cada rv for 1 com probabilidade pelo menos p , então

Pr[X(1+ϵ)p]  exp(9ϵ2pk).

Prova. Usamos a seguinte observação:

Reivindicação 1. Se , 1k1(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)!

2πk(ke)k2π(e)  2π(k)(ke)kexp(112k+1112112(k))
  12π(k)(kk)ke1.

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 pPr[X(1ϵ)p]i=0(1ϵ)pkPr[X=i/k]Pr[X=i/k]=(ki)pi(1p)ki

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 =(12ϵ)pk+1iPr[X=/k](ϵpk2)Pr[X=/k]

(ϵpk2)Pr[X=/k]  exp(9ϵ2pk).

As suposições e fornecem ; portanto, o lado esquerdo acima é pelo menos . Usando a Reivindicação 1, para vincular , isso é pelo menos onde e ϵ2pk3ϵ1/2ϵpk623ϵpk(k)p(1p)k(k)ABA=23eϵpk/2πB=(k)(kk)kp(1p)k.

Para finalizar, mostramos e .Aexp(ϵ2pk)Bexp(8ϵ2pk)

Reivindicação 2. Aexp(ϵ2pk)

Prova da reivindicação 2. As suposições e implicam (i) .ϵ2pk3ϵ1/2pk12

Por definição, . Por (i), . Assim, (ii) .pk+1pk121.1pk

Substituir o lado direito de (ii) para em fornece (iii) .AA23eϵpk/2.2π

A suposição, , implica , que com (iii) fornece (iv) .ϵ2pk3ϵpk3A23e3/2.2π0.1

A partir de , segue-se que (v) .ϵ2pk3exp(ϵ2pk)exp(3)0.04

(iv) e (v) juntos dão a reivindicação. QED

Reivindicação 3. .Bexp(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ϵBexp(2δ2pk)1/

pk(k(1p)k)k/1  exp(2δ2pk).
=(1δ)pk
(1δ)(1+δp1p)1(1δ)p1  exp(2δ21δ).
Tomando o logaritmo de ambos os lados e usando duas vezes, ele permanecerá contanto que O lado esquerdo acima simplifica para , que é menor que porque . QEDln(1+z)z
δ+δp1p(1(1δ)p1)  2δ21δ.
δ2/(1p)(1δ)2δ2/(1δ)p1/2

As reivindicações 2 e 3 implicam . Isso implica parte (i) do lema.ABexp(ϵ2pk)exp(8ϵ2pk)

Prova do Lema 1 Parte (ii). Sem perda de generalidade, assuma que cada variável aleatória é com probabilidade exatamente .1p

Nota . Corrija .Pr[X(1+ϵ)p]=i=(1ϵ)pknPr[X=i/k]^=(1+2ϵ)pk1

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(ϵpk2)Pr[X=^/k]exp(9ϵ2pk)^δδ^^=(1+δ^)pk

Neal Young
fonte
Vários [erros de processamento matemático] s - alguma chance de corrigi-los?
Aryeh 12/01
Essas expressões matemáticas costumavam exibir muito bem. Por alguma razão, o comando \ choose não está funcionando no mathjax. Nem é \ binom. Por exemplo, $ a \ escolha b $ fornece . Presumivelmente, esse é um erro na configuração do mathjax. Esperamos que esteja consertado em breve. Enquanto isso, veja o Lema 5.2 no apêndice de arxiv.org/pdf/cs/0205046v2.pdf ou cs.ucr.edu/~neal/Klein15Number . (ab)
Neal Young
22

O teorema de Berry-Esseen pode fornecer limites mais baixos à probabilidade da cauda, ​​desde que sejam maiores que .n1/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 ,kX

Pr[|X|>=12(E[Xk])1/k]E[Xk]24E[X2k]

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.Xnn±1Ω(n)

Sasho Nikolov
fonte
14

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.

Desigualdade de lamas *. Seja iid extraído de um Bernoulli rv com , e seja dado o inteiro . Se (a) e , ou (b) , então que é o cdf de um padrão normal.{Xi}i=1nE(X1)=pknp1/4npknpkn(1p)

Pr[iXik]1Φ(knpnp(1p)),
Φ

(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

z1+z2φ(z)<1Φ(z)<1zφ(z),
φ

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.

matus
fonte
7

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.|TS1|

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.nc

Colin McQuillan
fonte
4

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,,ans>0|ai|s1inX1,,Xn0<p12pPr[Xi=0]1p1inrR

Pr[ri=1naiXi<r+s]cpn
cpp
Lev Reyzin
fonte
3
Pode ser útil que outras pessoas saibam que esse tipo de resultado também é conhecido como "desigualdade de bolas pequenas" e Nguyen e Vu têm uma ótima pesquisa pessoal.math.osu.edu/nguyen.1261/cikk/LO-survey.pdf . Minha perspectiva aqui difere um pouco da sua. Penso em um "Chernoff reverso" vinculado como fornecendo uma estimativa mais baixa da massa de probabilidade da bola pequena em torno de 0. Penso em uma desigualdade de bola pequena dizendo qualitativamente que a probabilidade de bola pequena é maximizada pela bola em 0. Os limites inversos de Chernoff são geralmente mais fáceis de provar do que as desigualdades com pequenas bolas.
Sasho Nikolov
3

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<1X1,X2,iPr[Xi=1]=pPr[Xi=0]=1pε>0

2D(p+εp)nn+1Pr[i=1nXi(p+ε)n]2D(p+εp)n.

Aqui, , que é a divergência de Kullback-Leibler entre Bernoulli variáveis ​​com os parâmetros e .D(xy)=xlog2(x/y)+(1x)log2((1x)/(1y))xy

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

JWM
fonte
Também vale a pena notar que e, no caso comum de é . Isso mostra que quando o limite típico é nítido. (E quando para ). D(p+δpp)=p22pδ2+O(δ3)p=1/212δ2+O(δ4)δ=O(n1/3)eCδ2δ=O(n1/4)p=1/2
Thomas Ahle