Desigualdade do tipo Chernoff para variáveis ​​aleatórias independentes em pares

Desigualdades do tipo Chernoff são usadas para mostrar que a probabilidade de que uma soma de variáveis ​​aleatórias independentes se desvie significativamente de seu valor esperado é exponencialmente pequena no valor esperado e no desvio. Existe uma desigualdade do tipo Chernoff para qualquer soma de variáveis ​​aleatórias independentes em pares ? Em outras palavras, existe um resultado que mostra o seguinte: a probabilidade de uma soma de variáveis ​​aleatórias independentes em pares se desviar do valor esperado é exponencialmente pequena no valor esperado e no desvio?

A independência pareada não é suficiente para um tipo de Chernoff ligado à expectativa.

$poly(n)$$n$$1$$1/2$$n/2$$poly(n)$$v$$1/poly(n)$$1/exp(n)$

Para uma referência a essa amostra de construção de espaço, consulte as páginas 11-12 nesta pesquisa .

Se você tiver independência pareada, poderá vincular a variação da soma e, assim, obter uma concentração vinculada usando a desigualdade de Chebyshev.

Existem todos os tipos de resultados desse tipo no livro Dubhashi-Panconesi . Uma referência padrão desse tipo é a obra de Schmidt, Siegel e Srinivasan, de 1993, intitulada (apropriadamente): " Chernoff-Hoeffding limita para aplicações com independência limitada "