Una extensión del límite de Chernoff

13

Estoy buscando una referencia (no una prueba que pueda hacer) a la siguiente extensión de Chernoff.

Dejar que serán variables aleatorias booleanas, no necesariamente independientes . En cambio, se garantiza que para cada y cada evento que solo depende de . $X_1,..,X_n$ $Pr(X_i=1|C)<p$ $i$ $C$ $\{X_j|j\neq i\}$

$\Pr\left(\sum_{i\in[n]}X_i>(1+\lambda)np\right)$

¡Gracias por adelantado!

reference-request pr.probability chernoff-bound curioso
fuente

26

Lo que desea es el límite de Chernoff generalizado, que solo supone para cualquier subconjunto S de índices variables. Esto último se deduce de su suposición, ya que para , Impagliazzo y Kabanets recientemente dieron una prueba alternativa del límite de Chernoff, incluida la generalizada. En su documento, puede encontrar todas las referencias apropiadas a trabajos anteriores: http://www.cs.sfu.ca/~kabanets/papers/RANDOM2010.pdf $P(\bigwedge_{i\in S} X_{i}) \leq p^{|S|}$ $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|}$

Dana Moshkovitz
fuente

¡Gracias por la aclaración! De hecho, su condición está implicada tanto por lo que tengo como por las correlaciones negativas. Entonces, es de hecho cualitativamente más fuerte (de alguna manera me perdí ese punto cuando escuché la charla de Valentine). Ahora la prueba de lo que necesito se vuelve tan corta que con gusto marco mi pregunta como contestada, ¡muchas gracias!

curioso

3

En su caso, simplemente puede crear un sub-martingala a partir de sus variables y usar la desigualdad clásica de Azuma para el mismo efecto. Para que esto funcione, solo necesita que que implica su suposición.

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

$Pr[X_i=1|X_1, \ldots, X_{i-1}] < p$

MCH

7

Las cosas más cercanas que conozco en la literatura son extensiones de los límites de Chernoff a variables aleatorias negativamente correlacionadas, por ejemplo, ver esto o esto . Formalmente, su condición podría satisfacerse sin la correlación negativa, pero la idea es similar.

Debido a que su generalización no es difícil de probar, es posible que nadie se haya molestado en escribirla.

Lev Reyzin
fuente

Tienes razón, eso también fue lo más cercano que encontré (en "Concentración ... para el Análisis de ... Algoritmos"). La cuestión es que mi manuscrito se está alargando demasiado, me encantaría evitar otro spin-off, si es posible. Si no es así, voy a tener más remedio ...

curiosa

3

para eso están los Apéndices :)

Lev Reyzin

2

Hola, chicos, ya se demostró antes, y di una referencia en mi respuesta (a donde también pueden encontrar todas las demás referencias relevantes).

Dana Moshkovitz

Vaya, genial. ¡De alguna manera no noté tu respuesta!

Lev Reyzin

3

Una referencia alternativa podría ser Lemma 1.19 en B. Doerr, Análisis de heurísticas de búsqueda aleatoria: Herramientas de la teoría de probabilidad, Teoría de la heurística de búsqueda aleatoria (A. Auger y B. Doerr, eds.), World Scientific Publishing, 2011, pp. 1- 20)

En palabras simples, muestra que cuando con probabilidad sin importar lo que condicione , entonces satisfacen todos los límites de Chernoff-Hoeffding que son válidos para independientes variables aleatorias binarias con probabilidad de éxito , respectivamente. La prueba es elemental y el resultado es natural, así que supongo que nadie sintió la necesidad de escribirlo. $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
fuente

Una extensión del límite de Chernoff

Respuestas: