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$.
 A: 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:


*

*We can take $c = 2$ even in the case that $p = p_m > 0$ for all $m$.

*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. 

*Coupon collecting is also related to the birthday problem. For more on this connection, here's an interesting question with several different answers.

A: 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.
A: With $c\ge 2$, $0<r=1/c <1$; with $x=-p_1 \ge -1$ applying Bernoulli's inequality we actually obtain $b=1−(1−p_1)^{1/c}\ge p_1/c$.
