Exactly-solvable self-trapping lattice walks. II. Lattices of arbitrary height

This paper establishes that the generating functions for growing self-avoiding walks and Greek key tours on half-infinite strips of finite height are rational by providing a combinatorial finite state machine construction, while also employing Monte Carlo simulations to analyze walk properties on unbounded lattices where exact solutions are unavailable.

The Gist

Imagine you are walking through a giant, endless maze made of city blocks. You have a strict rule: you can never step on the same corner twice. This is what mathematicians call a "Self-Avoiding Walk."

Now, imagine you are blindfolded and you have to keep walking forward. At every intersection, you pick a random open path to take. But here's the catch: eventually, you will reach a corner where every single path around you has already been walked on. You are stuck. You are trapped.

This paper is about figuring out, with perfect mathematical precision, how long it usually takes for a walker to get trapped in a maze that is only a few blocks wide.

The Big Problem: The "71-Step" Mystery

For decades, scientists have known that if you walk on an infinite, flat grid (like a giant checkerboard), you will get trapped after taking about 71 steps on average. But this number was found using computer simulations (guessing and checking millions of times). No one had ever found the exact math to explain why it is 71. It was like knowing a cake tastes sweet but not knowing the exact recipe.

The Solution: The "Frame-by-Frame" Camera

The authors, Jay Pantone, Alexander Klotz, and Everett Sullivan, developed a new way to solve this. Instead of trying to simulate the whole walk at once, they broke the maze down into tiny, manageable snapshots.

Think of the maze as a long hallway. They built a "camera" that only looks at two columns of the hallway at a time (a 2-block wide slice).

1. The Snapshot (Frame): They look at the two columns and record: "Where is the walker? Which paths are connected? Which parts of the path are already linked together?"
2. The Transition: They ask, "If I move the camera one step to the right, what are all the possible new snapshots I could see?"
3. The Machine: They turned these snapshots into a giant flowchart (a Finite State Machine). This flowchart is like a choose-your-own-adventure book where every page is a valid snapshot of the maze, and every arrow is a legal move the walker can make.

Because the hallway is only a fixed height (say, 2 blocks, 3 blocks, or 4 blocks tall), the number of possible snapshots is finite. This allows them to write down a single, perfect mathematical formula (a "generating function") that counts every possible way the walker can get trapped.

The Two Ways to Walk

The paper explores two different "personalities" for the walker:

1. The Random Walker (Uniform Model): At every step, the walker picks a random open path with equal chance. This is like flipping a coin to decide where to go.
2. The Clingy Walker (Energetic Model): This walker prefers to walk next to its own past path. Imagine a polymer (a long molecule) that likes to stick to itself. If the walker is near its own trail, it's more likely to turn back toward it. This models how real polymers behave in bad solvents (like oil in water).

What They Found

Using their "camera" and "flowchart" method, they calculated the exact average number of steps a walker takes before getting stuck for mazes of different heights:

• 2-block wide maze: Trapped after 13 steps.
• 3-block wide maze: Trapped after ~19.3 steps.
• 4-block wide maze: Trapped after ~22.9 steps.
• 5-block wide maze: Trapped after ~26.5 steps.

By looking at these exact numbers, they could predict what happens in the "quarter-infinite" plane (a maze that is infinite in two directions, like a corner of a room). They estimated the answer to be ~45.8 steps. This is very close to the Monte Carlo simulation estimate of 45.4, giving them great confidence in their math.

Why This Matters

• Polymers and DNA: Real-world molecules, like DNA, often get squeezed into tiny channels (nanochannels). Understanding how they get "trapped" or how long they stretch out helps scientists design better medical tests and genomic mapping tools.
• Solving the "Greek Key" Puzzle: They also used this method to solve a different puzzle: How many ways can you walk through a small grid visiting every single square exactly once? (This is called a "Greek Key" tour, named after a pattern on ancient pottery). They solved this for grids up to 8 blocks high, confirming guesses that mathematicians had made for years.

The Takeaway

Before this paper, we had to guess the answers to these walking puzzles by running millions of computer simulations. Now, the authors have built a mathematical machine that gives the exact answer for any narrow hallway.

It's like going from guessing how many jellybeans are in a jar by shaking it, to having a formula that counts every single jellybean perfectly. This gives scientists a solid foundation to understand the complex behavior of molecules and polymers in the real world.

Technical Summary

1. Problem Statement

The paper addresses the problem of Growing Self-Avoiding Walks (GSAWs) on grid graphs. A GSAW is a directed walk on a lattice that:

1. Starts at a specific origin.
2. Never visits the same vertex twice (self-avoiding).
3. Grows step-by-step by choosing an unoccupied neighbor according to a specific probability distribution.
4. Terminates (becomes "trapped") when the current endpoint has no unoccupied neighbors.

While the mean trapping length for GSAWs on an infinite square lattice is a well-known empirical result (approximately 71 steps), it lacks an exact analytical solution. The authors aim to develop an exactly solvable model to compute the generating functions for GSAWs on half-infinite strips of arbitrary finite height ($h$). This allows for the exact calculation of:

• The mean trapping length (number of steps).
• The mean displacement (span in the x-direction).
• The distribution of these quantities under different probabilistic models.

2. Methodology

The core methodology involves constructing Combinatorial Finite State Machines (FSMs) (represented as directed graphs) that bijectively map walks on the graph to sequences of "frames."

A. The Frame Construction

The authors define a "frame" as a width-2 window moving from left to right across the grid. To ensure the walk remains self-avoiding and connected, a frame must encode more than just the edges present; it must encode:

