How does someone approximate something like $$\frac{1}{n}\sum_{k=1}^n e^{-k I(k)^2}$$ where I(k) is equidistributed on $[0,1]$. Ideally I would like to show its about $K/\sqrt{n}$ for some constant $K$. This is not homework, but a question I stumbled upon "in nature" and I don't really have any ideas on how to tackle it.
Summing something with random and non-random parts
1
$\begingroup$
probability
analysis
-
0Please pick a better title. – 2010-11-11
1 Answers
4
To get a rough idea for your sum, I tried the following, don't know if it is correct.
First compute the expected value of $e^{-k x^2}$ as $$\int_0^1 e^{-k x^2} dx = \frac{\sqrt{\pi}\mbox{erf}(\sqrt{k})}{2\sqrt{k}}$$ Now, I used the cheap bound that $\mbox{erf}(\sqrt{k}) < 1$, to see that in expected value each term of your sum is approximately $c/(2\sqrt{k})$, for some constant $c$. Thus, the your sum is approximately: $$\sum_{k=1}^n \frac{c}{2\sqrt{k}} \approx K\sqrt{n},$$ so that after using the normalizing $1/n$ outside the sum, the approximate value of your sum is indeed $K/\sqrt{n}$.
-
0According to mathworld: http://mathworld.wolfram.com/Erf.html, $erf(x) = 1 - e^{-x^2}(1/x - 2/x^3 + ...)/\sqrt{\pi}$. – 2010-11-11