9
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – User3378
    Feb 18, 2012 at 18:04
  • $\begingroup$ I've merged your two accounts. Cheers. $\endgroup$ Feb 20, 2012 at 11:54

3 Answers 3

2
$\begingroup$

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.
$\endgroup$
3
  • $\begingroup$ Great and detailed answer. Thanks, cardinal! $\endgroup$
    – User3378
    Feb 20, 2012 at 14:59
  • 1
    $\begingroup$ 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$. $\endgroup$
    – okintheory
    May 6, 2016 at 1:46
  • $\begingroup$ The main claim is wrong. Suppose $p_1=1/(k-1)$ and $p_2 = p_k = 1$. Then $\mu = 1/p_1 + (k-1) = 2/p_1$. To be concrete take $c=2$. The claimed bound implies $P(X_1 \geq 3/p_1) \leq \exp(-k/4)$. The LHS is constant while the RHS is exponentially small. (Note: my student Saeed came up with this but his reputation is too low to comment.) $\endgroup$ Jan 12, 2017 at 16:01
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – User3378
    Feb 20, 2012 at 15:04
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .