5
$\begingroup$

https://en.wikipedia.org/wiki/Stirling's_approximation

Here $$\sum \limits_{i=1}^n \log(i) $$ is approximated as $$\int^n_1\log(x) dx\ +\ 1/2\ \log(n)$$ but I would approximate it as $$\int^{n+1/2}_{0.5}\log(x)dx$$ clearly my method gives the wrong answer. Can someone explain to me how 1/2 logn term is decided?

ADDITION: For example, if I wanted to approximate $$\sum \limits_{i=1}^{100} i^{-2} $$ I would actually sum the first 10 terms, and then add a correction term using integration. What I would do is, I would add the integral of 1/x^2 from 10.5 to 100.5 (sort of like a midpoint rule). What this rule suggests I do is to integrate from 11 to 100 and then add 1/2(1/11^2 + 1/100^2). I actually did this and my term is accurate within 7.1677e-05 and the trapezoid is accurate within -1.2485e-04.

Final Edit: https://i.stack.imgur.com/kdPu2.png
My approximation actually provides a better approximation anyway.

$\endgroup$

2 Answers 2

5
$\begingroup$

They are using the trapezoid rule over $n-1$ intervals: $(1,2), (2,3) \dots (n-1,n)$ The trapezoid rule for the first interval is $\int_1^2f(x)\;dx \approx \frac 12(f(1)+f(2))$ When you add these up over all the intervals, each internal point gets a coefficient $1$, with $\frac 12$ coming from the interval below and $\frac 12$ from the interval above but the end terms retain the factor $\frac 12$. This gives $$\sum_{i=1}^n f(i) \approx \int_1^n f(x)\; dx +\frac 12 f(1)+\frac 12 f(n)$$ Using $f(x)=\log x$ and the fact that $\log 1=0$ we get the Wikipedia result.

Your approximation is not wrong or silly. You have applied the midpoint rule to the intervals $(1/2,3/2),(3/2,5/2)\dots (n-\frac 12,n+\frac 12)$ The result is $\left. x \log x \right|_{0.5}^{n+\frac 12}=(n+\frac 12) \log(n+\frac 12)-\frac 12\log \frac 12$ which only differs from the trapezoid rule result by the $+\frac12$ in the argument of the log and the addition of the constant $\frac 12 \log 2$. You have the same asymptotic form and the $+\frac 12$ is equivalent (for large $n$) to adding $\frac 12$ It would take a careful error analysis to see which is more accurate.

$\endgroup$
3
  • $\begingroup$ >You have the same asymptotic form|| Followup: by this logic $(n+1/2)^n\ \sim \ n^n$ but when I expand $(n+1/2)^n\ =n^n+n\ n^{n-1}1/2.....$ and they don't seem the same to me. $\endgroup$ May 12, 2015 at 0:40
  • 1
    $\begingroup$ Note that $\log (n+\frac 12) \approx \log n + \frac 12 \cdot \frac 1n$ as the first two terms of a Taylor series, so $(n+\frac 12)\log(n+\frac 12) \approx (n+\frac 12) \log n +\frac 12$. When we take the exponential to compare $(n+1/2)^2$ and $n^n$ the relevant thing is to divide them, not to subtract them. Then you get $(1+\frac 1{2n})^n\approx \sqrt e$ as a ratio $\endgroup$ May 12, 2015 at 0:56
  • $\begingroup$ Thank you very much. I have actually tried it and I now know that I am justified in being a midpoint rule proponent. i.imgur.com/8TO2FKC.png My approximation is the orange one, which clearly approaches 1 faster. However it is a reasonable to omit 1/2 since it makes the expression uglier. $\endgroup$ May 12, 2015 at 1:03
0
$\begingroup$

Years later I had to use the Stirling approximation and it made me think of this question. Since asking this question, I have discovered that the following (attained by the midpoint method) is a more accurate approximation:

$$\sqrt{2\pi}\bigg( \frac{n+\frac12}{e} \bigg)^{n+\frac12}$$

I realize the asymptotic series can get better approximations with more terms, but the midpoint method does give a more accurate result with the first term. The proportional error of this expression is half as large as Stirling approximation. By mixing them together, one can get a far superior approximation than either scenario.

$$\sqrt{2 \pi } \sqrt[3]{e^{-3 n-1} n^{n+\frac{1}{2}} \left(n+\frac{1}{2}\right)^{2 n+1}}$$

Below I plot $\log(n!)-\log(\text{approximation})$.
Stirling->Blue
Midpoint->Orange
Combined->Green
enter image description here

$\endgroup$
5
  • 1
    $\begingroup$ The factor $\frac{\mathrm e}{\sqrt{2\pi}}$ is incorrect, it should be $\sqrt{2\pi}$. Otherwise the comment about its error compared to the standard Stirling formula is not true. $\endgroup$
    – Gary
    Jul 6, 2023 at 22:44
  • 1
    $\begingroup$ You may find it interesting that your approximation is the leading order of $(5.11.8)$ with $z=n+\frac{1}{2}$ and $h=\frac{1}{2}$. This is actually the asymptotic expansion that was originally established by Stirling. $\endgroup$
    – Gary
    Jul 7, 2023 at 0:02
  • $\begingroup$ You are right. I'm not sure how I made that typo/mistake. $\endgroup$ Jul 7, 2023 at 17:04
  • $\begingroup$ The more "general" Stirling approximation is interesting. I had assumed he simply had an asymptotic series in terms of inverse powers of z and the first term was the commonly known Stirling formula. But I guess he accounted for an "offset" of h as well. $\endgroup$ Jul 7, 2023 at 17:26
  • 1
    $\begingroup$ This paper might be of interest for you: arxiv.org/pdf/1701.06689.pdf $\endgroup$
    – Gary
    Jul 8, 2023 at 0:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .