Prof. Knuth lecture about $ \pi $ and random maps

Question

In this video, Prof. Knuth talks about an interesting combinatorial problem: suppose you have a random map $ f\colon \{ 1, 2, 3,\ldots, n \} \rightarrow \{ 1, 2, 3,\ldots, n \}$. If you consider the values $( 1, f(1), f(f(1)), \ldots \}$, what is the mean value of the number of steps needed to find one of the previous values a second time?

Knuth sketches that the solution goes like $ 1 + \frac{\sqrt {\pi n}}{2} $, adding that this is a case where $ \pi $ shows up with apparently no connection with the circle. How is it possible to prove that result? Is there any hidden connection with the circle?

Answer 1

To sketch the argument we appeal to previous work on the tree function and random mapping statistics, namely the

• Pusieux series for the tree function and

• Cumulative EGF for cycle size and tail length.

We get for the former

$$T(z) = 1 -\sqrt{2} \sqrt{1-ez} + {\frac{2}{3}} (1-ez) -\frac{11 \sqrt{2}}{36} (1-ez)^{3/2} + {\frac{43}{135}} (1-ez)^2 \\ -\frac{769 \sqrt{2}}{4320} (1-ez)^{5/2} + {\frac{1768}{8505}} (1-ez)^3 - \frac{680863 \sqrt{2}}{5443200} (1-ez)^{7/2} + \cdots$$

and the latter

$$H(z) = \frac{T(z)+T(z)^2}{(1-T(z))^4}.$$

This cumulative EGF gives precisely the statistic we are trying to compute.

Substitute the first into the second to get

$$\frac{1}{2 (1-ez)^{2}} -\frac{\sqrt{2}}{12 (1-ez)^{3/2}} -\frac{1}{2 (1-ez)} +\frac{133 \sqrt{2}}{2160 \sqrt{1-ez}} \\ +\frac{107}{3240} -\frac{157 \sqrt{2}\, \sqrt{1-ez}}{120960} +\cdots.$$

We get from the dominant asymptotic (first term)

$$\frac{1}{2} \frac{n!}{n^n} [z^n] \frac{1}{(1-ez)^2} = \frac{1}{2} \frac{n!}{n^n} (n+1) \exp(n).$$

Using Stirling this becomes

$$\frac{1}{2} (n+1) \exp(n) \frac{1}{n^n} \frac{n^n}{\exp(n)} \sqrt{2\pi n} = \frac{1}{2} (n+1) \sqrt{2\pi n}.$$

We are asking for cycle size and tail length starting from node one. The EGF computes the statistic for all nodes, all mappings. By symmetry and working with grand averages we may divide by $n$ to get the value for node one as none of the nodes are distinguished in any way. We also need to add one to account for the last step hitting a node that we have seen before. (This is one more than the count of the nodes on the cycle and those on the tail where the tail length does not include the node that is shared with the cycle.) Putting it all together we obtain

$$1 + \frac{1}{2} \left( 1 + \frac{1}{n} \right) \sqrt{2\pi n} \sim 1 + \sqrt{\frac{\pi n}{2}}.$$

The values from the cumulative EGF are

$$1, 12, 153, 2272, 39225, 776736, 17398969, \\ 435538944, 12058401393, 366021568000, \ldots$$

We get from the second term

$$-\frac{\sqrt{2}}{12} \exp(n) {n+1/2\choose n} = -\frac{\sqrt{2}}{12} \exp(n) {n-(-3/2)-1\choose n} \sim -\frac{\sqrt{2}}{12} \exp(n) \frac{\sqrt{n}}{\Gamma(3/2)}.$$

With Stirling and scaling by $n!/n^n$ this makes for a contribution of

$$-\frac{\sqrt{2}}{12} n \frac{\sqrt{2\pi}}{\sqrt{\pi}/2} = -\frac{1}{3} n.$$

The third term is easy and we get on scaling again

$$- \frac{1}{2}\sqrt{2\pi n}.$$

Collecting the three we find for the cumulative statistic

$$\frac{1}{2} n \sqrt{2\pi n} - \frac{1}{3}n + \cdots.$$

Commentary. Here the tail length does not refer to the size of the tree attached at a node that is not on a cycle but rather the nodes on the path from a node to its eventual cycle. The node where it is attached to the cycle is also the repeat node that we see in the iterates of the map, which are sets of cycles of trees.

Answer 2

Is there any hidden connection with the circle?

As Marko Riedel's excellent answer shows, the combinatorial details here are complicated but the $\pi$ shows up via Stirling's formula / Stirling's approximation for the factorials

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

Here is a much simpler combinatorial situation in which the same $\sqrt{\pi}$ shows up with no apparent connection to the circle, which is also connected to Stirling's formula, and where the relationship to the circle can be explained more conceptually. The question is about flipping coins:

Suppose I flip $2n$ fair coins. What's the asymptotic probability that exactly $n$ of them are heads, as $n \to \infty$?

People are often surprised to learn that this probability converges to $0$. The exact probability can be expressed in terms of binomial coefficients as

$$p_n = \frac{1}{2^{2n}} {2n \choose n}.$$

We can get an asymptotic from here via two applications of Stirling's formula to the numerator and denominator of ${2n \choose n} = \frac{(2n)!}{n!^2}$; various cancellations occur and the result is

$$\boxed{ p_n \sim \frac{1}{\sqrt{\pi n}} }.$$

The appearance of $\pi$ in this expression can be explained conceptually using the central limit theorem, which tells us that as $n \to \infty$ the probability distribution over the number of heads converges to a normal distribution; evaluating the density of this normal distribution at its mean produces the above probability $p_n$. In other words, from the perspective of the central limit theorem the $\sqrt{\pi}$ that appears here is the value of the Gaussian integral

$$\int_{-\infty}^{\infty} e^{-x^2} \, dx = \sqrt{\pi}.$$

In turn, there is a nice argument explaining where this $\pi$ comes from via squaring the above integral to obtain the 2d integral $\int_{\mathbb{R}^2} e^{-x^2-y^2} \, dx \, dy$, then evaluating this integral in polar coordinates to obtain $\pi$. So there is a circle here but it appears quite indirectly, in the fact that the multivariate Gaussian is spherically symmetric so the multivariate Gaussian integral reduces to a (constant) integral over spheres and an integral over radii. (There is also a way to explain the appearance of this $\pi$ in terms of the Fourier transform, using the fact that the Fourier transform of a Gaussian is another Gaussian.)

So, that's the hidden connection to the circle! Many other asymptotic questions in combinatorics also end up having answers that are asymptotically Gaussian, due in some sense to generalizations of the central limit theorem, so $\sqrt{\pi}$'s also tend to appear more generally. I wouldn't be surprised if this specific question was one of them although I'm not familiar with the details.