How to simplify or upperbound this summation?

Question

I am not a mathematician, so sorry for this trivial question. Is there a way to simplify or to upperbound the following summation:

$$ \sum_{i=1}^n{\exp{\left(-\frac{i^2}{\sigma^2}\right)}}.$$

Can I use geometric series?

EDIT: I have difficulty because of the power $2$, i.e if the summation would be $ \sum\limits_{i=1}^n{\exp{\left(-\frac{i}{\sigma^2}\right)}} $ then it would be easy to apply geometric series!

Answer 1

Alternative:

Since $f(x) = \exp(-x^2/\sigma^2) \searrow 0$, we can write $ \DeclareMathOperator{\diff}{\,d\!} $ \begin{align*} &\sum_1^n \exp\left(-\frac {j^2}{\sigma^2}\right) \\ &= \sum_1^n \int_{j-1}^j \exp\left(-\frac {j^2}{\sigma^2}\right)\diff x \\ &\leqslant \sum_1^n \int_{j-1}^j \exp\left(-\frac {x^2}{\sigma^2}\right) \diff x \\ &=\sigma \int_0^n \exp\left(-\frac {x^2}{\sigma^2}\right) \diff \left(\frac x \sigma \right)\\ &= \sigma \int_0^{n/\sigma} \exp(-x^2)\diff x\\ &\leqslant \sigma \int_0^{+\infty}\exp(-x^2)\diff x\\ &= \frac \sigma 2 \sqrt \pi \end{align*}

Answer 2

TL;DR: three relatively easy bounds are the numbered equations below.

You cannot directly apply the formula for the geometric series for the reason mentioned in your edit. But note that $i\geq1$, so we have $$\sum_{i=1}^n{\exp{\left(-\frac{i^2}{\sigma^2}\right)}}\leq\sum_{i=1}^n{\exp{\left(-\frac{i\cdot1}{\sigma^2}\right)}}$$ The latter, of course, is a geometric sum. Taking the sum over all $i$ (including $i=0$), we get $$(1-e^{-\sigma^{-2}})^{-1} \tag{1} \label{eqn:first}$$ The calculation for finitely many terms isn't much harder, and only differs by an exponentially decreasing factor.

If this isn't a strong enough bound, there are other techniques. If $n<\sigma$, then we can get very far elementarily. Note that $e^x\geq x+1$; dividing each side, we get $$e^{-x}\leq(1+x)^{-1}=\sum_{k=0}^{\infty}{(-x)^k}$$ if $|x|<1$. Taking $x=\left(\frac{i}{\sigma}\right)^2$, we thus obtain \begin{align*} \sum_{i=1}^n{e^{-\frac{i^2}{\sigma^2}}}&\leq\sum_{i=1}^n{\sum_{k=0}^{\infty}{\left(-\left(\frac{i}{\sigma}\right)^2\right)^k}} \\ &=\sum_{k=0}^{\infty}{(-1)^k\sum_{i=1}^n{\left(\frac{i}{\sigma}\right)^{2k}}} \tag{*} \label{eqn:star} \end{align*}

(We can interchange sums because one is finite.) Now, for all $k$, the function $\left(\frac{\cdot}{\sigma}\right)^{2k}$ is increasing on $[0,\infty)$; we thus have $$\int_0^n{\left(\frac{i}{\sigma}\right)^{2k}\,di}\leq\sum_{i=1}^n{\left(\frac{i}{\sigma}\right)^{2k}}\leq\left(\frac{n}{\sigma}\right)^{2k}+\int_1^n{\left(\frac{i}{\sigma}\right)^{2k}\,di}$$ Evaluating the integrals and simplifying, we have $$0\leq\sum_{i=1}^n{\left(\frac{i}{\sigma}\right)^{2k}}-\frac{n}{2k+1}\left(\frac{n}{\sigma}\right)^{2k}\leq\left(\frac{n}{\sigma}\right)^{2k}\left(1-\frac{1}{(2k+1)n^{2k}}\right)$$

