Deadline: December 1, 2020

Puzzle Editor Anirban DasGupta offers “more or less a textbook problem” this time, which pertains to various important questions on linear polymers. He says, “It will be easy for you to read about the connections; you can figure out most of the parts very quickly.” Here is the problem:

Imagine a particle conducting a walk on the traditional square lattice, starting at the origin $(0,0)$. That is, at any time during the walk, the particle goes one unit distance to either the east, or the west, or the north, or the south. An $n$-walk is a walk that has taken $n$ steps. The walk is called self-avoiding if the particle does not visit any given state twice.

Let $f(n)$ denote the number of n-walks that are self-avoiding.

(a) Compute $f(n)$ for $n=2,3$, and justify how you got these values.

(b) Compute $f(4)$ if you can, or place it within good lower and upper bounds.

(c) Try to give non-trivial lower and upper bounds on $f(n)$ of the form $c{k}^n$ for $c>0$ and $k$ a positive integer.

Solution to Puzzle 30

Puzzle Editor Anirban DasGupta writes on the previous problem, which appeared in the August issue:

Well done to student member Bhargob Kakoty [pictured left], pursuing his Master’s degree in Statistics at the Indian Statistical Institute in Delhi, who submitted a correct solution to the first part of the puzzle.

The probability that $X_n$ is a new value is $p_n=\sum _{j:f(j)>0}f(j)(1-f(j){)}^{n-1}$, and apply the DCT to conclude that $p_n\to 0$ as
$n\to \mathrm{\infty }$.

By direct calculation, or by a familiar geometric decomposition, $E({\tau }_2)=1+\sum _j\frac{f(j)}{1-f(j)}$; for the Poisson case, the expression is the infinite series obtained by substituting $f(j)=\frac{e^{-\lambda }{\lambda }^j}{j!}$.

The series does not seem to have a closed form formula. The same argument results in $E({\tau }_3)$ as a double series.

For the Poisson case, $P({\tau }_2=2)$ simplifies. Indeed,
$$P({\tau }_2=2)=1-\sum _j{f}^2(j)=1-e^{-2\lambda }\sum _j\frac{{\lambda }^{2j}}{(j!{)}^2}$$
$$=1-e^{-2\lambda }{I}_0(2\lambda ),$$
where $I_0(z)$ is the modified first kind Bessel function $I_0(.)$.

Using an integral representation for $I_0(2\lambda )$ and carrying in the $e^{-2\lambda }$ term inside that integral, it follows that $P({\tau }_2=2)$ is monotone, and Fatou tells you that the limits as $\lambda \to 0,\lambda \to \mathrm{\infty }$ exist, and equal $0,1$ respectively.