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- $X_1,..,X_n$ são variáveis aleatórias booleanas, não necessariamente independentes . Em vez disso, é garantido que $Pr(X_i=1|C)<p$ para cadae todo eventoque depende apenas de. $i$ $C$ $\{X_j|j\neq i\}$

Naturalmente, quero um limite superior em . $\Pr\left(\sum_{i\in[n]}X_i>(1+\lambda)np\right)$

Desde já, obrigado!

reference-request pr.probability chernoff-bound curioso
fonte

25

O que você deseja é o limite de Chernoff generalizado, que assume apenas $P(\bigwedge_{i\in S} X_{i}) \leq p^{|S|}$ para qualquer subconjunto S de índices variáveis. O último segue da sua suposição, pois para $S=\{i_1,\ldots,i_{|S|}\}$ ,

P (\underset{i \in S}{⋀} X_{i}) = P (X_{i_{1}} = 1) P (X_{i_{2}} = 1 | X_{i_{1}} = 1) \dots P (X_{i_{| S |}} = 1 | X_{i_{1}}, . . ., X_{i_{| S | - 1}} = 1) \leq p^{| S |}

$P(\bigwedge_{i\in S} X_{i}) = P(X_{i_1} = 1)P(X_{i_2}=1|X_{i_1}=1)\cdots P(X_{i_{|S|}}=1|X_{i_1},...,X_{i_{|S|-1}}=1)\leq 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.

P r [X_{i} = 1 | X_{1}, \dots, X_{i - 1}] < p

$Pr[X_i=1|X_1, \ldots, X_{i-1}] < 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. $X_i=1$ $p_i$ $X_1, \dots, X_{i-1}$ $X_1, \ldots, X_n$ $Y_1, \ldots, Y_n$ $p_1, \ldots, p_n$

Benjamin Doerr
fonte

Uma extensão do limite de Chernoff

Respostas: