Stirling's approximation

From Wikipedia for FEVERv2
Jump to navigation Jump to search

In mathematics, Stirling's approximation (or Stirling's formula) is an approximation for factorials. Stirling's approximation_sentence_0

It is a good approximation, leading to accurate results even for small values of n. It is named after James Stirling, though it was first stated by Abraham de Moivre. Stirling's approximation_sentence_1

The version of the formula typically used in applications is Stirling's approximation_sentence_2

Specifying the constant in the O(ln n) error term gives 1/2ln(2πn), yielding the more precise formula: Stirling's approximation_sentence_3

where the sign ~ means that the two quantities are asymptotic: their ratio tends to 1 as n tends to infinity. Stirling's approximation_sentence_4

One may also give simple bounds valid for all positive integers n, rather than only for large n: Stirling's approximation_sentence_5

Derivation Stirling's approximation_section_0

Roughly speaking, the simplest version of Stirling's formula can be quickly obtained by approximating the sum Stirling's approximation_sentence_6

with an integral: Stirling's approximation_sentence_7

The full formula, together with precise estimates of its error, can be derived as follows. Stirling's approximation_sentence_8

Instead of approximating n!, one considers its natural logarithm, as this is a slowly varying function: Stirling's approximation_sentence_9

The right-hand side of this equation minus Stirling's approximation_sentence_10

is the approximation by the trapezoid rule of the integral Stirling's approximation_sentence_11

and the error in this approximation is given by the Euler–Maclaurin formula: Stirling's approximation_sentence_12

where Bk is a Bernoulli number, and Rm,n is the remainder term in the Euler–Maclaurin formula. Stirling's approximation_sentence_13

Take limits to find that Stirling's approximation_sentence_14

Denote this limit as y. Stirling's approximation_sentence_15

Because the remainder Rm,n in the Euler–Maclaurin formula satisfies Stirling's approximation_sentence_16

where big-O notation is used, combining the equations above yields the approximation formula in its logarithmic form: Stirling's approximation_sentence_17

Taking the exponential of both sides and choosing any positive integer m, one obtains a formula involving an unknown quantity e. For m = 1, the formula is Stirling's approximation_sentence_18

The quantity e can be found by taking the limit on both sides as n tends to infinity and using Wallis' product, which shows that e = √2π. Stirling's approximation_sentence_19

Therefore, one obtains Stirling's formula: Stirling's approximation_sentence_20

An alternative derivation Stirling's approximation_section_1

An alternative formula for n! Stirling's approximation_sentence_21

using the gamma function is Stirling's approximation_sentence_22

(as can be seen by repeated integration by parts). Stirling's approximation_sentence_23

Rewriting and changing variables x = ny, one obtains Stirling's approximation_sentence_24

Applying Laplace's method one has Stirling's approximation_sentence_25

which recovers Stirling's formula: Stirling's approximation_sentence_26

In fact, further corrections can also be obtained using Laplace's method. Stirling's approximation_sentence_27

For example, computing two-order expansion using Laplace's method yields Stirling's approximation_sentence_28

and gives Stirling's formula to two orders: Stirling's approximation_sentence_29

Speed of convergence and error estimates Stirling's approximation_section_2

Stirling's formula is in fact the first approximation to the following series (now called the Stirling series): Stirling's approximation_sentence_30

An explicit formula for the coefficients in this series was given by G. Nemes. Stirling's approximation_sentence_31

The first graph in this section shows the relative error vs. n, for 1 through all 5 terms listed above. Stirling's approximation_sentence_32

As n → ∞, the error in the truncated series is asymptotically equal to the first omitted term. Stirling's approximation_sentence_33

This is an example of an asymptotic expansion. Stirling's approximation_sentence_34

It is not a convergent series; for any particular value of n there are only so many terms of the series that improve accuracy, after which accuracy worsens. Stirling's approximation_sentence_35

This is shown in the next graph, which shows the relative error versus the number of terms in the series, for larger numbers of terms. Stirling's approximation_sentence_36

More precisely, let S(n, t) be the Stirling series to t terms evaluated at n. The graphs show Stirling's approximation_sentence_37

