# Tail bound on the sum of independent (non-identical) geometric random variables

Suppose $X_1, \ldots , X_k$ are $k$ independent geometric random variables with success probability $p_1, \ldots, p_k$ and let $X = X_1 + \cdots + X_k$.

The expected number of trials needed is $$\mathbb E[X] = \frac{1}{p_1} + \cdots + \frac{1}{p_k} \> .$$

Claim: It should be true that there is a constant $c>0$ (independent of $k$ and the success probabilities $p_i$) such that for any $t>0$ we have $$\mathbb P[X > c (\mathbb E[X] + t)] < (1 - p_\min)^t \>,$$
where $p_\min = \min_i p_i$.

I would be very thankful for any help in proving this.

Note that if $p_1 = \cdots = p_k = p$ then $X$ is a negative binomial random variable. In this case, one can prove the claim with $c=16$ via a standard Chernoff bound: The expected number of successes after $16(\frac{k}{p}+t)$ trials is $16(k+tp)$ and, by the Chernoff bound, the probability that there are less than $k<\frac{1}{2}E[X]$ successes is at most $e^{-16(k+tp)/8}$ which is less than $e^{-2tp} < (1 - p)^t$.

-
To help with intuition of the claim: $X_i$ is the number of tosses we have to make with coin $i$ (with success probability $p_i$) to get the first success and $X$ is the total number of trials needed to get one success with each of $k$ different coins. The claim then states that the probability that one needs more than ($c$ times) the expected number of trials plus $t$ extra ones gets exponentially smaller with $t$ and is essentially as unlikely as having thrown the worst coin $t$ times without getting one success. – User3378 Feb 18 '12 at 18:04
I've merged your two accounts. Cheers. – Willie Wong Feb 20 '12 at 11:54

Assume without loss of generality that $0 < p_1 \leq p_2 \leq \cdots \leq p_k$ and $X = X_1 + \cdots + X_k$ where $X_i$ are independent geometric random variables with parameter $p_i$. Let $\mu = \mathbb E X = \sum_{m=1}^k \frac{1}{p_m}$.

Below, we show a considerably stronger result than that claimed in the question. In particular:

Claim: For any $c \geq 2$ and any $k$, we have $$\renewcommand{\Pr}{\mathbb P}\newcommand{\E}{\mathbb E} \Pr(X > c (\mu + t) ) \leq (1-p_1)^t \exp(-(2c-3)k/4) \>.$$

Proof: By Markov's inequality applied to $e^{s X}$, for any $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} \>.$$

It is an easy exercise to check that $$\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}$$

Let $s = -\frac{1}{c}\log(1-p_1)$ so that $e^{-sc} = (1-p_1)$. Then, we get that $$\Pr(X > c (\mu + t) ) \leq (1-p_1)^t \exp( a \mu - {\textstyle\sum_{m=1}^k} \log(1-b/p_m)) \>,$$ where $a = \log(1-p_1)$ and $b = 1-(1-p_1)^{1/c}$.

Recalling the definition of $\mu$ and concentrating on the exponent of the last term, we need to find some $c$ such that $$\sum_{m=1}^k \frac{a}{b}\frac{b}{p_m} - \log(1 - b/p_m) < 0 \>.$$ Letting $c \geq 2$ and using Bernoulli's inequality, we have $b = 1-(1-p_1)^{1/c} \leq p_1/c \leq p_1 / 2$ and so, in particular $b/p_m \leq 1/2$ for all $m$.

Since, for $0 < z \leq 1/2$, the inequality $\log(1-z) \geq -z - z^2$ holds, we get that $$\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}) \>.$$

But, $a = \log(1-p_1) < 0$ and $b \leq p_1 / c$, so $$\frac{a}{b} \leq \frac{c\log(1-p_1)}{p_1} \leq -c \>.$$

Putting everything together, we have shown that $$\Pr(X > c (\mu + t) ) \leq (1-p_1)^t \exp(-(2c-3)k/4)$$ as claimed.

Notes: We observe the following:

1. We can take $c = 2$ even in the case that $p = p_m > 0$ for all $m$.
2. The special case where $p_m = m/k$ corresponds to the coupon collector problem. There are some sharper asymptotics in the case of the former problem as well as upper and lower bounds.
3. Coupon collecting is also related to the birthday problem. For more on this connection, here's an interesting question with several different answers.
-
Great and detailed answer. Thanks, cardinal! – User3378 Feb 20 '12 at 14:59
I think Bernoulli's inequality is being used incorrectly here. For $0 \leq x \leq 1$ we have $(1-p)^x \leq 1-px$ so $px \leq 1-(1-p)^x$. – okintheory May 6 at 1:46

A coupling argument works nicely nicely here. Let $X_1'$, $\cdots$, $X_k'$ be $k$ independent geometric random variables of parameter $p_{\min}$. Then we can couple the random variable $X_i$ and $X_i'$ in such a way that $X_i \leq X_i'$ because $p_{\min}$ is, well, $p_{\min}$. I can also choose all these couplings to be independent, which gives be a coupling between $(X_i)$ and $(X_i')$. This coupling in turn gives a coupling between $X$ and $X' = \sum_{i=1}^k X_i'$ such that $X \leq X'$.

By your argument (which I didn't check), we know that:

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

Since $X \leq X'$, we have:

$$\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.$$

Then we can replace $\mathbb{E} (X')/\mathbb{E} (X)$ by its exact value.

This argument is not very involved, and there should be a way to get better constants, however.

-
Thanks, D.Thomine. Unfortunately in your solution we get $c = 16\frac{E(X')}{E(X)}$ which makes the constant $c$ depend on $k$ and the success probabilities $p_i$. I added a clarifying sentence to the question. – User3378 Feb 20 '12 at 15:04