Why is $\sum_{t=0}^{n-1} \exp \{ -t \Delta^2 \} \geq \frac{1-e^{-1}}{\Delta^2}$ for $n \geq \frac{1}{\Delta^2}$?

Question

This is a follow-up question on this question. I was reading a paper about lower bounds for bandit problems (https://arxiv.org/abs/1302.1611). In Theorem 5, they prove a lower bound with an example problem with two arms. In the comments/answers of the previous question on stackexchange, it turned out that the theorem in the paper contains a few errors: the lower bound in Thrm. 5 should be $\frac{1-e^{-1}}{4\Delta}$, is should only hold for $n \geq 1/\Delta^2$, and the sum should start at 0.

I still don't understand the following step in the corrected proof:

$\sum_{t=0}^{n-1} \exp \{ -t \Delta^2 \} \geq \frac{1-e^{-1}}{\Delta^2}$ for $n \geq 1 / \Delta^2$.

I've tried to use:

• Jensen's inequality,
• Taylor expansion,
• infinite sums, all leading to an upper bound in stead of a lower bound.

Answer 1

Use$$\sum_{t=0}^{n-1}\exp(-t\Delta^2)=\frac{1-e^{-n\Delta^2}}{1-e^{-\Delta^2}}\ge\frac{1-e^{-1}}{1-e^{-\Delta^2}}\ge\frac{1-e^{-1}}{\Delta^2}.$$

Answer 2

Let $\delta = \Delta^2$ for short.

The sum equals $\frac{1 - e^{-n \delta}}{1 - e^{- \delta}}$. Since $n \delta \ge 1$, the top is $\ge 1 - e^{-1}$. The bottom is a concave function of $\delta$ and thus below its tangent line at $\delta = 0$, i.e. $1 - e^{-\delta} \le \delta$ for all $\delta$. Put it together and the desired inequality follows.