# How to bound the summation by an integral

For the distribution I have, I bounded the normalizing constant $$c$$ as $$c\leq \sum_{x=1}^z x^d \exp(−x^2/\sigma^2)$$ where $$z$$ and $$d$$ are finite and I don't know the relation between $$x$$ and $$\sigma^2$$.

I would like to simplify the bound so I tried considering the geometric series but I couldn't apply it because of the term $$x^d$$. After that, I used Euler-Maclaurin formula in order to approximate the summation to an integral but it didn't work.

The bound looks like the expected value of a normal random variable to the power $$d$$, $$E(X^d)$$, but I don't know where to start and how to deal with the summation to transform it to an integral in order to approximate "bound" the constant $$c$$. Also it would be possible to bound it by another way so many thanks for any help, hint or reference.

• Bluntly, the summand is bounded by $z^d e^{-1/\sigma^2}$, which makes the total sum bounded by $z^{d+1} e^{-1/\sigma^2}$. Granted this is not very sharp. Maybe you are looking for a specific kind of bound?
– Ϛ .
Oct 29, 2018 at 13:09
• @Ϛ. so I don't need to approximate by the normal distribution? can you give more details Oct 29, 2018 at 13:16
• Well I don't exactly know where you're heading, except trying to bound $c$. Since you know $1 \leq x \leq z$ and $exp$ is increasing, that's all I used.
– Ϛ .
Oct 29, 2018 at 13:47

I really prefer the usual conventions for integer variables, so I will consider:

$$S_m=\sum_{n=1}^m n^d \exp(−n^2/\sigma^2)$$

We have a general inequality for a monotone decreasing function:

$$\int _{N}^{M+1}f(x)\,dx\leq \sum _{n=N}^{M}f(n)\leq f(N)+\int _{N}^{M}f(x)\,dx$$

Note that our function is not monotone for $$d>0$$, it has a maximum:

$$f(x)=x^d e^{-x^2/\sigma^2}$$

$$f'(x)=\left(d -\frac{2x^2}{\sigma^2}\right)x^{d-1} e^{-x^2/\sigma^2}$$

So we have: $$x_0= \sigma\sqrt{d/2}$$

$$n_0=\lceil \sigma\sqrt{d/2} \rceil$$

Thus, we need to write for $$n_0>1$$:

$$S_m=\sum_{n=1}^{n_0-1} n^d \exp(−n^2/\sigma^2)+\sum_{n=n_0}^m n^d \exp(−n^2/\sigma^2)$$

The latter sum has the function decreasing monotonely, and we can use the bound:

$$S_m \leq \sum_{n=1}^{n_0} n^d \exp(−n^2/\sigma^2)+\int_{n_0}^{m} x^d \exp(−x^2/\sigma^2) dx$$

Thus:

$$c \leq \sum_{n=1}^{n_0} n^d \exp(−n^2/\sigma^2)+\int_{n_0}^{m} x^d \exp(−x^2/\sigma^2) dx$$

$$n_0=\lceil \sigma\sqrt{d/2} \rceil$$

Mind, this is definitely not a simplification of the bound, as the integral can only be expressed in terms of incomplete Gamma function for the general $$d$$.

But if $$m$$ is very large, we can approximate the integral by $$\int_{n_0}^\infty x^d \exp(−x^2/\sigma^2) dx$$, and write:

$$c \leq \sum_{n=1}^{n_0} n^d \exp(−n^2/\sigma^2)+\int_{n_0}^\infty x^d \exp(−x^2/\sigma^2) dx$$

If, in addition, $$n_0<1$$ (it depends on the values of $$d$$ and $$\sigma$$), we have:

$$c \leq \int_0^\infty x^d \exp(−x^2/\sigma^2) dx=\frac{\sigma^{d+1}}{2} \Gamma \left( \frac{d+1}{2} \right)$$

This is actually a good approximation for quite a lot of combinations of $$d,\sigma,m$$, just be careful to make sure the conditions for the approximation are satisfied.

For example, for $$d=1$$, $$\sigma=5$$ and $$m=25$$ we have:

$$S_m=12.41633011 \\ \frac{\sigma^{d+1}}{2} \Gamma \left( \frac{d+1}{2} \right)=12.5$$

(It somehow works even better for larger $$d$$, but I'm too tired to figure out why. I leave this to the OP).

• Thanks for your help, yes this is what I am looking for. There is something not clear for me ! I conclude, from what you did, that we can bound $c$, if $n_o<1$, as $$c \leq \frac{\sigma^{d+1}}{2}(\frac{d+1}{2})$$. But what will happen if $n_o> 1$ (which is my case!). As I saw in your last example I can use the same bound! IS this true Oct 30, 2018 at 10:37
• In my case, always $d>10$ and $\sigma$ also is positive Oct 30, 2018 at 10:42
• @Noah16, I don't know,I was too tired last night to figure out. My guess is there's some cancellation going on which allows the inequality to work in the more general case. Try to check it on your own, I will do it too but later Oct 30, 2018 at 10:42