# Tail bound for sum of geometric random variables

Consider the following experimenet. We go over the integers $1,2,\dots,$ in order, selecting each integer independently with probability $1/2$ and stopping after $m$ integers have been selected. Let $M$ be the largest selected integer. I am looking for a tight bound on $M$ which is true with high probability (- the probability goes to 1 when $m\to\infty$). Here is what I have so far:

$M$ is the sum of $m$ independent geometric random variables with probability $1/2$. Each such random variable has expected value 2 and variance 2. Hence:

$$\operatorname{E}[M] = 2m, \operatorname{Var}[M]=2m$$

By Chebyshev's inequality, for every constant $a>0$:

$$Pr\left[|M-2m| \leq a \right] \geq 1-\frac{2m}{a^2}$$

Taking $a=m^{2/3}$ gives:

$$Pr\left[2m-m^{2/3} \leq M \leq 2m + m^{2/3} \right] \geq 1-\frac{2}{m^{1/3}}$$

My questions are:

• Is this bound correct?
• Is there a better bound (- a tighter sub-linear bound around $2m$ that is true with a higher probability)?
• $M-m$ follows negative binomial distribution and by CLT $\frac {M-2m}{\sqrt{2m}}\to N(0,1)$ which will give you asymptotic bounds. – A.S. Dec 8 '15 at 9:37
• @A.S. the CLT is about convergence in distribution... how can I use this to get specific expressions to the probability that $M$ is bounded, such as the one in the question? – Erel Segal-Halevi Dec 8 '15 at 9:46
• $P(|M_m-2m|<a_m)\to 0$ for any $a_m^2/m\to\infty$ as you have also shown with Chebyshev's inequality. This + CLT's result (which gives an an EXACT (asymptotic) expression for probability of deviation) is as good as you will get. Do you recognize that convergence in distribution controls probability of deviation? – A.S. Dec 8 '15 at 9:49
• @A.S. I want deviations that are sub-linear in $m$. Is it possible to get exponential bounds for sub-linear deviations? – Erel Segal-Halevi Dec 8 '15 at 10:09
• Yes, you can. $P(M_n-2n>k)=P(B(k+2n,\frac 1 2)<n)=P(B(k+2n,\frac 1 2)-\frac 1 2(k+2n)<-\frac 1 2 k)$ and you can apply a concentration inequality for the binomial (say, Hoeffding's) for $k=\omega(n^{\frac 1 2})$. The bound will be of type $\exp(-2k^2/n)$. – A.S. Dec 8 '15 at 11:35

Viewing $M_n$ as a sequence of Bernoulli trials until we get $n$ failures, we get
$$P(M_n-2n>k)=P(B(k+2n,\frac 1 2)<n)=P(B(k+2n,\frac 1 2)-\frac 1 2(k+2n)<-\frac 1 2 k)\le \exp\left(-\frac {k^2}{2(2n+k)}\right)$$ by Hoeffding's bound. Similarly for $k\le 2n$ $$P(M_n-2n<-k)=P(B(2n-k,\frac 1 2)>n)\le \exp\left(-\frac {k^2}{2(2n-k)}\right)$$ We can nicely combine the two for $k\le 2n$ into $$P(|M_n-2n|>k)\le 2\exp\left(-\frac {k^2}{4n}\right)$$ due to concavity of $e^{-1/x}$.