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$.
Best Answer
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: