# Convergence as a function of error for the following function

This question is about finding the number of samples in a sequence required for the convergence of a series as a function of an error tolerance $$\epsilon$$. I want to show what I have tried so far.

The function is

$$\sum_{q=1}^{N-1} \exp(-q^2 \sigma^2/2)(1 - q/N)$$ for $$\sigma > 0$$ and $$N \geq 1$$

It is confirmed that this function converges with a large N. I want to find a function for $$N$$ at which the error is $$\epsilon$$.

So, the sum of this expression from $$N$$ to $$\infty$$ is less than $$\epsilon$$. The sum of this from $$N$$ to $$\infty$$ can be represented as,

$$\sum_{q=1}^{\infty} \exp(-q^2\sigma^2/2) - \sum_{q=1}^{N-1} \exp(-q^2\sigma^2/2) (1-q/N) < \epsilon$$

For the first term, I tried something like this. If $$q \geq 1$$, $$q(q-1) \geq 0$$.

So,

$$\sum_{q=1}^{\infty} \exp(-q(q-1)\sigma^2/2) \exp(-q \sigma^2/2) \leq \sum_{q=1}^{\infty} \exp(-q \sigma^2/2) = \frac{\exp(-\sigma^2/2)}{(1 - \exp(-\sigma^2/2))}$$

For the second term,

$$\sum_{q=1}^{N-1} \exp(-q^2\sigma^2/2) (1-q/N)$$

I used the same trick as above, but now I say that as $$q \leq N-1, \quad q(q-1) \leq (N-1)(N-2)$$

For the second term, as there is a negative in equation (2), we will test for greater than equal to conditional properties of that function.

$$\sum_{q=1}^{N-1} \exp(-q^2\sigma^2/2) (1-q/N) =\sum_{q=1}^{N-1} \exp(-q(q-1)\sigma^2/2) \exp(-q \sigma^2/2) (1-q/N)$$

$$\sum_{q=1}^{N-1} \exp(-q^2\sigma^2/2) (1-q/N) \geq \exp(-(N-1)(N-2)\sigma^2/2) \sum_{q=1}^{N-1} (1-q/N) \exp(-q \sigma^2/2)$$

I typed this sum on wolfram, and the final expression I have is this,

