Jump to ContentJump to Main Navigation
The Statistical Mechanics of Interacting Walks, Polygons, Animals and Vesicles$

E.J. Janse van Rensburg

Print publication date: 2015

Print ISBN-13: 9780199666577

Published to Oxford Scholarship Online: August 2015

DOI: 10.1093/acprof:oso/9780199666577.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (www.oxfordscholarship.com). (c) Copyright Oxford University Press, 2017. All Rights Reserved. Under the terms of the licence agreement, an individual user may print out a PDF of a single chapter of a monograph in OSO for personal use (for details see http://www.oxfordscholarship.com/page/privacy-policy). Subscriber: null; date: 26 February 2017

(p.558) Appendix D Asymptotic approximations

(p.558) Appendix D Asymptotic approximations

The Statistical Mechanics of Interacting Walks, Polygons, Animals and Vesicles
Oxford University Press

The Stirling approximation for the factorial [187] is given by


Lower and upper bounds on the factorial are


(see references [187, 494]), while the approximation


is from a numerical point of view very accurate.

Stirling’s approximation can also be stated as


from which it follows, for example,

nn(n)n722πn110nfor ,nN0, and 0n.

More on Stirling’s approximation may be found in reference [592].

Catalan numbers are defined by


By putting both n2n and =n in equation (D.5) and keeping more terms in the Stirling approximation, one finds that


for some fixed M>0; see lemma 4.4 in reference [488].

(p.559) D.1 Approximation of the binomial coefficient

The binomial coefficient can be approximated using approximations for the factorial. A more interesting approach is to consider random walks in Z.

Consider a random walk from 0 in Z giving left or right steps. Assign a generating variable t with each right step so that tˉ1t represents a left step.

The generating function of walks of length n is (t+tˉ)n, and the coefficient of tk is the number of walks ending at kZ from the origin. Thus, by the binomial theorem, the number of walks ending at k is n(n+k)/2, since the walk ends at k if it gives 12(n+k) right steps (and 12(nk) left steps).

Assume that t(0,1) and suppose that the walk steps to the right with probability P+=tt+tˉ and to the left with probability P=tˉt+tˉ. Let Xk be the final position of the walk after k steps. Then X0=0.

Note that Xk is a random variable and that Xn=k for k[n,n] with probability

Pr(Xn=k)={(n12(n+k) )tk(t+t¯)n, if mod(n+k,2)=0;0,otherwise.

The value of Pr(Xn=k) is 0 if n and k do not have the same parity (are not both even, or not both odd).

Asymptotically, n and k have the same parity with probability 12, and the distribution of Xn is given by


By the central limit theorem, the random variable Xn is asymptotically normally distributed with mean μn and variance σ2n, where


Thus, it follows that


This is maximal when k=μn, with μ‎ given above. In particular, if k=an, then one may solve for t to obtain


Since t(0,1), select the positive root ta+. In this event, it follows that, if t=ta+, then μn=an+O(n). For this choice of k and with t=ta+, one may solve for the binomial coefficient in equation (D.9):



Substitute t=ta+ into equation (D.12) to obtain the following approximation for the binomial:

Theorem D.1

The binomial coefficient is approximated by


Next, replace an=2bnn for b[0,1] and simplify to obtain


For large values of n, the above can be approximated by


Taking n gives Corollary D.2.

Corollary D.2

The rate of growth of binomial coefficients is given by


for b[0,1]. The function B(b) has infinite right- and left-derivatives at b=0, and b=1, respectively. Moreover, B(0)=B(1)=1, and B(12)=2B(b).

One may replace an or bn by an or bn with few, if any changes, in Corollary D.2.

More generally, for a,X>0, and b[0,a], one may consider the function


which has a maximum for fixed a>0 given by

maxb(0,a)B(a,b)=(1+x)a,realised when b=ax1+x.

Similar to B(b) in Corollary D.2, B(a,b) has infinite right- and left-derivatives at b=0, and b=a, for fixed a,x>0.

(p.561) The function for x>0, and a(0,1), defined by


similarly has the maximum

maxa(0,1)C(a)=121+1+4x,realised when a=1+4x121+4x

for fixed a>0. The function C(a) has infinite left- and right-derivatives at a=0, and a=1, respectively.

Lemma D.3

Let 0<q< and suppose γ[0,qq+1]. Then

lim supni=0γnniqi1/nqγγγ(1γ)1γ.


Let p=qq+1 so that 0γp<1. Then


Consider p to be the probability that a biased tossed coin will land heads. Let η‎ be the number of heads in n tosses of the coin. Then the probability that there are at most γn heads in n tosses is


If ζ is a random variable equal to 1 if ηγn, and 0 otherwise, then the expectation of ζ is Eζ=Pr(ηγn. By Jensen’s inequality,


The right-hand side is a minimum when γn(1p)=p(nγn)et. Thus, substituting for t gives


Substitute p=qq+1, take the power 1n and take n.

This completes the proof.

(p.562) D.2 Approximation of trinomial coefficients

Trinomial coefficients are defined by


The term ‘trinomial coefficient’ is used as in reference [9]; that is, ‘trinomial coefficient’ is used synonymously with ‘central trinomial coefficient’.

Trinomial coefficients are given in terms of binomial coefficients by


The properties of a random walker in Z can be used to find approximations to trinomial coefficients. Let the position of the walker be xn and suppose it gives right or left unit length steps in Z, or a neutral step where it stays put at xn, so that xn+1=xn±1, or xn+1=xn.

Let x0=0 and suppose the random walker gives right, neutral and left steps with probabilities P+, P0 and P, respectively. Suppose t(0,1), let tˉ=1t and let

 P+=tt+1+tˉP0=1t+1+tˉ; and P=tˉt+1+tˉ .

The probability that xn=k for k[n,n] is given by


since xn=k if the walk gives k+p right steps and p left steps, and since the number of walks ending at k is exactly given by the trinomial coefficient.

The central limit theorem states that the random variable xn is asymptotically normal with mean μn and variance σ2n, where




Thus, it follows that


Substitute k=αn, substitute μ=ttˉt+1+tˉ and solve for t:



Since t(0,1), select tα+ so that μn=αn+O(n) and solve for the trinomial coefficient in equation (D.22). If k=αn, and t=tα+, then this gives


Simplification gives theorem D.4.

Theorem D.4

The trinomial coefficient is approximated by



Aα =43n αn+43n2αn2;             Bα=11n αn;Cα =43n2 αn2;  and Dα=1n αn+43n2αn2.

For large values of n, one may use Corollary D.5.

Corollary D.5

The trinomial coefficient


where β=43α2.

The rate of exponential growth of the trinomial coefficient is given by Corollary D.6.

Corollary D.6

The limit

  limn(nαn)21/n=2α(43α+43α2)(1α)1α(α+43α2)1+α =(2α2α43α2)α/2(139α2+(73α2)43α2)1/32α/2(1α)(1+α)1+α

The rate of growth of the generating function of trinomial coefficients is defined by


Given an n, there is a value of j, say j=jn, which maximises the summand.

(p.564) Assuming that jn=ϵmn+o(n), where ϵm(0,1) is a function of z, it follows that


By replacing jn in the above by ϵn+o(n) and then using equation (D.6) when taking n in equation (D.29), it follows that


By differentiating and solving for ϵ, the supremum is realised when

ϵ=ϵm=zzˉz+1+zˉ=μ in equation (D.23).

It follows that ϵm(0,1) if z>1, and so the supremum is achieved when ϵm=0 when z1 at ϵm. These results show that, after simplification,

Theorem D.7

The function F(z) is given by

F(z)={z+1+zˉ,if z(1,);3,if z[0,1],

where zˉ=1z.

D.3 The Euler-Maclaurin formula

The Euler-Maclaurin formula (see for example [273]) is a useful method for approximating series by integrals. The formula is useful because it gives precise remainders, allowing estimates of the error in the approximation.

Theorem D.8 (Euler-Maclaurin)

If fC2m[0,N] for some m,NN, and both N>0 and m1, then


where the remainder term is given by


The function Bn(x) is the n-th Bernoulli polynomial; Bn=Bn(0), and Bn(xx) is the n-th periodic Bernoulli polynomial.

(p.565) In some applications the remainder term Rm approaches 0 with m (derivatives of f exist to all orders), and one may able to show that the series is convergent.

The remainder term can be bounded by


The Bernoulli functions are defined by the recurrence ddxBn(x)=nBn1(x), with B0(x)=1, and 01Bn(x)dx=0, for n1. The first few are given by B1(x)=x12; B2(x)=x2x+16; B3(x)=x332x2+12x; and B4(x)=x42x3+x2130.

The Bernoulli numbers Bn are defined by the exponential generating function tet1=m=0Bmm!tm. Notably, B2n+1=0 if n1 (that is B3=B5=B7==0), and the first few non-zero Bernoullui numbers are B1=12; B2=16; B4=130; and B6=142.

The Stirling approximation for n! is obtained as follows. Consider the integral


Applying the Euler-Maclaurin formula to the integral on the left-hand side gives


The infinite series in the above is a polygamma function and


Take the anti-derivative of this twice to obtain


The constant C is computed from the Legendre duplication formula


This gives C=12log(2π). Finally,


This is an asymptotic series approximating logz!. By truncating the infinite series, the error in the approximation is less than the magnitude of the first omitted term. If the series is discarded in its entirety, then the Stirling approximation in equation (D.1) is found.

(p.566) D.4 Saddle point approximations of the integral

Suppose that f is an analytic complex function of the complex variable z=x+iy. Then f=u+iv, and {u,v} satisfies the Cauchy-Riemann equations. Consequently, it may be shown that u satisfies the Laplace equation:


At any stationary point of f, if 2x2u>0, then 2y2u<0. That is, if f is real valued, then its stationary points are necessarily saddle points.

The function f may be approximated in the vicinity of a saddle point z0 by


This approximation of f near its saddle points allows the approximation of integrals of the form


where N is large, and g(z) is slowly varying.

Insert the approximation of f in the above and replace g(z)g(z0). Deform the contour of integration from a to b into a contour C in the complex plane passing through z0. This gives


Put zz0=reiϕ and let f(z0)=f(z0)eiθ. The integration will be along r, with ϕ‎ fixed at a convenient value, namely, θ+2ϕ=π. The integration is approximated by integrating from r= to r=. These substitutions simplify the integral above into a Gaussian integral:


Evaluating the integral gives the saddle point approximation


The phase ϕ‎ is determined by solving for ϕ=πθ2.

It is possible to refine the above approximations by keeping more terms in the expansion (D.35). This approximation also has the implicit assumption that the only significant contribution to the integral along the contour C is from the vicinity of the saddle point (this means that u(z0)u(z) if |z0z| is ‘large’. This may not be necessarily the case. For more on this method, which is related to steepest descent methods, see, for example, reference [13].

(p.567) D.5 Asymptotic formulae for the q-factorial and related functions

The q-deformations of special functions are obtained from an arithmetic based on q-integers, and defined by


where qC. These q-integers retain many of the properties of the usual integers. A q-integer is sometimes called a q-bracket or a basic integer.

The q-Pochhammer function is a finite product formally defined by


(t;q) is an infinite product.

The q-Pochhammer function (t;q) is an analytic function inside the unit disk in the q-plane. Euler’s function is defined by (q;q). Observe that (q)=(q;q) and


Put n= in the above to find an infinite product representation of (q).

A partition identity (see for example reference [8]) shows that


Note that the usual factorial in the definition of the exponential is replaced by (q)k. For this reason, e(t,q) is sometimes called the q-exponential; however, see equation (D.46) below.

(p.568) The natural definition of the q-analogue of the factorial is in terms of q-integers:


and these are also called basic factorials or Gaussian factorials. This gives rise to the q-analogue of the gamma function or the q-gamma function:


which becomes Γq(k+1)=[k]q! if kN. Observe that, if q1 in each of the above, then the usual integers, factorials and gamma functions are recovered.

The natural definition of the q-exponential is


or, alternatively,


Observe that Eqt=e1/qt=1/eqt.

These definitions of the exponential give rise to q-analogues of the trigonometric functions sine and cosine. There are also q-analogues of special functions. For example, q-deformed Bessel functions are defined by


More on q-calculus can be found, for example, in reference [345].

D.5.1 The q-binomial coefficient

The above definitions extend to the q-binomial coefficient, defined by


and, if nN, and kN, then this becomes


Observe that [n]q=n1 and that nk satisfies the following q-binomial identities:


Lemma D.9 is not obvious.

Lemma D.9

If nN0, and kN0, then the Gaussian binomial coefficient is a polynomial of degree k(nk) with non-negative integer coefficients. In other words,


where NnkαN0.



Observe that n0=1 and is a polynomial of degree 0.

The proof proceeds by induction.

Suppose that mj is a polynomial with coefficients in N0 and with degree j(mj), where mn, and jk. By equation (D.51),


The largest power of q in the above is k+k(nk)=k(n+1k) as required, and the coefficients of qα on the right-hand side are sums over integers in N0.

Similarly, again by equation (D.51),


Hence, if n1k+1 is a polynomial in q of degree (k+1)((n1)(k+1)) and with coefficients in N0, then nk+1 is a polynomial in q of degree (k+1)(n(k+1)) and with coefficients in N0. Notice that k+1k+1=1.

The q-binomial theorem is usually stated as


but it is also encountered as


The proof of the last equality proceeds by the counting of partitions.

The q-binomial theorem gives rise to the Jacobi triple product identity


where tˉ=1t.

The identity


is also useful [8]. By the q-binomial theorem in equation (D.53), it follows that


D.5.2 Directed paths and the q-binomial coefficient

There is a close connection between Gaussian binomial coefficients and D.9 (see reference [467]). Consider the square lattice L2 and let L+2 be the positive half-lattice with the boundary L+2 as the x-axis. In figure D.1, directed paths from the origin in L+2 give only north and east steps. The path oversteps area α‎ in the first quadrant of L2 underneath the path and to the left of the endpoint of the path.

Then the number of such paths of length n is related to Nnki and Gaussian binomial coefficients (see lemma D.9) by the following lemma. (p.570)

Appendix D Asymptotic approximations

Fig. D.1 A staircase walk from the origin to the point (r,nr) overstepping an area α‎.

Lemma D.10

The number of square lattice directed paths in L2, of length n, from the origin to the point (r,nr), giving only north and east steps and which overstep an area of size α‎ in the first quadrant of L2 is Nnrα.


This is true for any α‎ if n=1, and 0r1. Suppose that the lemma is true for any mn.

Consider m=n+1. By equation (D.51),


If coefficients of qα are compared, then


This result is interpreted in figure D.2. By the induction hypothesis, the term Nnrα counts the number of walks of length n, from (0,0) to (r,nr), and overstepping area α‎.

Appending a vertical step to paths turn these into walks of length n+1 which contribute towards N(n+1)rα

In a similar fashion, Nn(r1)(α+rn1) counts the number of walks from the origin to (r1,nr+1) and which enclose the area α+rn1. If a horizontal edge is appended from (r1,nr+1) to (r,nr+1), then it encloses area α‎. Thus, N(n+1)rα counts the number of walks from (0,0) to (r,nr+1) and which overstep area α‎.

Appendix D Asymptotic approximations

Fig. D.2 Any staircase walk of length n+1 from the origin to (r,n+1r) and which oversteps area α‎ has either a north step or an east step as its last step. If the last step was north, then it can be deleted to find Nnrα. If it was to the east, then deleting the last step also removes the last column, and this gives Nn(r1)(α+rn1).

Putting q=1 gives the corollary


Figure D.1 is also a Ferrer’s diagram of a partition. Thus, let the number of partitions of αN into r parts with largest part k be denoted ρk,r(α). Then ρk,r(α)=N(k+r)rα.

The generating function of ρk,r(α) for fixed k and r is


See reference [531] for a different proof of this result.

The generating function of partitions follows from this as


where t is the generating variable conjugate to perimeter length.

D.5.3 Theta functions, and partial theta functions

The Jacobi θ‎-function is defined by


(p.572) ϕ(q)=θ(1,q) is the Ramanujan θ‎-function. The Jacobi triple product identity may be cast as


By expanding the second and third products on the left-hand side, this becomes


where t=e2πiz. Putting t=1 gives


This last identity may also be obtained from the Ramanujan θ‎-function, which is defined as


The Jacobi triple product becomes


By choosing a=b=q in the above, Ramanujan’s ϕ‎-function ϕ(q)=f(q,q) is recovered:


Other identities may be recovered; for example, if a=q, and b=q3, then


and, if a=q, and b=q2, then


This identity is the famous pentagonal number theorem [184].

(p.573) The summation in the series definitions of θ‎-functions given above is over all of Z. It may in some instances be necessary to have to have the summation only over N. This restriction gives rise to partial θ-functions. An example is encountered in equation (D.63), which may be stated as


This is related to Gauss’s formula (see for example [8]):


More generally, a partial θ‎-function has the form


Some identities for partial θ‎-functions are known. For example, in reference [10] it is shown that


D.5.4 Asymptotics for (q;q)

A good starting point is the identity in equation (D.68). The left-hand side converges quickly if |q|1, but, when q is close to 1, another approach is necessary.

Theorem D.11 (Poisson’s sum formula)

Suppose that f is continuous for all tR, and k=f(t+k) is uniformly convergent for t[0,1]. Then


for all values of t where the right-hand side converges.


The function


is continuous and periodic with period T=1. In a Fourier expansion of h the coefficients would be


Moreover, by Fejér’s theorem, n=ane2πint is Cesàro summable to h(t) for all t (since h is continuous and periodic).

(p.574) Hence, by replacing h in the last integral with the uniformly convergent series over f, one obtains


The right-hand side evaluates to an, and therefore the Fourier series for h(t) is as claimed above.

Corollary D.12 (The θ‎-transformation formula)

For all values of t,sC, such that Re(s)>0,



Put f(t)=eπst2 in theorem D.11. Then n=f(t+n) converges uniformly for t[0,1], and Re(s)>0. The Poisson sum formula gives


where the integral above gives the Fourier coefficients. It remains to evaluate these coefficients.

Assume that s>0 and substitute y=sx:


The contour integral on the right evaluates as


using Cauchy’s theorem. This completes the evaluation of the Fourier coefficients in equation (D.73).

Substitution of the result and replacing nn in the summation on the right-hand side of equation (D.73) completes the proof.

Corollary D.12 gives a suitable expansion for (q;q); see, for example, reference [359] for an expansive treatment.

Theorem D.13

For Euler’s function,


where r=e4π2logq. For q(0,1) the right-hand side converges quickly.



Put t=16+π3ilogq, put q3=e2πs and define r by (logr)(logq)=4π2. Substitute these variables in the left-hand side of Corollary D.12 and then simplify. This shows that


Comparison to equation (D.68) gives


It remains to simplify the right-hand side.

Substitute t and s on the right-hand side and simplify:


The sum on the right-hand side is absolutely convergent if |r|<1. Collecting terms,


The right-hand side is evaluated by summing along n in residue classes modulo 6: replace n6n+ and sum over ℓ from 3 to 2.


Comparing the terms in the sum over ℓ shows that the terms for =2 and =1 cancel. The terms for both =3 and =2 are equal under the exchange of nn, up to phase factors. This is similarly the case for =1 and =0. This simplifies the expressions above to

(q;q)=(rq)1/242sn=(r(3n+1)(2n+1)cos(2π6(6n+52))                                             +rn(n+6)cos(2π6(6n+12))).

Evaluate the cosines and replace s=3logq2π to complete the proof.

Taking logarithms of the result in theorem D.13 and keeping the n=0 term gives the following asymptotic formula for (q;q) as q1:

Theorem D.14

The function log(q;q)=π26logq+12log2πlogq+O(logq).

(p.576) This gives the approximation

(q;q)=2πlogqeπ26|logq|+O(log(q))as q1.

For additional results, see, for example, the paper by Moak [425].

D.5.5 Asymptotics for (t;q)

First examine the limit limn(t;q)n for q(0,1) and assume that 0<tqk<1 for all k1.

Theorem D.15

If q<1, and 0<tqk<1 for all k1, then 0<(t;q)1.


Surely, 0(t;q)n1 for all n0, and (t;q)n is monotone decreasing, so the limit limn(t;q)n exists and is less than or equal to 1.

It remains to show that the limit is not 0.

For any positive p<1, log(1p)p1p. Moreover, for any small ϵ>0, there exists a N0N such that 0<1ϵ<1tqk if k>N0, since q<1 and since t0. Hence, log(1tqk)tqk1ϵ if k>N0.

Thus, assume that n>N0+1; then

(t;q)n=expk=0n1log(1tqk)expk=0N0log(1tqk)+t1ϵi=N0+1n1qk,if n>N0+1;=expk=0N0log(1tqk)+tq1ϵ1qnN011q.

Take n to obtain


which is greater than 0.

Asymptotic approximations for the q-Pochhammer function (t;q)n can be determined using the Euler-Maclaurin theorem. This can be determined directly or indirectly by first determining an approximation for the q-gamma function (see, for example, references [425] and [468]).

Define Li2 to be the dilogarithm:


(p.577) Theorem D.16

If 0<t<1, and 0<q<1, then




For fixed t<1, this term vanishes as q1.


The Euler-Maclaurin formula gives




The integral over log(1tqx) can be done by expanding first the logarithm and then integrating term by term; the result is a sequence of terms giving rise to dilogarithms and logarithms.

It remains only to examine the remainder. Observe that

B2B2(xx)=13(xx)(xx)243if x[0,n1].

Next, consider the derivative in R1 above and compute it to see that


This completes the proof.

Taking n in theorem D.16 gives the following corollary:

Corollary D.17

If ϵ>0, and t[0,1ϵ], and if q(0,1), then


or if Li2(t)+Li2(1t)=π26log(t)log(1t) is used, then


where R1 approaches 0 uniformly as q1 for any t[0,1ϵ].

(p.578) By this corollary,


where R10 uniformly as q1. For example, if t=qn<q<1 for nN, then


D.6 Asymptotics from the generating function

If the generating function g(t) of a function qn on N, defined by


is known, then qn may in principle be found by using Darboux’s theorem. Darboux’s theorem has the following formulation (see, for example, reference [443]).

Theorem D.18 (Darboux’s theorem)

Let ψ(t) be an analytic function with Laurent expansion


in the annulus 0<|t|<r.

Let χ(t) be a function which is analytic in 0<|t|<r and with Laurent expansion given by


in 0<|t|<r.

Suppose that the difference of the m-th derivatives of ψ(t) and χ(t) has a finite number of singularities at t=tj such that


for some positive constants σj, as ttj. Then

an=bn+o(rnnm)as n.

(p.579) D.7 Convergence of continued fractions

Finite fractions are denoted by


(For example, S1=a1b1, and S2=a1b1+a2b2).

Taking n gives the infinite continued fraction S. The n-th approximation to S is Sn(s), obtained by truncating the fraction at n and putting bn=c:


Useful theorems on the convergence of continued fractions are the following.

Theorem D.19

(Pringsheim [474]) Let an and bn be sequences in R such that |bn|>|an|+1. Then the continued fraction k=1akbk converges absolutely to fR with 0<|f|<1.

Theorem D.20

(Worpitzky [572]) Let an be a sequence in C and let K be a continued fraction given by


If 0<|an|14 for all n2, then K converges absolutely and 0<|K|12. Moreover, if, in addition, Sn(b)=Kk=1nak1, where an=b and |b|12 is the n-th approximant of K, then 0<|Sn(b)|12.

Theorem D.21 (Van Vleck [554])

If rn>0, then a condition that is necessary for the continued fraction



to converge for all values of θn is that the series


is convergent. This condition is also sufficient if rn<1 for all values of n.