3
$\begingroup$

To what function is $s(n) = \sum_{i=0}^n e^{-i^2/n + i^a}$ with $a \in ]0,1]$ asymptotic (as $n \to \infty$)? or what are relatively tight lower and upper bounds?

Here is what I tried so far: go over to a "Riemann sum" $$ n \sum_{i=0}^n \tfrac{1}{n} e^{ -n (i/n)^2 + n^a (i/n)^a} \approx n \int_0^1 e^{ -n x^2 + n^a x^a} $$ when $a = 1$ this integral is actually easy to evaluate (it's asymptotic to $\sqrt{\pi} \cdot e^{n/4}/\sqrt{n}$) and gives a very tight bound for the asymptotics of the sum.

When $a<1$, I used the following estimates: $-n x^2 + n^a x^a >0 \iff 0< x < n^{(a-1)/(2-a)}$. The maximum of the exponent happens when $-2nx + an^ax^{a-1} =0 \iff x = (\tfrac{a}{2})^{1/(2-a)}n^{(a-1)/(2-a)}$. This gives a maximal value of the exponent of the integrand $$ -n (\tfrac{a}{2})^{2/(2-a)}n^{(2a-2)/(2-a)} + n^a (\tfrac{a}{2})^{a/(2-a)}n^{(a^2-a)/(2-a)} = \bigg( -(\tfrac{a}{2})^{2/(2-a)} + (\tfrac{a}{2})^{a/(2-a)} \bigg)n^{a/(2-a)} = ( 1-\tfrac{a}{2}) (\tfrac{a}{2})^{a/(2-a)} n^{a/(2-a)} $$ Up to a mistake of $1$, one can ignore the part of the area of the integral which is the region of the unit square. There remains at most a rectangle with dimensions $n^{(a-1)/(2-a)} \times \mathrm{exp}\bigg( ( 1-\tfrac{a}{2}) (\tfrac{a}{2})^{a/(2-a)} n^{a/(2-a)} \bigg)$.

Hence $s(n) \leq n^{1/(2-a)} \mathrm{exp}\bigg( ( 1-\tfrac{a}{2}) (\tfrac{a}{2})^{a/(2-a)} n^{a/(2-a)} \bigg)$ (for large $n$).

The lower bound [for $n$ large] $s(n) \geq \mathrm{exp}\bigg( ( 1-\tfrac{a}{2}) (\tfrac{a}{2})^{a/(2-a)} n^{a/(2-a)} \bigg)$ is also not too hard to get (just restrict the sum to the a few values of $i$ so that $i/n \approx (\tfrac{a}{2})^{1/(2-a)}n^{(a-1)/(2-a)}$).

Numerics indicate that $s(n) \approx K n^{1/2} \mathrm{exp}\bigg( ( 1-\tfrac{a}{2}) (\tfrac{a}{2})^{a/(2-a)} n^{a/(2-a)} \bigg)$ for some $K \in [1,2]$

$\endgroup$

1 Answer 1

4
$\begingroup$

I suppose that you can also evaluate $K \in [1,2]$. Consider the power of exponent near the maximum: $$e^{f(k)}=e^{f(k_{max})+\frac{1}{2}f''(k_{max})(k-k_{max})^2+...}$$ It is supposed that other terms of the series in the power of the exponent can be omitted (do not contribute into the main asymptotics term). In many cases such approximation works well.

$$f(k)=-\frac{k^2}{n}+k^a$$ $$k_{max}=(\frac{a}{2}n)^\frac{1}{2-a}$$ $$ f(k_{max})=\Bigl((\frac{a}{2})^\frac{a}{2-a}-(\frac{a}{2})^\frac{2}{2-a}\Bigr)*n^\frac{a}{2-a}$$ $$f''(k)=-\frac{2}{n}+a(a-1)k^{a-2}$$ $$f''(k_{max})=-\frac{2}{n}+a(a-1)(\frac{an}{2})^\frac{a-2}{2-a}=-\frac{2}{n}(2-a)$$

$$S(n)=\sum_{k=0}^n e^{-k^2/n + k^a}\sim{e}^{\Bigl((\frac{a}{2})^\frac{a}{2-a}-(\frac{a}{2})^\frac{2}{2-a}\Bigr)n^\frac{a}{2-a}}\sum_{k=0}^n e^{\frac{1}{2}f''(k_{max})(k-k_{max})^2}$$

Switching from summation to integration and expanding integration to $\pm\infty$ we get the main asymptotics term: $$S(n)\sim{e}^{\Bigl((\frac{a}{2})^\frac{a}{2-a}-(\frac{a}{2})^\frac{2}{2-a}\Bigr)n^\frac{a}{2-a}}\int_{0}^n{e}^{-\frac{2-a}{n}(k-k_{max})^2}dk$$ $$S(n)\sim{e}^{\Bigl((\frac{a}{2})^\frac{a}{2-a}-(\frac{a}{2})^\frac{2}{2-a}\Bigr)n^\frac{a}{2-a}}\sqrt\frac{\pi{n}}{2-a}$$

You can check the expression at $a=1$.

$\mathsf{Supplement}$

We can also dig a bit deeper - to get an idea about the limitations of the method. $$F(k)=\exp(-\frac{k^2}{n}+k^a)$$ $$F'(k)=(-\frac{2k}{n}+\frac{a}{k^{1-a}})\exp(-\frac{k^2}{n}+k^a)$$ $k_{max}=(\frac{a}{2}n)^\frac{1}{2-a}=\frac{n}{2}$ at $a=1$, so at $a=1$ the function is exactly the Gauss curve with a maximum at $k=\frac{n}{2}$. At $a\to0$ $k_{max}=(\frac{a}{2}n)^\frac{1}{2-a}\to\sqrt{\frac{a}{2}n}$ and is shifting to the left from the center of the interval $(0,n)$. The function becomes asymmetrical, and at $a=0$ we end up with a half of Gauss curve with $k_{max}=0$. So we may suppose that the method works as soon as $a$ is not too close to zero.

In order to omit higher powers in the expansion $f(k)=f(k_{max})+\frac{1}{2}f''(k_{max})(k-k_{max})^2+\frac{1}{6}f'''(k_{max})(k-k_{max})^3+...$

there should be $|f'''(k_{max})|<<|f''(k_{max})|$, or $\frac{2}{n}>>a(1-a)(\frac{an}{2})^{\frac{a-3}{2-a}}$

We consider the case $a<<1$, so the limitation is $\frac{2}{n}>>a(\frac{an}{2})^{-\frac{3}{2}}$, or $\sqrt{na}>>1$. We can check that when this requirement is met $f^{(l+1)}(k_{max})<<f^{(l)}(k_{max})$ for all derivatives.

Therefore the main asymptotics term $$S(n)\sim{e}^{\Bigl((\frac{a}{2})^\frac{a}{2-a}-(\frac{a}{2})^\frac{2}{2-a}\Bigr)n^\frac{a}{2-a}}\sqrt\frac{\pi{n}}{2-a} (n>>1, \sqrt{na}>>1)$$

$\endgroup$
1
  • $\begingroup$ Very nice Idea with the expansion around $k_{max}$, and many thanks for the supplement! $\endgroup$
    – ARG
    Feb 27, 2021 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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