Uma extensão do limite de Chernoff

12

Estou procurando uma referência (não uma prova, o que posso fazer) à seguinte extensão de Chernoff.

Deixe- X1,..,Xn são variáveis ​​aleatórias booleanas, não necessariamente independentes . Em vez disso, é garantido que Pr(Xi=1|C)<p para cadae todo eventoque depende apenas de.C { X j | j i }iC{Xj|ji}

Naturalmente, quero um limite superior em .Pr(i[n]Xi>(1+λ)np)

Desde já, obrigado!

curioso
fonte

Respostas:

25

O que você deseja é o limite de Chernoff generalizado, que assume apenas P(iSXi)p|S| para qualquer subconjunto S de índices variáveis. O último segue da sua suposição, pois para S={i1,,i|S|} ,

P(iSXi)=P(Xi1=1)P(Xi2=1|Xi1=1)P(Xi|S|=1|Xi1,...,Xi|S|1=1)p|S|
Impagliazzo e Kabanets recentemente deram uma prova alternativa do limite de Chernoff, incluindo o generalizado. Em seu artigo, você pode encontrar todas as referências apropriadas para trabalhos anteriores: http://www.cs.sfu.ca/~kabanets/papers/RANDOM2010.pdf
Dana Moshkovitz
fonte
Obrigado pelo esclarecimento! De fato, a condição deles está implícita pelo que eu tenho e por correlações negativas. Então, é de fato qualitativamente mais forte (de alguma forma, perdi esse ponto quando ouvi a conversa de Valentine). Agora, a prova do que eu preciso fica tão curta, que fico feliz em marcar minha pergunta como respondida, muito obrigado!
curioso
3
No seu caso, você pode simplesmente criar uma submartingale com suas variáveis ​​e usar a desigualdade clássica de Azuma para o mesmo efeito. Para que isso funcione, você precisa apenas de que está implícito em sua suposição. Pr[Xi=1|X1,,Xi1]<p
MCH 25/06
7

As coisas mais próximas que conheço na literatura são extensões dos limites de Chernoff para variáveis ​​aleatórias correlacionadas negativamente, por exemplo, veja isto ou aquilo . Formalmente, sua condição pode ser satisfeita sem a correlação negativa, mas a ideia é semelhante.

Como sua generalização não é difícil de provar, pode ser que ninguém tenha se incomodado em redigir.

Lev Reyzin
fonte
Você está certo, também foi o mais próximo que encontrei (em "Concentração ... para a análise de ... algoritmos"). O problema é que meu manuscrito está ficando muito longo. Eu adoraria evitar mais um spin-off, se possível. Se não, eu vou ter nenhuma escolha ...
curioso
3
são para isso que os apêndices são :) :)
Lev Reyzin
2
Ei, pessoal, isso já foi provado antes, e eu dei uma referência na minha resposta (para onde você também pode encontrar todas as outras referências relevantes).
Dana Moshkovitz 8/08
Opa - incrível. De alguma forma eu não percebi sua resposta!
Lev Reyzin
3

Uma referência alternativa poderia ser o Lema 1.19 em B. Doerr, Analisando heurísticas de pesquisa randomizada: Ferramentas da teoria da probabilidade, Teoria das heurísticas de pesquisa randomizada (A. Auger e B. Doerr, orgs.), World Scientific Publishing, 2011, pp. 1- 20

Em palavras simples, mostra que quando com probabilidade não importa o que você condiciona , em seguida satisfazem todos os limites de Chernoff-Hoeffding válidos para independência variáveis ​​aleatórias binárias com probabilidade de sucesso , respectivamente. A prova é elementar e o resultado é natural, então acho que ninguém sentiu necessidade de escrevê-la.p i X 1 , , X i - 1 X 1 , , X n Y 1 , , Y n p 1 , , p nXi=1piX1,,Xi1X1,,XnY1,,Ynp1,,pn

Benjamin Doerr
fonte