Why is $\sum_{t=1}^n \exp \{ -t \Delta^2\} \geq \frac{1}{\Delta^2}$? I am 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 proof, I see the following step and I wonder where it comes from.
$\sum_{t=1}^n \exp \{ -t \Delta^2\} \geq \frac{1}{\Delta^2}$
I've tried to derive it from

*

*a Taylor expansion,

*Jensen's inequality,

*summing to infinity,

but I don't see it.
Thanks!
 A: It is the other way aroud:
\begin{align*}
\sum\limits_{t = 1}^n {\exp ( - t\Delta ^2 )} & \le \sum\limits_{t = 1}^n {\int_{t - 1}^t {\exp ( - s\Delta ^2 )ds} } \\ & = \int_0^n {\exp ( - s\Delta ^2 )ds}  \le \int_0^{ + \infty } {\exp ( - s\Delta ^2 )ds}  = \frac{1}{{\Delta ^2 }}.
\end{align*}
A: This inequality is indeed obviously incorrect... there are several typos in the statement (and the proof) of Theorem 5. First thing first, it can only be true for $n \geq 1/\Delta^2$ (for smaller $n$, the regret is upper-bounded by $n\Delta$ which is itself smaller than $1/\Delta$). Also, the sum should be from $0$ up to $t-1$ (instead from $1$ up to $t$ as we wrote).
With standard computations, you then get  that regret is bigger than $\frac{1-e^{-1}}{4\Delta}$ and even bigger than   $\frac{1}{4\Delta}$ asymptotically with $n$ (as it goes to infinity).
A: $$\sum\limits_{t = 1}^n {\exp ( - t\Delta ^2 )}<\sum\limits_{t = 1}^\infty {\exp ( - t\Delta ^2 )}=\sum\limits_{t = 1}^\infty {[\exp ( - \Delta ^2 )]^t}=\frac{\exp(-\Delta^2)}{1-\exp(-\Delta^2)}=\frac1{\exp\Delta^2-1}\\ <\frac1{\Delta^2}.$$