$$\sum_{q=1}^{N-1} \exp(-q^2\sigma^2/2) (1-q/N) \geq \exp(-(N-1)(N-2)\sigma^2/2) \frac{\exp(-\sigma^2/2) (N-1 + \exp(-N \sigma^2/2) - N \exp(-\sigma^2/2))}{((1 - \exp(-\sigma^2/2))^2 N}$$

Rearranging a bit,

$$\sum_{q=1}^{N-1} \exp(-q^2\sigma^2/2) (1-q/N) \geq \exp(-(N^2-3N+3)\sigma^2/2) \frac{(N-1 + \exp(-N \sigma^2/2) - N \exp(-\sigma^2/2))}{((1 - \exp(-\sigma^2/2))^2 N}$$

If I plug this into the original inequality, things become complicated.

$$\sum_{q=1}^{\infty} \exp(-q^2\sigma^2/2) - \sum_{q=1}^{N-1} \exp(-q^2\sigma^2/2) (1-q/N) \leq \frac{\exp(-\sigma^2/2)}{(1 - \exp(-\sigma^2/2))} - \exp(-(N^2-3N+3)\sigma^2/2) \frac{(N-1 + \exp(-N \sigma^2/2) - N \exp(-\sigma^2/2))}{((1 - \exp(-\sigma^2/2))^2 N} < \epsilon$$

I don't know how to proceed from here.

$$\newcommand\ep\epsilon\newcommand{\si}{\sigma}$$"I want to find a function for $$N$$ at which the error is $$\epsilon$$."

This question is stated very poorly.

Indeed, let $$n:=N$$ (there is no reason to use $$N$$ where $$n$$ will do.) The $$n$$th error is $$\begin{equation*} \ep_n:=s-s_n=\ep_{1n}+\ep_{2n}, \end{equation*}$$ where $$\begin{equation*} s:=\sum_{q=1}^\infty a_q,\quad s_n:=\sum_{q=1}^{n-1} a_q(1-q/n), \quad a_q:=e^{-q^2\si^2/2}, \end{equation*}$$ $$\begin{equation*} \ep_{1n}:=\sum_{q=n}^\infty a_q,\quad \ep_{2n}:=\frac1n\,\sum_{q=1}^{n-1} a_q q. \end{equation*}$$

Clearly, $$\ep_n$$ takes only countably many values; so, the equality $$\ep_n=\ep$$ can hold only for countably many values of $$\ep$$. Also, a closed-form expression for $$\ep_n$$ is not available. So, solutions of the equation $$\ep_n=\ep$$ for $$n$$ are not available in closed form, even when such solutions exist.

However, for any real $$\ep>0$$, we can provide an explicit lower bound $$n_{\si,\ep}$$ on $$n$$ such that $$\ep_n\le\ep$$ for $$n\ge n_{\si,\ep}$$ -- and this is what appears to have actually been tried to do in most of the OP.

Indeed, note that $$\begin{equation*} r_q:=\frac{a_{q+1}}{a_q}=e^{-(q+1/2)\si^2} \end{equation*}$$ is decreasing in $$q$$. So, $$\begin{equation*} \ep_{1n}\le\sum_{q=n}^\infty a_n r_n^{q-n}=\frac{a_n}{1-r_n}=\frac{e^{-n^2\si^2/2}}{1-e^{-(n+1/2)\si^2}} \le2e^{-n^2\si^2/2} \end{equation*}$$ if $$\begin{equation*} n\ge\frac{\ln2}{\si^2}-\frac12. \end{equation*}$$ Next, $$\begin{equation*} \ep_{2n}\le\frac1n\,\sum_{q=1}^\infty a_q q \le\frac{h(\si)}n, \end{equation*}$$ where $$$$h(\si):=\sum_{q=1}^\infty a_1 r_1^{q-1} q =\frac{e^{5 \si ^2/2}}{(e^{3 \si^2/2}-1)^2}.$$$$ Thus, if $$$$n\ge n_{\si,\ep}:=\max\Big(\frac{\ln2}{\si^2}-\frac12,\sqrt{\frac2{\si^2}\, \max\Big(0,\ln\frac3\ep\Big)}, \frac{h(\si)}{\ep/3}\Big),$$$$ then $$\ep_n\le\ep$$. $$\quad\Box$$

• Thank you very much indeed for the detailed answer. I will look into it line by line. When you said $n$ will do instead of $N$, do you mean only in terms of notation, or something else? And, when you said the question is stated poorly, do you mean the definition of the error stated poorly? I want to understand. Commented Dec 21, 2022 at 15:21
• @CfourPiO : (i) I meant $n$ instead of $N$ in terms of notation. (ii) As for "poorly stated", this is explained in the answer as follows: "Clearly, $\epsilon_n$ takes only countably many values; so, the equality $\epsilon_n=\epsilon$ can hold only for countably many values of $\epsilon$. Also, a closed-form expression for $\epsilon_n$ is not available. So, solutions of the equation $\epsilon_n=\epsilon$ for $n$ are not available in closed form, even when such solutions exist." Commented Dec 21, 2022 at 15:25
• I want to understand why we use certain inequalities sometimes to find easier ways to show convergence. For example, when we say $\epsilon_{2n} = \frac{1}{n}\sum_{q=1}^{n-1} a_q q \leq \frac{1}{n}\sum_{q=1}^{\infty} a_q q$ . Logically it makes sense. However, I want to understand why it is used in this context. It could be any number less than $\infty$ and bigger than $n-1$. How do we acknowledge the error we are introducing by such inequalities. Commented Dec 22, 2022 at 10:04
• I also want to understand why $\epsilon_{n}$ can only take countably many values. I am not a mathematician, so my understanding can be really basic. From your approach, all I can understand is that probably the two terms involved in the original equation behave differently as $n$ increases so you introduced $\epsilon_{1n}$ and $\epsilon_{2n}$. Then, you dealt them separately to find convergence of each and then took a maximum? I think this is what I was looking for. When I said $\epsilon$, it is a common non mathematician way of saying convergence. I am happy I am learning new things here. :) Commented Dec 22, 2022 at 10:12
• @CfourPiO : (i) We bound $\sum_{q=1}^{n-1} a_q q$ by $\sum_{q=1}^\infty a_q q$ because the latter sum is easier to deal with (see what is done with it next); also, for large $n$ the sum $\sum_{q=1}^{n-1} a_q q$ will be close to $\sum_{q=1}^\infty a_q q$. (ii) $\epsilon_n$ takes only countably many values by the definition of a countable set (see e.g. "there exists a surjective function from ${\displaystyle \mathbb {N} }$ to ${\displaystyle S}$" in the section at en.wikipedia.org/wiki/Countable_set#Definition . Commented Dec 22, 2022 at 17:46