[Math] Combinatorial\Probabilistic Proof of Stirling’s Approximation

asymptoticsco.combinatoricsrandom walks

Stirling's approximation is the following well-known asymptotic result:

$$n! \approx \left(\frac{n}{e}\right)^n \sqrt{2 \pi n}$$

This result has several analytical proofs, for example via Laplace's method, the trapezoidal rule (and Euler–Maclaurin formula for an asymptotic expansion) or Hayman's method (essentially Cauchy's formula). There are also other (usually ad-hoc) proofs.

The result is applied often in combinatorics and probability, especially in the study of random walks. I want a result which is the other way around – a combinatorial\probabilistic proof for Stirling's approximation. I'm not sure if this is possible, but to convince you that it might be I'll give some partial results.

First, write $n! = \left(\frac{n}{e}\right)^n f(n)$. We'll obtain bounds related to $f(n)$:

Consider $\{S_n\}_{n\ge 0}$, the random walk on $\mathbb{Z}^{d}$, with $S_0=\vec{0}$. It is recurrent iff $\sum_{n\ge 1} P(S_{2n} = \vec{0})$ diverges. This series is $\sum_{n\ge 1} (2d)^{-2n} \sum_{a_1+\cdots+a_d=n} \binom{2n}{a_1,a_1,a_2,a_2,\cdots,a_d,a_d}$. For $d=1$, this becomes $\sum_{n\ge 1} \frac{\binom{2n}{n}}{4^n} = \sum_{n\ge 1} \frac{f(2n)}{f^2(n)}$. There's is Stirling-free proof for the recurrence of the 1-dimensional random walk, using a criterion due to Nash-Williams.
Similarly, for $d=2$, there's a rotation trick that shows $\sum_{n\ge 1} P(S_{2n} = \vec{0})=\sum_{n\ge 1} \left( \frac{\binom{2n}{n}}{4^n} \right)^2= \sum_{n\ge 1} \left( \frac{f(2n)}{f^2(n)} \right)^2$. Again, the Nash-Williams criterion proves the recurrence of the 2-dimensional random walk without Stirling, and hence the divergence of said series.
Back to the 1-dimensional case. Using the reflection principle, the probability that the random walk returns to the origin during the first $2n$ steps is $1-\frac{\binom{2n}{n}}{4^n} = 1-\frac{f(2n)}{f^2(n)}$, and this tends to 1 as the walk is recurrent.
Still with the 1-dimensional case. One can calculate $E|\frac{S_n}{\sqrt{n}}|$ explicitly – it is $2^{1-n} \sqrt{n}\binom{n-1}{\lfloor \frac{n-1}{2} \rfloor}$. On the other hand, the CLT together with the notion of uniform integrability justifies the following limit: $\lim_{n\to\infty} E|\frac{S_n}{\sqrt{n}}| = E|N(0,1)| = \frac{2}{\sqrt{2\pi}}$. When $n$ is odd this implies $\sqrt{n} \frac{f(n-1)}{f^2(\frac{n-1}{2})} \to \frac{2}{\sqrt{2\pi}}$.

So if we assume $f(n) \approx C \cdot n^{\alpha}$, the first results give bounds on $\alpha$ ($\alpha \le 1, \alpha \le 0.5, \alpha >0$) and the last one gives the true value of $\alpha$ and $C$. The fact that the 3-dimensional random walk is transient implies $\alpha \ge \frac{1}{3}$, but I don't know how to prove it without tools that prove Stirling's approximation.

Questions:

Can we remove\relax the assumption $f(n) \approx C \cdot n^{\alpha}$ somehow? Can we use less analysis than we used in the 3rd result? Are there other combinatorial approaches to the problem that give partial results (or even the full one)? Can the fact that the 3-dimensional random walk is transient be proved Stirling-free (and preferably combinatorially)?

Best Answer

The Wikipedia page List of probabilistic proofs of non-probabilistic theorems has a reference to the paper:

Blyth, Colin R.; Pathak, Pramod K. A Note on Easy Proofs of Stirling's Theorem. Amer. Math. Monthly 93 (1986), no. 5, 376–379. MR 1540867 DOI 10.2307/2323600

in which several simple proofs of Stirling's approximation are given, using the central limit theorem on Gamma or Poisson random variables.

Related Solutions

Probability – Probability of a Random Walk Crossing a Straight Line

I wrote a Maple program in 2003 which computes $P(\alpha)$ (both the "upper" and "lower" values) for a given rational number $\alpha$, much in line with the method described by Johan. I think I was able to compute it for all $\alpha=a/b$ for integers $1\le a\lt b\le 300$ in a couple of hours, so the program could probably compute fairly good approximations to $P(1-2/\log_2(p))$ when $p$ is not too large. (Edit: When $p$ is large, $1/2$ will be a very good approximation. For example, if $p\gt1000$ then $0.499\lt P(1-2/\log_2(p))\lt1/2$.)

I didn't publish any of this, but much of it is contained in the article "The Maximum Average Gain in a Sequence of Bernoulli Games" by Wolfgang Stadje (American Mathematical Monthly, December 2008).

EDIT: Since I don't have access to Maple anymore, I translated the program to Matlab:

function p=p(s,t);
d=gcd(s+t,2*t);
s=(s+t)/d;
t=2*t/d;
pol=zeros(1,t+1);
pol([1 s+1 t+1])=[1 -2 1];
r=roots(pol);
[rsort,i]=sort(abs(r));
p=1-prod(abs(1-r(i(1:t-s))));

The program computes $P(s/t)$ for integers $0\lt s\lt t$, by computing $1$ minus the product of $1-r$ for those zeroes $r$ of $z^{2t/d}-2z^{(t-s)/d}+1$ that have absolute value less than $1$ (there are $(t-s)/d$ of them), where $d=\gcd(s+t,2t)$.

By the way, in my notes I found the lower bound $P(\alpha)\ge A$, where $\alpha=1-\frac{2\log A}{\log(2A-1)}$, with equality for $\alpha=(k-2)/k$. I think Johan was involved in obtaining this bound.

EDIT (May 14): So, here is a fairly detailed proof of the formula used in the program above.

Lemma 1. For integers $0\lt 2b\lt a$, the polynomial $g(z)=z^a-2z^b+1$ has no multiple zeros and exactly $b$ zeroes inside the unit circle.

Proof. If $g(z)=g'(z)=0$ then $z\ne 0$ and $$0=g'(z)=az^{a-1}-2bz^{b-1}=z^{b-1}(az^{a-b}-2b),$$ so $az^{a-b}-2b=0$. Hence, $0=g(z)-g'(z)*z/a=1-2(1-b/a)z^b$ so that $|z|^b=\frac1{2(1-b/a)}=\frac a{2(a-b)}$. Also, $az^{a-b}-2b=0$ so $|z|^{a-b}=2b/a$. This implies that $$\left(\frac a{2(a-b)}\right)^{a-b}=\left(\frac{2b}a\right)^b.$$ This can be rewritten as $2(1-b/a)^{1-b/a}(b/a)^{b/a}=1$. But it is easily checked that $2(1-y)^{1-y}y^y\gt1$ for $0\lt y\lt1/2$, a contradiction.

The second part can be proved by a straight forward application of Rouché's theorem.

Lemma 2. Suppose that $\sum_{i=1}^kA_ir_i^{-j}=1$ for $1\le j\le k$. Then $\sum_{i=1}^kA_i=1-\prod_{i=1}^k(1-r_i)$.

Proof. The equations can be seen as a system of linear equations in $A_1,\dots,A_k$, and the result can be obtained by using Cramer's rule and Vandermonde determinants. I skip the details. (Actually, I think I had a simpler proof of this lemma, but I could neither find it in my notes, nor figure it out right now.)

Now, let $L=\max_{n\gt0}{S_n/n}$, so that $P(\alpha)=P(L\gt\alpha)$. Also, let $Y_i=(X_i+1)/2$ and $T_n=\sum_{i=1}^nY_i$ (so that $T_n$ is a random walk with steps $0$ and $1$ instead of $\pm 1$). (The main reason for this is that my original result was for $T_n$, but I also think that the formulae get a little simpler in this case.)

Let me restate the result I am going to prove:

Theorem. For integers $0\lt s\lt t$, $P(s/t)=1-\prod_{i=1}^{t-s}(1-r_i)$, where $r_1,\dots,r_{t-s}$ are the zeroes of $z^{2t}-2z^{(t-s)}+1$ that have absolute value less than $1$.

Proof. Let $M=\max_{n\gt0}{T_n/n}$ and $Q(\alpha)=P(M\gt\alpha)$. I will prove the corresponding result for $Q(s/t)$, and then translate it to $P$, using the fact that $T_n=(S_n+n)/2$ which implies that $P(\alpha)=Q((\alpha+1)/2)$.

Suppose then that $1/2\lt s/t\lt1$ and consider $Q(s/t)$. Just as Johan did, we define another random walk $U_n=\sum_{i=1}^nZ_i$ with steps $Z_i=s$ or $Z_i=s-t$ so that $Q(s/t)$ equals the probability that $U_n$ will ever reach $-1$, define $f(j)$ as the probablity that $U_n$ will reach $-1$ when it is currently at $j$, and find that $f(j)=f(j+s)/2+f(j+s-t)/2$ for $j\ge0$. The characteristic equation of this recursion is $g(z)=z^t-2z^{t-s}+1=0$. By Lemma 1 and since $f(j)$ tends to $0$ as $j$ tends to infinity, we must have $f(j)=\sum_{i=1}^{t-s}A_ir_i^j$, where $r_1,\dots,r_{t-s}$ are the (necessarily simple) zeroes of $g(z)$ inside the unit circle. Since $f(j)=0$ for $s-t\le j\le -1$, Lemma 2 implies that $Q(s/t)=f(0)=\sum_{i=1}^{t-s}A_i=1-\prod_{i=1}^{t-s}(1-r_i)$.

Now, if $0\lt s/t\lt1$ then $P(s/t)=Q((s+t)/(2t))$, which, by what we have just proved, equals $1-\prod_{i=1}^{t-s}(1-r_i)$, where $r_1,\dots,r_{t-s}$ are the zeroes of $z^{2t}-2z^{t-s}+1$ inside the unit circle. This concludes the proof.

[Math] Simple Random Walk on a Locally Finite Graph – when is it recurrent

The fundamental result the completely characterizes recurrent/transient graphs is that a graph is recurrent if and only if the effective resistance of the graph, when considered as an electric network where every edge has resistance one, from some/any vertex to infinity is infinite. This is true also when the degrees are unbounded.

Of course, to use this, you need to understand how this resistance is defined and what method there are to show it's finite/infinite. The easiest ways to bound the the resistance from below is finding cutsets, sets which separate some specified vertex from infinity. If you have a disjoint sequence of such cutsets of sizes $a_n$, the effective resistance is at least $\sum_n 1/a_n$, so if this sum is infinite, the graph is recurrent. This is called the Nash-Williams criteria and it's easy to see that graphs growing slower than quadratic satisfy it (in fact, a slightly bigger growth rate is still OK).

In the other direction, one can bound the resistance from above by using flows. This is slightly more involved, I can elaborate later, if there is a demand.

Best Answer

Related Solutions

Probability – Probability of a Random Walk Crossing a Straight Line

[Math] Simple Random Walk on a Locally Finite Graph – when is it recurrent

Related Question