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)?
Best Answer
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}$.