• Segments: Ordered lists of paths sharing no vertices.
• Connectivity: Which segments are already connected by edges to the left of the current frame.
• Ordering: The sequence in which segments are traversed.
• Trapping Status: Whether the current endpoint is trapped.

B. The Directed Graph ($D_h$)

For a strip of height $h$, the authors construct a directed graph $D_h$ where:

• Vertices: Represent valid "frames" (states of the walk at a specific x-coordinate).
• Edges: Represent valid extensions of a frame to the next column. An edge exists from frame $F$ to $F'$ if $F'$ can be formed by extending $F$ into a new column and then "trimming" the leftmost column.
• Weights: Edges are weighted by $x^k y^d$, where $k$ is the number of new edges added and $d$ is the increase in displacement.

C. The Transfer Matrix Method

Once $D_h$ is constructed, the Transfer Matrix Method is applied. The generating function for the GSAWs is derived by inverting the matrix $(I - xM)$, where $M$ is the adjacency matrix of the graph. This guarantees that the resulting generating function is rational (a ratio of two polynomials).

D. Probabilistic Adaptations

The framework is adapted for two probabilistic models:

1. Uniform Model: The next step is chosen uniformly from all available unoccupied neighbors. The edge weights in the FSM are adjusted to include the probability of the transition.
2. Energetic Model: The probability of a step depends on the number of occupied neighbors of the target vertex (parameterized by a constant $C$). This mimics polymer behavior in poor solvents (attraction) or repulsive forces. This model requires width-4 frames (instead of width-2) to capture the necessary "neighbor-of-neighbor" information to calculate energies correctly.

E. Greek Key Tours

A modification of the FSM approach is used to enumerate Greek Key tours (Hamiltonian paths that visit every vertex in a finite $k \times n$ grid). The constraints are tightened to ensure every vertex in a new column is visited before moving on.

3. Key Contributions

1. Generalization to Arbitrary Height: Extends previous work (limited to height 2) to strips of arbitrary height $h$.
2. Rationality Proof: Proves that the generating functions for GSAWs on half-infinite strips of any fixed height are rational functions.
3. Algorithmic Construction: Provides a Python implementation to automatically construct the FSMs and compute generating functions for any height.
4. Exact Solutions for Probabilistic Models: Derives exact generating functions for both Uniform and Energetic models, allowing for the calculation of exact moments (mean, variance) rather than relying on Monte Carlo simulations.
5. Resolution of Conjectures: Uses the method to exactly enumerate Greek Key tours up to height 8, resolving previous conjectures regarding their generating functions and growth rates.

4. Key Results

A. Non-Probabilistic Results (Enumerative)

The authors computed the number of GSAWs for heights $h=2$ through $h=7$.

• Generating Functions: Explicit rational functions were derived for $h=2$ to $h=6$. For $h=7$, full functions were too large, but specializations (length-only or displacement-only) were computed.
• Asymptotic Growth: The connective constants ($\mu$) for the number of walks were calculated. For example, for $h=2$, $\mu \approx 1.618$; for $h=7$, $\mu \approx 2.332$. These match previous results for confined SAWs.

B. Probabilistic Results (Mean Trapping Lengths)

Using the Uniform Model, the authors calculated the exact mean trapping lengths ($\langle L \rangle$) and mean displacements ($\langle D \rangle$):

• Height 2: $\langle L \rangle = 13$, $\langle D \rangle = 7$.
• Height 3: $\langle L \rangle \approx 19.32$, $\langle D \rangle \approx 7.75$.
• Height 4: $\langle L \rangle \approx 22.98$, $\langle D \rangle \approx 7.83$.
• Height 5: $\langle L \rangle \approx 26.52$, $\langle D \rangle \approx 8.08$.

Extrapolation to Infinite Lattice:
By fitting an exponential decay model $N(h) = N_\infty(1 - e^{-\kappa h})$ to the exact results for $h=2$ to $5$, the authors estimate the mean trapping length for a quarter-infinite plane to be $N_\infty \approx 45.8$. This is remarkably close to the Monte Carlo estimate of $45.4$ for the quarter-infinite case and provides a theoretical bridge to the famous 71-step result for the fully infinite square lattice.

Energetic Model (Repulsive Walks):
In the limit of strong repulsion ($C \to 0$), the authors found that the trapping length reaches a plateau. For height 3, the plateau is exactly $3867/112 \approx 34.5$. This contrasts with the unconfined repulsive lattice value of $\approx 178.5$.

C. Greek Key Tours

The authors proved the generating functions for Greek Key tours on $k \times n$ grids are rational for $k \le 8$. They calculated the exact exponential growth rates for these sequences, confirming previous conjectures for $k=3, 4, 5$ and providing new data for $k=6, 7, 8$.

5. Significance

• Theoretical Rigor: The paper moves GSAW analysis from purely empirical (Monte Carlo) to exact analytical solutions for confined geometries.
• Polymer Physics: The results provide exact benchmarks for polymer scaling models, particularly regarding confined polymers (e.g., DNA in nanochannels) where displacement and trapping statistics are critical.
• Methodological Advance: The "frame" approach combined with finite state machines offers a scalable framework for solving other constrained lattice walk problems, including those with complex interaction energies.
• Bridging Scales: The ability to compute exact values for small strips and extrapolate them to infinite lattices provides a powerful tool for understanding asymptotic behavior in statistical mechanics.

In summary, this work provides a comprehensive, algorithmic framework for solving GSAW problems on strips of arbitrary height, yielding exact rational generating functions and precise statistical moments that deepen the understanding of self-trapping phenomena in lattice walks.