Substituting into $\eqref{eqn:star}$, we get \begin{align*} \sum_{i=1}^n{e^{-\frac{i^2}{\sigma^2}}}&\leq\sum_{k=0}^{\infty}{\frac{(-1)^kn}{2k+1}\left(\frac{n}{\sigma}\right)^{2k}}-\sum_{j=0}^{\infty}{\left(\frac{n}{\sigma}\right)^{4j+2}\left(1-\frac{1}{(4j+3)n^{4j+2}}\right)} \\ &\leq\sum_{k=0}^{\infty}{\frac{(-1)^kn}{2k+1}\left(\frac{n}{\sigma}\right)^{2k}}-\sum_{j=0}^{\infty}{\left(\frac{n}{\sigma}\right)^{4j+2}} \\ &=\sigma\tan^{-1}{\left(\frac{n}{\sigma}\right)}-\frac{\left(\frac{n}{\sigma}\right)^2}{1-\left(\frac{n}{\sigma}\right)^4}\hspace{4em}(n<\sigma) \tag{2} \end{align*}

Finally, for the general case we can achieve a slight improvement on $\eqref{eqn:first}$ via the theory of majorization. $\{x_i\}_{i=1}^n\mapsto\sum_{i=1}^n{\exp{\left(-\frac{x_i}{\sigma^2}\right)}}$ is convex and symmetric in its arguments, hence Schur-convex. Let $b_i=i^2$ and $a_i=\left(\frac{2n-1}{3}\right)i$. Clearly, for all $m\leq n$, we have $$\sum_{i=1}^m{a_i}=\frac{m(m-1)}{2}\cdot\frac{2n-1}{3}\geq\frac{m(m-1)(2m-1)}{6}=\sum_{i=1}^m{b_i}$$ with equality if $m=n$. Thus $\vec{a}$ majorizes $\vec{b}$, so \begin{align*} \sum_{i=1}^n{\exp{\left(-\frac{i^2}{\sigma^2}\right)}}&=\sum_{i=1}^n{\exp{\left(-\frac{b_i}{\sigma^2}\right)}} \\ &\leq\sum_{i=1}^n{\exp{\left(-\frac{a_i}{\sigma^2}\right)}} \\ &=\sum_{i=1}^n{\exp{\left(-\frac{(2n-1)i}{3\sigma^2}\right)}} \\ &\leq\sum_{i=0}^{\infty}{\exp{\left(-\frac{(2n-1)i}{3\sigma^2}\right)}} \\ &\leq\left(1-\exp{\left(\frac{2n-1}{3\sigma^2}\right)}\right)^{-1} \tag{3} \end{align*}

Answer 3

There's a rather trivial upper bound that $\frac{-i^2}{\sigma^2}$ is negative, so exponentiating it results in a number less than 1, so the sum is at most $n$. If you want a constant upper bound, you can upper bound it with the geometric series.

Answer 4

The matter is that $e^{-(x/ \sigma)^2}$, in the range $0 \le x < \approx \sigma$ is very steep.
So, unless $\sigma$ is quite high, you cannot get a good approximation by the integral.
But of course everything depends on the parameters into play and on the accuracy required.

Hint :

For general values of $n$ and $\sigma$ it might be interesting to take advantage of the fact that
the Fourier Transform of a Gaussian is a Gaussian itself.

Then you are taking the signal $e^{-\, (t/ \sigma)^2}$, windowing it between $0 \le t \le n/ \sigma$, taking $n$ samples of it, and after that you are taking $n$ times the average.
All these operations have a simple translation into the frequency domain.
However I do not go further not knowing whether you are acknowledged in this field, and keep this as a hint.

Also, might be interesting this identity $$ \sum\limits_{k \in \mathbb Z} {\exp \left( { - \pi \left( {k/c} \right)^2 } \right)} = c\sum\limits_{k \in \mathbb Z} {\exp \left( { - \pi \left( {k\,c} \right)^2 } \right)} $$ reported at the end of the Properties paragraph in this wikipedia article.