Families of prudent self-avoiding walks

Abstract

A self-avoiding walk (SAW) on the square lattice is prudent if it never takes a step towards a vertex it has already visited. Prudent walks differ from most classes of SAW that have been counted so far in that they can wind around their starting point. Their enumeration was first addressed by Préa in 1997. He defined 4 classes of prudent walks, of increasing generality, and wrote a system of recurrence relations for each of them . However, these relations involve more and more parameters as the generality of the class increases. The first class actually consists of partially directed walks, and its generating function is well-known to be rational. The second class was proved to have an algebraic (quadratic) generating function by Duchi (2005). Here, we solve exactly the third class, which turns out to be much more complex: its generating function is not algebraic, nor even D-finite. The fourth class -- general prudent walks -- is the only isotropic one, and still defeats us. However, we design an isotropic family of prudent walks on the triangular lattice, which we count exactly. Again, the generating function is proved to be non-D-finite. We also study the asymptotic properties of these classes of walks, with the (somewhat disappointing) conclusion that their endpoint moves away from the origin at a positive speed. This is confirmed visually by the random generation procedures we have designed.

References in corpus (3)

• Walks with small steps in the quarter plane
• Two Non-holonomic Lattice Walks in the Quarter Plane
• Scaling Limit of the Prudent Walk

Cited by in corpus (15)

• Greedy walk on the real line
• Scaling Limit of the Prudent Walk
• A variational formula for the free energy of the partially directed polymer collapse
• Weakly directed self-avoiding walks
• Endless self-avoiding walks
• Interacting partially directed self-avoiding walk: a probabilistic perspective
• Stability of the Greedy Algorithm on the Circle
• A solvable non-directed model of polymer adsorption
• A pumping lemma for non-cooperative self-assembly
• The Enumeration of Prudent Polygons by Area and its Unusual Asymptotics
• Scaling limit of the uniform prudent walk
• Random walks avoiding their convex hull with a finite memory
• Collapse transition of the interacting prudent walk
• The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation
• Partition function zeros of adsorbing Dyck paths