which, when small, is essentially the relative error. Stirling's approximation_sentence_38

Writing Stirling's series in the form Stirling's approximation_sentence_39

it is known that the error in truncating the series is always of the opposite sign and at most the same magnitude as the first omitted term. Stirling's approximation_sentence_40

More precise bounds, due to Robbins, valid for all positive integers n are Stirling's approximation_sentence_41

Stirling's formula for the gamma function Stirling's approximation_section_3

For all positive integers, Stirling's approximation_sentence_42

where Γ denotes the gamma function. Stirling's approximation_sentence_43

However, the gamma function, unlike the factorial, is more broadly defined for all complex numbers other than non-positive integers; nevertheless, Stirling's formula may still be applied. Stirling's approximation_sentence_44

If Re(z) > 0, then Stirling's approximation_sentence_45

Repeated integration by parts gives Stirling's approximation_sentence_46

where the expansion is identical to that of Stirling' series above for n!, except that n is replaced with z-1. Stirling's approximation_sentence_47

A further application of this asymptotic expansion is for complex argument z with constant Re(z). Stirling's approximation_sentence_48

See for example the Stirling formula applied in Im(z) = t of the Riemann–Siegel theta function on the straight line 1/4 + it. Stirling's approximation_sentence_49

Error bounds Stirling's approximation_section_4

For any positive integer N, the following notation is introduced: Stirling's approximation_sentence_50

and Stirling's approximation_sentence_51

Then Stirling's approximation_sentence_52

For further information and other error bounds, see the cited papers. Stirling's approximation_sentence_53

A convergent version of Stirling's formula Stirling's approximation_section_5

Thomas Bayes showed, in a letter to John Canton published by the Royal Society in 1763, that Stirling's formula did not give a convergent series. Stirling's approximation_sentence_54

Obtaining a convergent version of Stirling's formula entails evaluating Raabe's formula: Stirling's approximation_sentence_55

One way to do this is by means of a convergent series of inverted rising exponentials. Stirling's approximation_sentence_56

If Stirling's approximation_sentence_57

then Stirling's approximation_sentence_58

where Stirling's approximation_sentence_59

where s(n, k) denotes the Stirling numbers of the first kind. Stirling's approximation_sentence_60

From this one obtains a version of Stirling's series Stirling's approximation_sentence_61

which converges when Re(x) > 0. Stirling's approximation_sentence_62

Versions suitable for calculators Stirling's approximation_section_6

The approximation Stirling's approximation_sentence_63

and its equivalent form Stirling's approximation_sentence_64

can be obtained by rearranging Stirling's extended formula and observing a coincidence between the resultant power series and the Taylor series expansion of the hyperbolic sine function. Stirling's approximation_sentence_65

This approximation is good to more than 8 decimal digits for z with a real part greater than 8. Stirling's approximation_sentence_66

Robert H. Windschitl suggested it in 2002 for computing the gamma function with fair accuracy on calculators with limited program or register memory. Stirling's approximation_sentence_67

Gergő Nemes proposed in 2007 an approximation which gives the same number of exact digits as the Windschitl approximation but is much simpler: Stirling's approximation_sentence_68

or equivalently, Stirling's approximation_sentence_69

An alternative approximation for the gamma function stated by Srinivasa Ramanujan (Ramanujan 1988) is Stirling's approximation_sentence_70

for x ≥ 0. Stirling's approximation_sentence_71

The equivalent approximation for ln n! Stirling's approximation_sentence_72

has an asymptotic error of 1/1400n and is given by Stirling's approximation_sentence_73

The approximation may be made precise by giving paired upper and lower bounds; one such inequality is Stirling's approximation_sentence_74

Estimating central effect in the binomial distribution Stirling's approximation_section_7

History Stirling's approximation_section_8

The formula was first discovered by Abraham de Moivre in the form Stirling's approximation_sentence_75

See also Stirling's approximation_section_9

Stirling's approximation_unordered_list_0

Credits to the contents of this page go to the authors of the corresponding Wikipedia page:'s approximation.