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 \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 \infty $ exist, and equal $0, 1$ respectively.