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!

  • 3
    Don't be sorry for the question! The only way to get better as mathematician is to ask questions. (See also the first annotation to this post) – Jacob Manaker Sep 18 at 16:18
  • 2
    Seems that you could try the integral $\int_0^\infty \exp(-x^2)\,\mathrm dx$ to bound that. – xbh Sep 18 at 16:26
  • tinyurl.com/y76n9loh (wolframalpha) gives a closed form for the infinite sum involving the elliptic theta function. – barrycarter Sep 19 at 23:46
up vote 8 down vote accepted

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*}

  • 2
    Nicely done! Sometimes simplest is best. – Jacob Manaker Sep 18 at 17:54
  • brilliant answer, thanks – user8003788 Sep 19 at 7:39
  • @user8003788 You are welcome. Glad to help you out! – xbh Sep 19 at 7:43
  • @JacobManaker Thanks for compliment! – xbh Sep 19 at 7:43

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*}

  • Great detailed work..I considered previously the first answer but I thought it would be better if I can get a stronger bound.Thanks a lot – user8003788 Sep 19 at 7:42

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.

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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