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)?
  • 1
    $\begingroup$ $M-m$ follows negative binomial distribution and by CLT $\frac {M-2m}{\sqrt{2m}}\to N(0,1)$ which will give you asymptotic bounds. $\endgroup$ – A.S. Dec 8 '15 at 9:37
  • $\begingroup$ @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? $\endgroup$ – Erel Segal-Halevi Dec 8 '15 at 9:46
  • 1
    $\begingroup$ $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? $\endgroup$ – A.S. Dec 8 '15 at 9:49
  • $\begingroup$ @A.S. I want deviations that are sub-linear in $m$. Is it possible to get exponential bounds for sub-linear deviations? $\endgroup$ – Erel Segal-Halevi Dec 8 '15 at 10:09
  • $\begingroup$ 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)$. $\endgroup$ – 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}$.

  • $\begingroup$ Nice! I like the use of bounds for Binomial random variables to bound a geometric random variable. $\endgroup$ – Erel Segal-Halevi Dec 9 '15 at 6:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.