Cota de cola en la suma de variables aleatorias geométricas independientes (no idénticas)

Question

Supongamos que $X_1, \ldots , X_k$ son $k$ variables aleatorias geométricas independientes con probabilidad de éxito $p_1, \ldots, p_k$ y que $X = X_1 + \cdots + X_k$ .

El número esperado de ensayos necesarios es $$ \mathbb E[X] = \frac{1}{p_1} + \cdots + \frac{1}{p_k} \> . $$

Reclamación : Debe ser cierto que hay una constante $c>0$ (independiente de $k$ y las probabilidades de éxito $p_i$ ) tal que para cualquier $t>0$ tenemos $$ \mathbb P[X > c (\mathbb E[X] + t)] < (1 - p_\min)^t \>, $$
donde $p_\min = \min_i p_i$ .

Estaría muy agradecido por cualquier ayuda para probar esto.

Tenga en cuenta que si $p_1 = \cdots = p_k = p$ entonces $X$ es una variable aleatoria binomial negativa. En este caso, se puede demostrar la afirmación con $c=16$ a través de un límite estándar de Chernoff: El número esperado de aciertos después de $16(\frac{k}{p}+t)$ los juicios es $16(k+tp)$ y, por el límite de Chernoff, la probabilidad de que haya menos de $k<\frac{1}{2}E[X]$ éxitos es como máximo $e^{-16(k+tp)/8}$ que es menor que $e^{-2tp} < (1 - p)^t$ .

Answer 1

Supongamos sin pérdida de generalidad que $0 < p_1 \leq p_2 \leq \cdots \leq p_k$ y $X = X_1 + \cdots + X_k$ donde $X_i$ son variables aleatorias geométricas independientes con parámetro $p_i$ . Dejemos que $\mu = \mathbb E X = \sum_{m=1}^k \frac{1}{p_m}$ .

A continuación, mostramos un resultado bastante más contundente que el que se afirma en la pregunta. En particular:

Reclamación : Para cualquier $c \geq 2$ y cualquier $k$ tenemos $$\renewcommand{\Pr}{\mathbb P}\newcommand{\E}{\mathbb E} \Pr(X > c (\mu + t) ) \leq (1-p_1)^t \exp(-(2c-3)k/4) \>. $$

Prueba : Por la desigualdad de Markov aplicada a $e^{s X}$ para cualquier $s > 0$ , $$ \Pr(X > c (\mu + t) ) \leq e^{-s c t} e^{-s c \mu} \prod_{m=1}^k \E e^{s X_m} \>. $$

Es un ejercicio fácil comprobar que $$ \E e^{s X_m} = \frac{p_m e^s}{1-(1-p_m) e^s} = \Big(1-\frac{1-e^{-s}}{p_m}\Big)^{-1} $$

Dejemos que $s = -\frac{1}{c}\log(1-p_1)$ para que $e^{-sc} = (1-p_1)$ . Entonces, obtenemos que $$ \Pr(X > c (\mu + t) ) \leq (1-p_1)^t \exp( a \mu - {\textstyle\sum_{m=1}^k} \log(1-b/p_m)) \>, $$ donde $a = \log(1-p_1)$ y $b = 1-(1-p_1)^{1/c}$ .

Recordando la definición de $\mu$ y concentrándonos en el exponente del último término, necesitamos encontrar algún $c$ tal que $$ \sum_{m=1}^k \frac{a}{b}\frac{b}{p_m} - \log(1 - b/p_m) < 0 \>. $$ Dejar $c \geq 2$ y utilizando La desigualdad de Bernoulli tenemos $b = 1-(1-p_1)^{1/c} \leq p_1/c \leq p_1 / 2$ y así, en particular $b/p_m \leq 1/2$ para todos $m$ .

Ya que, para $0 < z \leq 1/2$ la desigualdad $\log(1-z) \geq -z - z^2$ se mantiene, obtenemos que $$ \sum_{m=1}^k \frac{a}{b}\frac{b}{p_m} - \log(1 - b/p_m) \leq \frac{k}{2} (\frac{a}{b} + \frac{3}{2}) \>. $$

Pero, $a = \log(1-p_1) < 0$ y $b \leq p_1 / c$ Así que $$ \frac{a}{b} \leq \frac{c\log(1-p_1)}{p_1} \leq -c \>. $$

Al juntar todo, hemos demostrado que $$ \Pr(X > c (\mu + t) ) \leq (1-p_1)^t \exp(-(2c-3)k/4) $$ como se ha reclamado.

---

Notas : Observamos lo siguiente:

1. Podemos tomar $c = 2$ incluso en el caso de que $p = p_m > 0$ para todos $m$ .
2. El caso especial en el que $p_m = m/k$ corresponde a la Problema de cobro de cupones . Hay algunas asintóticas más agudas en el caso del primer problema, así como límites superior e inferior .
3. La recogida de cupones también está relacionada con la problema de cumpleaños . Para más información sobre esta conexión, aquí hay un interesante pregunta con varias respuestas diferentes.

Answer 2

Un argumento de acoplamiento funciona muy bien aquí. Sea $X_1'$ , $\cdots$ , $X_k'$ sea $k$ variables aleatorias geométricas independientes de parámetro $p_{\min}$ . Entonces podemos acoplar la variable aleatoria $X_i$ y $X_i'$ de tal manera que $X_i \leq X_i'$ porque $p_{\min}$ es, bueno, $p_{\min}$ . También puedo elegir que todos estos acoplamientos sean independientes, lo que da como resultado un acoplamiento entre $(X_i)$ y $(X_i')$ . Este acoplamiento da a su vez un acoplamiento entre $X$ y $X' = \sum_{i=1}^k X_i'$ tal que $X \leq X'$ .

Por su argumento (que no he comprobado), lo sabemos:

$$\mathbb{P} (X' \geq 16 (\mathbb{E} (X')+t)) \leq (1-p_{\min})^t.$$

Desde $X \leq X'$ tenemos:

$$\mathbb{P} \left(X \geq 16 \frac{\mathbb{E} (X')}{\mathbb{E} (X)} \left(\mathbb{E} (X)+t\right)\right) \leq \mathbb{P} \left(X \geq 16 \left(\frac{\mathbb{E} (X')}{\mathbb{E} (X)}\mathbb{E} (X)+t\right)\right) \leq (1-p_{\min})^t.$$

Entonces podemos sustituir $\mathbb{E} (X')/\mathbb{E} (X)$ por su valor exacto.

Sin embargo, este argumento no es muy complicado y debería haber una forma de obtener mejores constantes.

Answer 3

Con $c\ge 2$ , $0<r=1/c <1$ con $x=-p_1 \ge -1$ aplicando la desigualdad de Bernoulli obtenemos realmente $b=1(1p_1)^{1/c}\ge p_1/c$ .