# Influence of Initial Entangled States on the Temperature-Dependent CHSH
Inequality.

Esteban Marulanda<EMAIL_ADDRESS>Andrés Gómez
<EMAIL_ADDRESS>Physics department, Universidad de Antioquia, Calle
70 No. 52-21, Medellín, Colombia

(August 28, 2024)

###### Abstract

We demonstrate that the temperature affects the validity of the CHSH
inequality in an open bipartite two-qubit system. Specifically, for initial
entangled states within the decoherence-free subspace (DFS), the CHSH
inequality remains temperature-independent. In contrast, other entangled
states exhibit a temperature threshold beyond which the inequality holds.

##  I Introduction

The advent of quantum information theory and the 50th-anniversary celebrations
of the original publication of Bell’s theorem in 2014 has only further
elevated the importance of Bell inequalities in modern physics 202 (2022).
Bell inequalities have played a pivotal role in the foundational analysis of
quantum mechanics, leading to insights that challenge our classical intuitions
about the nature of reality. Introduced as part of Bell’s Theorem in 1964,
these inequalities stem from considerations of local causality, the idea that
correlations between distant events should be explainable regarding local
factors, such as the common source of the particles in question Bell (1964).
Although initially confined to discussions among a small group of physicists
and philosophers, interest in Bell’s theorem has surged, particularly
following the groundbreaking experiments by Aspect and colleagues. Nowadays,
Bell inequalities are used to test entanglement in systems like photonic chips
that generate entangled states Chen et al. (2021).
However, those tests are primarily designed for systems with pure states. In
reality, most systems interact with an environment, and generally, the state
that describes the system of interest must be mixed. Therefore, the necessity
for investigating quantum correlations and their dependence on environmental
parameters is a task of vital importance. In the past years, much research has
focused on this. To highlight a few, Galve et al. (2010), contrary to the
conventional wisdom for a continuum variable setting, finds a high-temperature
entangled system. Chakrabarty et al. (2011) investigates various measures of
quantum correlations in mixed states that interact with an environment through
non-demolition and dissipative mechanisms. Marconi et al. (2022) presents an
example of a system with a quantum correlation robust against noise. Finally,
Fadel and Tura (2018) addresses a system of N spins in thermal equilibrium,
calculating a bound for the temperature of the multipartite Bell inequality.

While there is extensive literature on the topic, the relationship between the
CHSH inequality for an open system and temperature remains unclear.
Additionally, the possible underlying mechanisms that permit the existence of
entangled states in high-temperature regimes. Could this phenomenon depend on
the initial entangled state coupled to the environment? This article aims to
explore CHSH inequality for an open quantum system composed of two qubits and
discuss the conditions for which an initial entangled state after coupling
with an environment remains entangled even in the high-temperature regime. If
an initial state doesn’t maintain its entanglement in this high-temperature
context, we then establish a specific temperature threshold beyond which the
CHSH inequality is violated.

This paper is organized as follows: Section 2 presents an example of a system
defined by a Bell-type state. In the absence of external interactions, this
system violates the CHSH inequality. We explore how interaction with a bosonic
bath and temperature variation can affect such inequalities. Section 3 is
dedicated to analyzing why some initial states have a violation of the CHSH
inequality that is not affected by temperature. We conclude the study in
Section 4.

##  II Methodology.

Let us consider the version of the EPR paradox initially proposed by David
Bohm Bohm (1951). This involves a system of two spin-1/2 particles that move
far apart enough that their mutual interaction becomes negligible. Among the
possible final states, let us consider a Bell-type state,

$\left|\psi_{AB}\right\rangle=\frac{1}{\sqrt{2}}\left(\left|0_{A}1_{B}\right\rangle-\left|1_{A}0_{B}\right\rangle\right),$
(1)

where $A$ and $B$ represent the spin to be measured by Alice and Bob,
respectively. Since both are unaware of the system’s orientation in which the
state 1 is prepared, they perform measurements of the received spin in an
arbitrary basis rotated by $\theta$ and $\phi$ concerning the preparation
reference frame. Considering a statistical ensemble of bell states given by 1,
the expected value for simultaneous measurement of A and B are Schumacher and
Westmoreland (2010):

$\left\langle\hat{W}^{A}_{\theta}\hat{W}^{B}_{\phi}\right\rangle=-\cos{(\theta-\phi)},$
(2)

where
$\hat{W}^{j}_{\theta}=\sin{\theta}\hat{\sigma}_{x}^{j}+\cos{\theta}\hat{\sigma}_{z}^{j}$,
with $j=A,B$ and $\hat{\sigma}_{x}^{j}$, $\hat{\sigma}_{z}^{j}$ represent the
spin operators of $j$ in the directions indicated by the subscript. In the
state specified by equation 1, the CHSH inequality is violated for certain
specific values of $\theta$ and $\phi$,

$\begin{split}S&=\left\langle\hat{W}^{A}_{0}\hat{W}^{B}_{\pi/4}\right\rangle-\left\langle\hat{W}^{A}_{0}\hat{W}^{B}_{3\pi/4}\right\rangle+\left\langle\hat{W}^{A}_{\pi/2}\hat{W}^{B}_{\pi/4}\right\rangle\\\
&+\left\langle\hat{W}^{A}_{\pi/2}\hat{W}^{B}_{3\pi/4}\right\rangle=-2\sqrt{2}<-2.\end{split}$
(3)

This example highlights a well-established understanding: a theory based on
Bell locality cannot account for the results of quantum mechanics in every
instance Myrvold et al. (2021). Nonetheless, in the context of open quantum
systems, we often examine the reduced system due to the impracticality of
achieving complete isolation. Consequently, questions arise regarding the
sufficient conditions for a reduced system to violate the CHSH inequality.

EntangledABTT$g_{k}$$g_{k}$ Figure 1: Schematic showing the entangled state of
two distant spins (measured by Alice and Bob) with negligible interaction,
coupled to a thermal bath at temperature $T$ via $g_{k}$.

To observe this, let us consider a simplified experiment illustrated in Figure
1: two spins that have interacted become entangled at a moment $t<0$, at $t=0$
they couple to a thermal bath consisting of bosons such that the interaction
is now solely between the spins and the bath. In this scenario, we have the
following initial state of the entire system, composed of the pair of spins
and the bath:

$\hat{\rho}(0)=\hat{\rho}_{S}(0)\otimes\hat{\rho}_{E},$ (4)

in this expression,
$\hat{\rho}_{S}(0)=\left|\psi\right\rangle\left\langle\psi\right|$ represents
the density matrix of the bipartite system composed of two spins whose
Hamiltonian is given by
$\hat{H}_{S}=\sum_{m\in\\{A,B\\}}\frac{\omega^{m}_{0}}{2}\hat{\sigma}^{m}_{z}$,
where $\omega^{m}_{0}$ is the energy difference between the eigenstates
$\left|0_{m}\right\rangle$ and $\left|1_{m}\right\rangle$.
$\hat{\sigma}^{m}_{z}$ is the spin operator in the z-direction for spin $m$.
On the other hand, $\hat{\rho}_{E}=\frac{\exp(-\beta\hat{H}_{E})}{Z_{E}}$
characterizes the thermal state of the bosonic bath, with a Hamiltonian
defined by $\hat{H}_{E}=\sum_{s}\omega_{s}\hat{b}^{\dagger}_{s}\hat{b}_{s}$.
The interaction is assumed to be of the oscillator type, that is,

$\hat{H}_{int}=\frac{1}{2}\sum_{m\in\\{A,B\\}}\sum_{s}\hat{\sigma}^{m}_{z}\left(g_{s}\hat{b}^{\dagger}_{s}+g^{*}_{s}\hat{b}_{s}\right),$
(5)

where $g_{s}$ represents the coupling constants. Physically, this model
represents a situation of decoherence without dissipation, as
$\left[\hat{H},\hat{\sigma}^{m}_{z}\right]=0$. Our focus now shifts to
calculating equation 2 for the bipartite system, that is,

$\begin{split}&\left\langle\hat{W}^{A}_{\theta}\hat{W}^{B}_{\phi}\right\rangle_{S}=\text{tr}_{S}\left(\hat{\rho}_{S}(t)\hat{W}^{A}_{\theta}\hat{W}^{B}_{\phi}\right)=\\\
&=\sin{\theta}\sin{\phi}\left(\rho_{S}^{1100}(t)+\rho_{S}^{0011}(t)+\rho_{S}^{0101}(t)+\rho_{S}^{1010}(t)\right)\\\
&+\sin{\theta}\cos{\phi}\left(\rho_{S}^{0100}(t)+\rho_{S}^{0010}(t)-\rho_{S}^{1101}(t)-\rho_{S}^{0111}(t)\right)\\\
&+\cos{\theta}\sin{\phi}\left(\rho_{S}^{1000}(t)+\rho_{S}^{0001}(t)-\rho_{S}^{1101}(t)-\rho_{S}^{0111}(t)\right)\\\
&+\cos{\theta}\cos{\phi}\left(\rho_{S}^{0000}(t)+\rho_{S}^{1111}(t)-\rho_{S}^{1001}(t)-\rho_{S}^{0110}(t)\right),\end{split}$
(6)

here,
$\hat{\rho}_{S}(t)=\text{tr}_{E}\left(\hat{U}(t)\hat{\rho}(0)\hat{U}^{\dagger}(t)\right)$
represents the reduced density matrix of the bipartite system and
$\rho_{S}^{ijkl}(t)=\left\langle
ij\right|\hat{\rho}_{S}(t)\left|kl\right\rangle$. The computation of the
matrix elements has been studied in the literature when the coupling with a
single spin is considered Breuer and Petruccione (2007). However, since there
is no interaction between the spins, it is feasible to generalize the result
for two spins, thus obtaining,

$\begin{split}\left\langle
ji\right|\hat{\rho}_{S}(t)\left|lk\right\rangle&=\rho_{S}^{jilk}(0)\times\\\
&\text{tr}_{E}[\exp{\left(\frac{1}{2}p_{ij}\sum_{s}\left(\alpha_{s}\hat{b}^{\dagger}_{s}-\alpha^{*}_{s}\hat{b}_{s}\right)\right)}\hat{\rho}_{E}(0)\\\
&\exp{\left(\frac{1}{2}p_{lk}\sum_{s}\left(\alpha^{*}_{s}\hat{b}_{s}-\alpha_{s}\hat{b}^{\dagger}_{s}\right)\right)}],\end{split}$
(7)

we have defined $\alpha_{k}=2g_{k}\frac{1-\exp{(i\omega_{k}t)}}{\omega_{k}}$
and also $p_{ij}=(-1)^{i}+(-1)^{j}$. Thus, for the state
$\left|\psi\right\rangle=\left|\psi_{AB}\right\rangle$ given by equation 1,
only the matrix elements $\rho_{S}^{jilk}(0)$ that satisfy $l\neq k$ and
$i\neq j$ are non-zero. Therefore, we observe no temperature dependence in the
bipartite system at any point for this initial state since equation 6 matches
equation 2; hence, the Bell inequalities will be violated at any temperature.

Now, among the possible initially entangled states, consider
$\left|\psi_{AB}\right\rangle=\frac{1}{\sqrt{2}}\left(\left|1_{A}1_{B}\right\rangle+\left|0_{A}0_{B}\right\rangle\right)$,
which violates the CHSH inequality when considering the same $\theta$ and
$\phi$ from equation 3. For the new bell-type state, we obtain for the reduced
system under the same physical conditions as in the previous case,

$\begin{split}\left\langle\hat{W}^{A}_{\theta}\hat{W}^{B}_{\phi}\right\rangle_{S}&=\cos{(\theta-\phi)}\times\\\
&\times\exp{\left(-8\sum_{s}\left|\alpha_{s}\right|^{2}\text{coth}\left(\frac{\omega_{s}\beta}{2}\right)\right)}.\end{split}$
(8)

Moreover, in this case, equation 3 exhibits a temperature dependence for the
bipartite system. Explicitly,

$\begin{split}S=2\sqrt{2}\times\exp{\left(-8\sum_{s}\left|\alpha_{s}\right|^{2}\text{coth}\left(\frac{\omega_{s}\beta}{2}\right)\right)}.\end{split}$
(9)

This expression demonstrates how the Bell inequality would be satisfied as a
function of temperature and the parameters associated with the thermal bath
and interaction. For instance, if we assume that the number of bosons tends to
infinity, equation 9 can be expressed in terms of the spectral density of the
thermal bath as,

$\begin{split}S&=2\sqrt{2}\times\\\
&\times\exp{\left(-32\int_{0}^{\infty}d\omega\hskip
2.84544ptJ(\omega)\left|\frac{\sin{\left(\frac{\omega
t}{2}\right)}}{\omega/2}\right|^{2}\text{coth}\left(\frac{\omega\beta}{2}\right)\right)},\end{split}$
(10)

where, $J(\omega)=\sum_{s}\left|g_{s}\right|^{2}\delta(\omega_{s}-\omega)$.
For this example, we see that given the spectral density of the bath, we can
find an upper limit for the temperature $T_{c}$ such that $S<2$. Let’s
consider the thermal limit $t\rightarrow\infty$, in this case,
$\sin^{2}{\left(\frac{\omega t}{2}\right)}/\omega^{2}\rightarrow\pi
t\delta(\omega)$ Bransden and Joachain (1982). Commonly spectral densities
satisfy $J(\omega=0)=0$ Schlosshauer (2007). Then, we have,

$\begin{split}S&=2\sqrt{2}\times\exp{\left(-256k_{b}T\frac{\mathrm{d}J}{\mathrm{d}\omega}|_{\omega=0}\right)}\\\
&\Rightarrow
T_{c}=\frac{\text{ln}\sqrt{2}}{256k_{b}\frac{\mathrm{d}J}{\mathrm{d}\omega}|_{\omega=0}}.\end{split}$
(11)

The upper equation shows the expected physical situation. In the high-
temperature limit, the CHSH inequality is anticipated to hold since
$S\rightarrow 0$. On the other hand, the equation below indicates the critical
temperature dependence on the spectral density.

##  III Discusion.

In the previous section, we prove that CHSH inequality could be independent on
the temperature once the system interacts with a bosonic bath for certain
initial entangled states of the bipartite system. We find out that this is
because the system’s initial states belong to the decoherence-free subspace
(DFS), which is not influenced by the bath Lidar et al. (1999). That is, the
density matrix associated with the bipartite system preserves unitary
evolution
$\hat{\rho}_{S}(t)=\hat{U}_{S}\hat{\rho}_{S}(0)\hat{U}_{S}^{\dagger}$ with
$\hat{U}_{S}=\text{exp}(-it\hat{H}_{S})$. In our previous example, states
belonging to DFS are given by those states which are eigenstates of
$\frac{1}{2}\sum_{m\in\\{A,B\\}}\sum_{s}\hat{\sigma}^{m}_{z}$. In short,
initial entangled states satisfying this condition as in the case of equation
1 violated CHSH inequality independent of temperature. However, other states,
such as in the case
$\left|\psi_{AB}\right\rangle=\frac{1}{\sqrt{2}}\left(\left|1_{A}1_{B}\right\rangle+\left|0_{A}0_{B}\right\rangle\right)$,
will exhibit a critical temperature beyond which the Bell inequality is
satisfied. Therefore, the environment constrains the validity of using a Bell
test as a measure of entanglement. That is, violating the Bell inequality is a
sufficient condition to ensure entanglement but not a necessary one Werner
(1989). In this scenario, employing other more effective entanglement tests is
essential.

##  IV Conclusion.

We show that starting from an initial state that violates the CHSH inequality,
we ascertain that states residing in the Decoherence-Free Subspace (DFS) allow
two qubits, when interacting with an oscillator environment, to consistently
violate the CHSH inequality irrespective of temperature. For states outside
the DFS, we determine a temperature threshold beyond which the CHSH inequality
is no longer violated. This threshold holds true across various spectral
densities of the environment.

## References

  * 202 [2022] Nature Computational Science 2, 687 (2022), URL https://doi.org/10.1038/s43588-022-00368-0.
  * Bell [1964] J. S. Bell, Physics Physique 1, 195 (1964), URL https://doi.org/10.1103/physicsphysiquefizika.1.195.
  * Chen et al. [2021] X. Chen, Z. Fu, Q. Gong, and J. Wang, Advanced Photonics 3 (2021), URL https://doi.org/10.1117/1.ap.3.6.064002.
  * Galve et al. [2010] F. Galve, L. A. Pachón, and D. Zueco, Physical Review Letters 105 (2010), URL https://doi.org/10.1103/physrevlett.105.180501.
  * Chakrabarty et al. [2011] I. Chakrabarty, S. Banerjee, and N. Siddharth, Quantum Info. Comput. 11, 541–562 (2011), ISSN 1533-7146.
  * Marconi et al. [2022] C. Marconi, A. Riera-Campeny, A. Sanpera, and A. Aloy, Physical Review A 105 (2022), URL https://doi.org/10.1103/physreva.105.l060201.
  * Fadel and Tura [2018] M. Fadel and J. Tura, Quantum 2, 107 (2018), URL https://doi.org/10.22331/q-2018-11-19-107.
  * Bohm [1951] D. Bohm, _Quantum Theory_ (Prentice Hall, Old Tappan, NJ, 1951).
  * Schumacher and Westmoreland [2010] B. Schumacher and M. Westmoreland, _Quantum Processes Systems, and Information_ (Cambridge University Press, Cambridge, England, 2010).
  * Myrvold et al. [2021] W. Myrvold, M. Genovese, and A. Shimony, in _The Stanford Encyclopedia of Philosophy_ , edited by E. N. Zalta (Metaphysics Research Lab, Stanford University, 2021), Fall 2021 ed.
  * Breuer and Petruccione [2007] H.-P. Breuer and F. Petruccione, _The Theory of Open Quantum Systems_ (Oxford University Press, 2007), ISBN 9780199213900, URL https://doi.org/10.1093/acprof:oso/9780199213900.001.0001.
  * Bransden and Joachain [1982] B. H. Bransden and C. J. Joachain, _Physics of atoms and molecules_ (Prentice-Hall, London, England, 1982).
  * Schlosshauer [2007] M. Schlosshauer, _Decoherence and the Quantum-To-Classical Transition_ (Springer Berlin Heidelberg, 2007).
  * Lidar et al. [1999] D. A. Lidar, D. Bacon, and K. B. Whaley, Physical Review Letters 82, 4556 (1999), URL https://doi.org/10.1103/physrevlett.82.4556.
  * Werner [1989] R. F. Werner, Physical Review A 40, 4277 (1989), URL https://doi.org/10.1103/physreva.40.4277.


main[] [][][] Self Avoiding Random Walks

# Exactly-Solvable Self-Trapping Lattice Walks. Part I: Trapping in Ladder
Graphs

Alexander R. Klotz
<EMAIL_ADDRESS>
Department of Physics and Astronomy
California State University, Long Beach
1250 Bellflower Blvd., Long Beach, CA, 90840 Everett Sullivan
<EMAIL_ADDRESS>
Department of Mathematics
Virginia Tech
Blacksburg, Virginia USA
Department of Mathematics
Clayton State University
Morrow, Georgia USA

###### Abstract

A growing self-avoiding walk (GSAW) is a stochastic process that starts from
the origin on a lattice and grows by occupying an unoccupied adjacent lattice
site at random. A sufficiently long GSAW will reach a state in which all
adjacent sites are already occupied by the walk and become trapped,
terminating the process. It is known empirically from simulations that on a
square lattice, this occurs after a mean of 71 steps. In Part I of a two-part
series of manuscripts, we consider simplified lattice geometries only two
sites high (“ladders”) and derive generating functions for the probability
distribution of GSAW trapping. We prove that a self-trapping walk on a square
ladder will become trapped after a mean of 17 steps, while on a triangular
ladder trapping will occur after a mean of 941/48$\approx$19.6 steps. We
discuss additional implications of our results for understanding trapping in
the “infinite” GSAW.

## 1\. Introduction and Background

The self-avoiding walk (SAW) is a random walk that cannot visit the same
location more than once. The statistics of SAWs are used to model the physics
of polymer chains with excluded volume interactions [11]. The universal
quantities of SAWs, such as the growth exponent, size-scaling exponent, and
finite-length corrections can be calculated by full enumerations of SAWs [8,
3] or by stochastic generation of large ensembles [2] on various lattices.
These universal SAW properties make predictions for the behavior of real
polymers that can be observed in experiment, for example the dependence of
radius of gyration on molecular weight [4]. Combinatorial techniques used to
enumerate SAWs include the lace expansion method [3], transfer matrix methods
[8], and the length-doubling method [14].

SAW statistics assume that each walk of a given length is equally likely to
occur. An alternative ensemble is that of the growing self-avoiding walk
(GSAW), a stochastic process in which a walk grows from the origin on a
lattice by taking a random step to an adjacent unoccupied site. The
probability of a given walk occurring is history-dependent and GSAWs have
different statistics from SAWs [10]. One feature of GSAWs is trapping: a walk
will eventually grow to a configuration at which there are no unoccupied
adjacent sites, and the process terminates.

It is known empirically that a growing self-avoiding walk on a square lattice
will become trapped after a mean of approximately 71 steps, with a positively
skewed distribution peaked at around 35 steps, and that walks are more likely
to become trapped after an odd number of steps than even [6]. It has been
argued based on heuristic reasoning that walks become trapped with probability
1 [5]. In addition, the trapping statistics of GSAWs have been explored on
other lattices such as the triangular, honeycomb, and simple cubic lattices
[13].

The mean trapping length is only known through stochastic simulations of
GSAWs, there is no exact or closed-form expression for the probability
distribution of trapping lengths. Deriving the mean trapping length requires
knowledge of the probability of every possible self-avoiding walk.
Enumerations are known up to, coincidentally, 71 steps, for which there are
4,190,893,020,903,935,054,619,120,005,916 distinct walks on the square lattice
[8]. It would not be feasible to calculate the probability of each walk in the
ensemble. It is, in principle, possible to calculate the probability of every
trapped configuration until the median and mode of the trapping probability
distribution are surpassed, but the extensive computation required for that
calculation would not provide sufficient insight to justify it.

The motivation behind this manuscript and its followup [9] is to use a
simplified system that allows exact solutions of the trapping behavior of
growing self-avoiding walks through the use of combinatorial methods. We
consider restricted lattices upon which growing self-avoiding walks may be
trapped. Reduced latices prevent “combinatorial explosion” and allow a
realistic number of cases to be considered, such that parameters such as the
mean trapping length may be exactly solved. In particular, we consider
lattices with square or triangular connectivity that only span two sites in
one dimension, while remaining infinite or semi-infinite in the other, which
we refer to as ladders. We derive the mean trapping length and other relevant
metrics for these restricted lattices.

Beyond the mean trapping length, there are a number of empirical features of
GSAW trapping statistics that we may exactly solve. It is known that on a
square lattice, walks are more likely to become trapped after an odd number of
steps, while the parity asymmetry is not observed in the triangular lattice,
which has a mean of about 77 steps. The trapping probability distribution has
a global maximum before decaying exponentially, with a different decay
constant for square and triangular lattices [13]. We recently explored
trapping in GSAWs that were biased to take steps adjacent to occupied sites,
modelling a poor-solvent interaction in polymer physics [7]. A non-monotonic
dependence of the trapping length on the bias strength was observed, with a
global minimum for weak bias before it diverges exponentially. In this work,
we seek to exactly solve these empirical phenomenon in a simplified system.

Confined walks adopt a highly extended configuration, and the statistics of
confined random walks may be used to understand the physics of confined
polymers, for example the mean extension of chains in a reptation tube [12] or
of DNA confined in nanochannel devices for genomic imaging [1]. Exactly-
solvable models have proved insightful in this area. For example, a mapping
between the physics of confined DNA in the extended de Gennes regime and the
exactly solvable one-dimensional Domb-Joyce model has allowed an exact
derivation of a molecule’s mean extension [15]. In addition to deriving the
trapping length and distribution of confined GSAWs, we also derive exact
solutions for their mean extension to complement existing work in this area.

In this paper, Part I, we explore lattices that are two sites high and use
pencil-and-paper combinatorial methods to derive a generating function for the
trapping probability distribution. We prove that trapping is inevitable and
derive the exact probability distribution and trapping length for the square
and triangular lattice, the discussion of which begins on Page 29. In a
forthcoming paper, Part II [9], we use finite state machines and related
methods to prove that the generating functions for the trapping probabilities
on square lattices of arbitrary height are rational and we explicitly compute
the trapping probability distribution for square lattices that are three and
four sites high.

## 2\. Derivations

###  2.1 Definitions and Notation

######  Definition 2.1.

Given two graphs $G$ and $H$ we define the graph $G\Box H$, called the box
product, to be the graph with vertex set $V=\\{(g,h)\mid g\in V(G)\text{ and
}h\in V(H)\\}$, and edge set

$\displaystyle E=\\{((g_{1},h_{1}),(g_{2},h_{2}))\mid$
$\displaystyle\left(h_{1}=h_{2}\text{ and }(g_{1},g_{2})\in E(G)\right)$
$\displaystyle\text{ or }\left(g_{1}=g_{2}\text{ and }(h_{1},h_{2})\in
E(H)\right)\\}$

######  Definition 2.2.

We define the path graph, $P_{n}$ to be the simple graph with vertex set
$V=\\{1,\cdots,n\\}$ and edge set $E=\\{(a,b)\mid a,b\in V\text{ and
}\lvert{a-b}\rvert=1\\}$.

Then the ladder graph, $L_{n}$ is $P_{2}\Box P_{n}$.

######  Example 2.3.

Here are some examples of ladder graphs

$L_{1}$$L_{2}$$L_{4}$

We will also consider the cases where the ladder graph is unbounded on one
side. Thus we make the follow definitions

######  Definition 2.4.

We define $P^{\ast}_{\infty}$ to be the simple graph with vertex set
$V=\\{a\mid a\in\mathbb{Z}\text{ and }a>0\\}$ with edge set $E=\\{(a,b)\mid
a,b\in V\text{ and }\lvert{a-b}\rvert=1\\}$.

We define $P_{\infty}$ to be the simple graph with vertex set $V=\mathbb{Z}$
with edge set $E=\\{(a,b)\mid a,b\in V\text{ and }\lvert{a-b}\rvert=1\\}$.

Then we define $L^{\ast}_{\infty}=P_{2}\Box P^{\ast}_{\infty}$ and
$L_{\infty}=P_{2}\Box P_{\infty}$

######  Example 2.5.

The defined graphs are as follows:

$\scriptstyle\cdots\,$$L^{\ast}_{\infty}$$\scriptstyle\cdots\,$$\scriptstyle\cdots\,$$L_{\infty}$

We will consider Growing Self Avoiding Random Walks (GSAW) on these graphs.

######  Definition 2.6.

A Growing Self Avoiding Random Walk (GSAW) on a graph $G$ is a (possibly
finite) sequence of vertices $W=\\{v_{i}\\}_{1}^{\infty}$ such that for all
$i$, the vertices $v_{i}$ and $v_{i+1}$ are adjacent, and $v_{i}\neq v_{j}$
for any $i\neq j$.

If $W$ is finite then additionally we say that the length of the path is the
number of vertices in the path, and the last vertex must have all neighbors
belonging to the path as well.

We may think of this as starting at some vertex and randomly choosing another
vertex to walk to that we have not been to before. If we arrive at a vertex
where every neighbor is already in the path, then we must stop.

Any step in a path of a lattice graph can be identified as a step in the
positive $x$ direction which we will denote with the symbol $E$, a step in the
negative $x$ direction which we will denote with the symbol $W$, a step in the
negative $y$ direction which we will denote with the symbol $S$, or step in
the positive $y$ direction which we will denote with the symbol $N$.

Thus we may identify a path in a lattice graph by its starting point and a
sequence of steps. On $L^{\ast}_{\infty}$ we will only consider GSAWs that
start at $(1,1)$. Observe that by symmetry that this is same as starting at
$(1,2)$.

$\scriptstyle\cdots\,$$NEESW$ Figure 1: An example of a GSAW on
$L^{\ast}_{\infty}$. The starting position is denoted by a square and the
ending position by a diamond.

######  Definition 2.7.

Let $P$ be a path on $L_{n},L^{\ast}_{\infty},$ or $L_{\infty}$. We define the
length of a path to be the number of steps taken. We define the width of a
path to be the (positive) distance between the largest and smallest
$x$-coordinates of points on the path.

###  2.2 Unbiased Square Ladders

####  2.2.1 Precursor Functions

######  Definition 2.8.

We define a hook path of order $n$ on $L^{\ast}_{\infty}$ to be the path

$H^{\ast}_{n}=\underbrace{E\cdots E}_{\text{$n$ steps}}N\underbrace{W\cdots
W}_{\text{$n$ steps}}.$

We observe that for all $n>0$, $H^{\ast}_{n}$ is a GSAW. Given a GSAW that
selects neighbors uniformly at random, the probability of a GSAW using a being
$H^{\ast}_{n}$ is

$\left(\frac{1}{2}\right)^{n}\cdot\frac{1}{2}\cdot\frac{1}{2}=\left(\frac{1}{2}\right)^{n+2}.$

The length of $H^{\ast}_{n}$ is $2n+1$ and its width is $n$

######  Lemma 2.9.

Let $h_{\ell,w}$ be the probability that a GSAW on $L^{\ast}_{\infty}$
terminates as a hook path of length $\ell$ and width $w$. Then the bivariate
ordinary generating function $H^{\ast}(x,y)$ of $h_{\ell,w}$ is

$H^{\ast}(x,y)=\frac{x^{3}y}{8-4x^{2}y}.$

###### Proof.

Since we are only considering hook paths that terminate, $H_{0}$ is not
considered. Thus for the remaining hook paths $H^{\ast}_{n}$, each has length
$2n+1$ and probability $(1/2)^{n+2}$. We observe that for any hook path,
$\ell=2w+1$. Thus we see that the length of every hook path must be odd and
have minimum length 3. Thus if $\ell$ is even, if $\ell$ is 1 $h_{\ell,w}=0$,
$h_{1,w}=0$, and otherwise $h_{\ell,w}=(1/2)^{(\ell+3)/2}$ otherwise. Thus

$\displaystyle H^{\ast}(x,y)$
$\displaystyle=\sum_{{\ell=0}}^{{\infty}}{{\sum_{{w=0}}^{{\infty}}{{h_{\ell,w}x^{\ell}y^{w}}}}}=\sum_{{w=0}}^{{\infty}}{{h_{2w+1,w}x^{2w+1}y^{w}}}=\sum_{{k=1}}^{{\infty}}{{h_{2k+1,k}x^{2k+1}y^{k}}}$
$\displaystyle=\sum_{{k=1}}^{{\infty}}{{\left(\frac{1}{2}\right)^{k+2}x^{2k+1}y^{k}}}=\sum_{{k=0}}^{{\infty}}{{\left(\frac{1}{2}\right)^{k+3}x^{2k+3}y^{k+1}}}$
$\displaystyle=\left(\frac{x}{2}\right)^{3}y\sum_{{k=0}}^{{\infty}}{{\left(\frac{x^{2}y}{2}\right)^{k}}}=\frac{\left(\frac{x}{2}\right)^{3}y}{1-\frac{x^{2}y}{2}}=\boxed{\frac{x^{3}y}{8-4x^{2}y}}.$

∎

######  Definition 2.10.

We define a twist path of order $n$ on $L^{\ast}_{\infty}$ be the path

$T^{\ast}_{n}=\underbrace{E\cdots E}_{\text{$n$ steps}}NE.$

The probability of the first $n$ steps of a GSAW being $T^{\ast}_{n}$ is

$\left(\frac{1}{2}\right)^{n+2}\quad\text{if $n\geq 1$,
and}\quad\frac{1}{2}\quad\text{if $n=0$.}$

The length of $T^{\ast}_{n}$ is $n+2$ and its width is $n+1$.

######  Lemma 2.11.

Let $t_{\ell,w}$ be the probability that the first $\ell$ steps of a GSAW is a
twist path of length $\ell$ and width $w$. Then the bivariate ordinary
generating function $T^{\ast}(x,y)$ of $t_{\ell,w}$ is

$T^{\ast}(x,y)=\frac{x^{2}y}{2}+\frac{x^{3}y^{2}}{8-4xy}.$

###### Proof.

We observe that the minimum length of a twist path is 2, and that for any
twist path that $\ell=1+w$. Thus

$\displaystyle T^{\ast}(x,y)$
$\displaystyle=\sum_{{\ell=0}}^{{\infty}}{{\sum_{{w=0}}^{{\infty}}{{t_{\ell,w}x^{\ell}y^{w}}}}}=\sum_{{\ell=2}}^{{\infty}}{{t_{\ell,\ell-1}x^{\ell}y^{\ell-1}}}=t_{2,1}x^{2}y+\sum_{{\ell=3}}^{{\infty}}{{t_{\ell,\ell-1}x^{\ell}y^{\ell-1}}}$
$\displaystyle=t_{2,1}x^{2}y+\sum_{{k=0}}^{{\infty}}{{t_{k+3,k+2}x^{k+3}y^{k+2}}}=\frac{x^{2}y}{2}+\sum_{{k=0}}^{{\infty}}{{\left(\frac{1}{2}\right)^{k+3}x^{k+3}y^{k+2}}}$
$\displaystyle=\frac{x^{2}y}{2}+\frac{x^{3}y^{2}}{8}\sum_{{k=0}}^{{\infty}}{{\left(\frac{xy}{2}\right)^{k}}}=\frac{x^{2}y}{2}+\frac{\left(\frac{x^{3}y^{2}}{8}\right)}{1-\frac{xy}{2}}=\boxed{\frac{x^{2}y}{2}+\frac{x^{3}y^{2}}{8-4xy}}.$

∎

$\scriptstyle\cdots\,$ Figure 2: If the first $n$ steps form $T^{\ast}_{n}$,
then the remainder of the path must be another GSAW since the path can’t move
back, and so by symmetry it is in the same starting position.

####  2.2.2 The One Sided Case

######  Theorem 2.12.

Let $p_{\ell,w}$ be the probability that a GSAW on $L^{\ast}_{\infty}$
terminates having taken $\ell$ steps and a width of $w$. Then the bivariate
ordinary generating function $L^{\ast}_{\infty}(x,y)$ of $p_{\ell,w}$ is

$L^{\ast}_{\infty}(x,y)=\frac{x^{3}y(xy-2)}{(x^{2}y-2)(x^{3}y^{2}-4x^{2}y-4xy+8)}.$

###### Proof.

We first consider an arbitrary GSAW on $L^{\ast}_{\infty}$. We observe that
with probability 1, the GSAW makes a $N$ step at some point, since the only
way to avoid such a step is an infinite series of $E$ steps which has
probability 0 of happening. After the GSAW makes the $N$ step, it must either
take an $E$ step or $W$ step. If it takes a $W$ step then it forms a hook path
and terminates. If it takes an $E$ step then it forms a twist path and must
continue. However, at the end of the twist path, the remaining spaces
reachable from the current position is equivalent to starting a new GSAW, as
seen in figure 2.

Thus every GSAW on $L^{\ast}_{\infty}$ is either a hook path or a twist path
followed by another GSAW on $L^{\ast}_{\infty}$.

Let $p_{\ell,w}$ be the probability that a GSAW on $L^{\ast}_{\infty}$
terminates with length $\ell$ and width $w$. Then

$p_{\ell,w}=\sum_{{i=0}}^{{\ell}}{{\sum_{{j=0}}^{{\infty}}{{t}}_{i,j}p_{\ell-i,w-j}}}+h_{\ell,w}.$

Thus

$L^{\ast}_{\infty}(x,y)=T^{\ast}(x,y)L^{\ast}_{\infty}(x,y)+H^{\ast}(x,y).$

Solving for $L^{\ast}_{\infty}(x,y)$ we get that

$L^{\ast}_{\infty}(x,y)=\frac{H^{\ast}(x,y)}{1-T^{\ast}(x,y)}=\frac{x^{3}y(xy-2)}{(x^{2}y-2)(x^{3}y^{2}-4x^{2}y-4xy+8)}.$

∎

######  Corollary 2.13.

The generating function for the lengths of paths of terminating GSAWs on
$L^{\ast}_{\infty}$ is

$L^{\ast}_{\infty}(x,1)=\frac{x^{3}(x-2)}{(x^{2}-2)(x^{3}-4x^{2}-4x+8)}.$

The generating function for the widths of paths of terminating GSAWs on
$L^{\ast}_{\infty}$ is

$L^{\ast}_{\infty}(1,y)=\frac{y(y-2)}{(y-2)(y^{2}-8y+8)}$

######  Corollary 2.14.

The probability that a GSAW on $L^{\ast}_{\infty}$ terminates is 1.

###### Proof.

Let $p$ be the probability that a GSAW on $L^{\ast}_{\infty}$ terminates and
$q$ be the probability that it doesn’t. If the GSAW terminates, then it has a
finite number of steps. Thus

$p=\sum_{{\ell=0}}^{{\infty}}{{\sum_{{w=0}}^{{\infty}}{{p_{\ell,w}}}}}=L^{\ast}_{\infty}(1,1)=1.$

Thus $q=0$ and a GSAW will terminate with probability 1. ∎

######  Corollary 2.15.

The expected number of steps taken before a GSAW on $L^{\ast}_{\infty}(x,y)$
terminates is 13 with variance 98 (standard deviation $\approx 3.6$). The
expected width when a GSAW on $L^{\ast}_{\infty}(x,y)$ terminates is 7 with
variance 40 (standard deviation $\approx 6.3$).

###### Proof.

Let $p_{\ell}$ be the probability that a GSAW on $L^{\ast}_{\infty}$
terminates with $\ell$ steps. Then

$p_{\ell}=\sum_{{w=0}}^{{\infty}}{{p_{\ell,w}}}.$

The expected value of the number of steps is

$\mathbb{E}(\ell)=\sum_{{\ell=0}}^{{\infty}}{{\ell p_{\ell}}}.$

Thus

$\mathbb{E}(\ell)=\left.\left(\frac{\partial}{\partial
x}L^{\ast}_{\infty}(x,1)\right)\right|_{x=1}=13$

and the variance of the number of steps is

$\displaystyle\mathbb{V}(\ell)$
$\displaystyle=\left.\left(\frac{\partial^{2}}{\partial
x^{2}}L^{\ast}_{\infty}(x,1)\right)\right|_{x=1}+\left.\left(\frac{\partial}{\partial
x}L^{\ast}_{\infty}(x,1)\right)\right|_{x=1}-\left(\left.\left(\frac{\partial}{\partial
x}L^{\ast}_{\infty}(x,1)\right)\right|_{x=1}\right)^{2}$ $\displaystyle=98.$

By similar analysis the expected value of the displacement is

$\mathbb{E}(w)=\left.\left(\frac{\partial}{\partial
y}L^{\ast}_{\infty}(1,y)\right)\right|_{y=1}=7$

and the variance of the displacement is

$\displaystyle\mathbb{V}(w)$
$\displaystyle=\left.\left(\frac{\partial^{2}}{\partial
y^{2}}L^{\ast}_{\infty}(1,y)\right)\right|_{y=1}+\left.\left(\frac{\partial}{\partial
y}L^{\ast}_{\infty}(1,y)\right)\right|_{y=1}-\left(\left.\left(\frac{\partial}{\partial
y}L^{\ast}_{\infty}(1,y)\right)\right|_{y=1}\right)^{2}$ $\displaystyle=40.$

∎

####  2.2.3 The Double Sided Case

######  Definition 2.16.

We define a hook path of order $n$ on $L_{\infty}$ to be the path

$H_{n}=\underbrace{E\cdots E}_{\text{$n$ steps}}N\underbrace{W\cdots
W}_{\text{$n+1$ steps}}.$

The probability of GSAW having $H_{n}$ as its first segment is

$\frac{1}{3\cdot 2^{n}}.$

The length of $H_{n}$ is $2n+2$ and its width is $n+1$.

######  Lemma 2.17.

Let $h_{\ell,w}$ be the probability that a GSAW on $L_{\infty}$ terminates as
a hook path of length $\ell$ and width $w$. Then the bivariate ordinary
generating function $H(x,y)$ of $h_{\ell,w}$ is

$H(x,y)=\frac{2x^{2}y}{6-3x^{2}y}.$

###### Proof.

We first observe by symmetry that every starting position on $L_{\infty}$ is
the same. Without loss of generality we assume we start at $(0,1)$. The first
step is either a $N,W$, or $E$ step. However by symmetry $W$ and $E$ produce
the same path, so without loss of generality we may either move $N$ or $E$.

Thus a path has $1/3$ probability of taking a $N$ step at which point the next
step must form $H_{n}$ by symmetry. Therefor the probability of a GSAW having
$H_{0}$ as its first segment is $1/3$.

Otherwise the path takes an $E$ step with probability $2/3$, at which point to
create $H_{n}$ on $L_{\infty}$, the path must move $n-1$ $E$ steps, each with
probability $1/2$. Then a $N$ step with probability $1/2$ and then a $W$ step
with probability $1/2$, at which point the remaining $W$ steps must be taken
since there are no other options. Thus the probability of a GSAW having
$H_{n}$ as its first segment is

$\frac{2}{3}\left(\frac{1}{2}\right)^{n-2}\cdot\frac{1}{2}\cdot\frac{1}{2}=\frac{1}{3\cdot
2^{n}}.$

We observe that for any hook path, $\ell=2w$. Thus we see that the length of
every hook path must be even and have minimum length 2. Thus if $\ell$ is odd,
$h_{\ell,w}=0$. Thus

$\displaystyle H(x,y)$
$\displaystyle=\sum_{{\ell=0}}^{{\infty}}{{\sum_{{w=0}}^{{\infty}}{{h_{\ell,w}x^{\ell}y^{w}}}}}=\sum_{{w=0}}^{{\infty}}{{h_{2w,w}x^{2w}y^{w}}}=\sum_{{k=1}}^{{\infty}}{{h_{2k,w}x^{2k}y^{k}}}$
$\displaystyle=\sum_{{k=1}}^{{\infty}}{{\frac{1}{3\cdot
2^{k-1}}x^{2k}y^{k}}}=\sum_{{k=0}}^{{\infty}}{{\frac{1}{3\cdot
2^{k}}x^{2k+2}y^{k+1}}}$
$\displaystyle=\frac{x^{2}y}{3}\sum_{{k=0}}^{{\infty}}{{\left(\frac{x^{2}y}{2}\right)^{k}}}=\frac{\frac{x^{2}y}{3}}{1-\frac{x^{2}y}{2}}=\boxed{\frac{2x^{2}y}{6-3x^{2}y}}.$

∎

######  Definition 2.18.

We define a twist path of order $n$ on $L_{\infty}$ to be the path

$T_{n}=\underbrace{E\cdots E}_{\text{$n$ steps}}ENE.$

The probability of GSAW having $T_{n}$ as its first segment is

$\frac{1}{3\cdot 2^{n+1}}.$

The length of $T_{n}$ is $3+n$ and its width is $2+n$.

######  Lemma 2.19.

Let $t_{\ell,w}$ be the probability that a GSAW begins with a twist path of
length $\ell$ and width $w$. Then the bivariate ordinary generating function
$T(x,y)$ of $t_{\ell,w}$ is

$T(x,y)=\frac{x^{3}y^{2}}{6-3xy}.$

###### Proof.

We first observe by symmetry that every starting position on $L_{\infty}$ is
the same. Without loss of generality we assume we start at $(0,1)$. By
symmetry the first step must be a $W$ or $E$ step. The probability of the
first step being one of these two is $2/3$. By symmetry we may assume without
loss of generality that the step was an $E$ step.

After the first step, in order to create $T_{n}$ on $L_{\infty}$, the path
must move $n$ $E$ steps each with probability $1/2$. Then a $N$ step with
probability $1/2$ and then an $E$ step with probability $1/2$. At which point
the remaining $W$ steps must be taken since there are no other options. Thus
the probability of a GSAW having $T_{n}$ as its first segment is
$(2/3)(1/2)^{n}(1/2)(1/2)=1/(3\cdot 2^{n+1})$.

We observe that for any hook path, $\ell=w+1$ and the minimum width is $2$.
Thus

$\displaystyle T(x,y)$
$\displaystyle=\sum_{{\ell=0}}^{{\infty}}{{\sum_{{w=0}}^{{\infty}}{{t_{\ell,w}x^{\ell}y^{w}}}}}=\sum_{{w=0}}^{{\infty}}{{t_{w+1,w}x^{w+1}y^{w}}}=\sum_{{w=0}}^{{\infty}}{{\frac{1}{3\cdot
2^{w-1}}x^{w+1}y^{w}}}$
$\displaystyle=\sum_{{w=2}}^{{\infty}}{{\frac{1}{3\cdot
2^{w-1}}x^{w+1}y^{w}}}=\sum_{{k=0}}^{{\infty}}{{\frac{1}{3\cdot
2^{k+1}}x^{k+3}y^{k+2}}}=\frac{x^{3}y^{2}}{6}\sum_{{k=0}}^{{\infty}}{{\left(\frac{xy}{2}\right)^{k}}}$
$\displaystyle=\frac{\frac{x^{3}y^{2}}{6}}{1-\frac{xy}{2}}=\boxed{\frac{x^{3}y^{2}}{6-3xy}}.$

∎

######  Theorem 2.20.

let $p_{\ell,w}$ be the probability that a GSAW on $L_{\infty}$ terminates
having taken $\ell$ steps and a displacement of $w$. Then the bivariate
ordinary generating function $L_{\infty}(x,y)$ of $p_{\ell,w}$ is

$L_{\infty}(x,y)=\frac{x^{5}y^{2}(4-x^{3}y)}{3(x^{2}y-2)^{2}(x^{3}y^{2}-4x^{2}y-4xy+8)}.$

###### Proof.

We first consider an arbitrary GSAW on $L_{\infty}$.

With probability 1, the GSAW will take a north step, and thus form either a
hook or twist path on $L_{\infty}$. However, after that, the path continues as
if it were on $L^{\ast}_{\infty}$ since it can no longer go back.

Thus every GSAW on $L_{\infty}$ is either a hook path or a twist path followed
by another GSAW on $L^{\ast}_{\infty}$.

Thus

$L_{\infty}(x,y)=(T(x,y)+H(x,y))L^{\ast}_{\infty}(x,y).$

Since the other generating functions have already been computed we get that

$L_{\infty}(x,y)=\frac{x^{5}y^{2}(4-x^{3}y^{2})}{3(x^{2}y-2)^{2}(x^{3}y^{2}-4x^{2}y-4xy+8)}.$

∎

######  Corollary 2.21.

The generating function for the lengths of paths of terminating GSAWs (the
trapping length) on $L_{\infty}$ is

$L_{\infty}(x,1)=\frac{x^{5}(4-x^{3})}{3(x^{2}-2)^{2}(x^{3}-4x^{2}-4x+8)}.$

The generating function for the widths of paths of terminating GSAWs on
$L_{\infty}$ is

$L_{\infty}(1,y)=\frac{y^{2}(4-y)}{3(y-2)^{2}(y^{2}-8y+8)}$

######  Corollary 2.22.

The probability that a GSAW on $L_{\infty}$ terminates is 1.

###### Proof.

Let $p$ be the probability that a GSAW on $L_{\infty}$ terminates and $q$ be
the probability that it doesn’t. If the GSAW terminates, then it has a finite
number of steps. Thus

$p=\sum_{{\ell=0}}^{{\infty}}{{\sum_{{d=0}}^{{\infty}}{{p_{\ell,d}}}}}=L_{\infty}(1,1)=1.$

Thus $q=0$ and a GSAW will terminate with probability 1. ∎

######  Corollary 2.23.

The expected number of steps taken before a GSAW on $L_{\infty}$ terminates is
17 with variance 104 (standard deviation $\approx 10.2$). The expected width
when a GSAW on $L_{\infty}$ terminates is $28/3\approx 9.6$ with variance
$740/9\approx 82.2$ (standard deviation $\approx 9.1$).

###  2.3 Unbiased Triangular Ladders

####  2.3.1 Definitions

######  Definition 2.24.

We define the graph $\Delta_{\infty}$ to be the graph with vertex set
$V=\\{(a,b)\mid a\in\mathbb{Z},\quad b\in\\{0,1\\},\text{ and }a+b\text{ is
even}\\}$ and edge set
$E=\\{((x_{1},y_{1}),(x_{2},y_{2}))\mid(\lvert{x_{1}-x_{2}}\rvert=1\text{ and
}\lvert{y_{1}-y_{2}}\rvert=1)\text{ or }(y_{1}=y_{2}\text{ and
}\lvert{x_{1}-x_{2}}\rvert=2)\\}$

######  Definition 2.25.

We define the graph $\Delta^{\ast}_{\infty}$ to be the induced sub-graph of
$\Delta_{\infty}$ whose vertex set is given by $V=\\{(a,b)\mid
a\in\mathbb{N},\quad b\in\\{0,1\\},\text{ and }a+b\text{ is even}\\}$

######  Example 2.26.

The defined graphs are as follows:

$\scriptstyle\cdots\,$$\Delta^{\ast}_{\infty}$$\scriptstyle\cdots\,$$\scriptstyle\cdots\,$$\Delta_{\infty}$

$\scriptstyle\cdots\,$wide cornernarrow corner$EN_{d}ES_{u}N_{u}ES_{d}$ Figure
3: The $N_{u}$ and $S_{u}$ steps will always travel on the diagonal that moves
east, while the $N_{d}$ and $S_{d}$ steps will always travel on the diagonal
that moves west.

Since GSAWs on these graphs are no longer on a rectangular grid, we have
different notation for the representation of steps.

Any step in a path of the graphs $\Delta^{\ast}_{\infty}$ and
$\Delta_{\infty}$ can be identified as a step in the positive $x$ direction
which we will denote with the symbol $E$, a step in the negative $x$ direction
which we will denote with the symbol $W$, a step in the negative $x$ and $y$
direction which we will denote with the symbol $S_{d}$, or step in the
positive $y$ direction and negative $x$ which we will denote with the symbol
$N_{d}$, a step in the positive $x$ and $y$ direction which we will denote
with the symbol $N_{u}$, or step in the negative $y$ direction and positive
$x$ which we will denote with the symbol $S_{u}$.

All of these steps can be seen in the path given by Figure 3.

We additionally define the vertex $(0,0)$ in $\Delta^{\ast}_{\infty}$ to be
the “narrow corner” and the vertex $(1,1)$ in $\Delta^{\ast}_{\infty}$ to be
the “wide corner”.

####  2.3.2 Precursor Functions

######  Definition 2.27.

We define an upward twist path of order $n$ on $\Delta^{\ast}_{\infty}$
starting at the wide corner to be the path

$T^{u}_{n}=\underbrace{E\cdots E}_{\text{$n$ steps}}S_{u}E.$

The probability of GSAW on $\Delta^{\ast}_{\infty}$ starting at the wide
corner having $T^{u}_{n}$ as its first segment is

$\frac{1}{3^{n+2}}.$

The length of $T^{u}_{n}$ is $n+2$.

######  Lemma 2.28.

Let $t^{u}_{\ell}$ be the probability that a GSAW on $\Delta^{\ast}_{\infty}$
starting at the wide corner has $T^{u}_{n}$ as its first segment where
$n+2=\ell$. Then the ordinary generating function $T^{u}(x)$ of $t^{u}_{\ell}$
is

$T^{u}(x)=\frac{x^{2}}{9-3x}.$

###### Proof.

In order to create $T^{u}_{n}$ on $\Delta^{\ast}_{\infty}$, the path must move
$n$ $E$ steps each with probability $1/3$, then a $S_{u}$ step with
probability $1/3$ and then an $E$ step with probability $1/3$. Thus the
probability of a GSAW on $\Delta^{\ast}_{\infty}$ starting at the wide corner
having $T^{u}_{n}$ as its first segment is $1/(3^{n+2})$.

Thus

$\displaystyle T^{u}(x)$
$\displaystyle=\sum_{{\ell=0}}^{{\infty}}{{t^{u}_{\ell}x^{\ell}}}=\sum_{{\ell=2}}^{{\infty}}{{t^{u}_{\ell}x^{\ell}}}=\sum_{{n=0}}^{{\infty}}{{t^{u}_{n+2}x^{n+2}}}$
$\displaystyle=\sum_{{n=0}}^{{\infty}}{{\frac{1}{3^{n+2}}x^{n+2}}}=\frac{x^{2}}{9}\sum_{{n=0}}^{{\infty}}{{\left(\frac{x}{3}\right)^{n}}}=\frac{\frac{x^{2}}{9}}{1-\frac{x}{3}}=\boxed{\frac{x^{2}}{9-3x}}.$

∎

######  Definition 2.29.

We define a crooked path of order $n$ on $\Delta^{\ast}_{\infty}$ starting at
the wide corner to be the path

$C_{n}=\underbrace{E\cdots E}_{\text{$n$ steps}}S_{u}N_{u}.$

######  Lemma 2.30.

Let $c_{\ell}$ be the probability that a GSAW on $\Delta^{\ast}_{\infty}$
starting at the wide corner has $C_{n}$ as its first segment where $n+2=\ell$.
Then the ordinary generating function $C(x)$ of $c_{\ell}$ is

$C(x)=\frac{x^{2}}{9-3x}.$

###### Proof.

The proof is the same as in the upward twist case. The only different is that
the last step is a $N_{u}$ as opposed to an $E$ step, the probability of the
step is the same, and the length doesn’t change. ∎

######  Definition 2.31.

We define an upwards hook path of order $n$ on $\Delta^{\ast}_{\infty}$
starting at the wide corner to be the path

$H^{u}_{n}=\underbrace{E\cdots E}_{\text{$n$ steps}}S_{u}\underbrace{W\cdots
W}_{\text{$n+1$ steps}}.$

The probability of a GSAW on $\Delta^{\ast}_{\infty}$ starting at the wide
corner having $H^{u}_{n}$ as its first segment is

$\frac{1}{3^{n+2}}.$

The length of $H^{u}_{n}$ is $2n+2$.

######  Lemma 2.32.

Let $h^{u}_{\ell}$ be the probability that a GSAW on $\Delta^{\ast}_{\infty}$
starting at the wide corner has $H^{u}_{n}$ as its first segment where
$2n+2=\ell$. Then the ordinary generating function $H^{u}(x)$ of
$h^{u}_{\ell}$ is

$H^{u}(x)=\frac{x^{2}}{9-3x^{2}}.$

###### Proof.

In order to create $H^{u}_{n}$ on $\Delta^{\ast}_{\infty}$, the path must move
$n$ $E$ steps each with probability $1/3$, then a $S_{u}$ step with
probability $1/3$ and then a $W$ step with probability $1/3$. The remaining
$W$ steps are forced to exist, since there are no other options. Thus the
probability of a GSAW on $\Delta^{\ast}_{\infty}$ starting at the wide corner
having $H^{u}_{n}$ as its first segment is $1/(3^{n+2})$.

Thus

$\displaystyle H^{u}(x)$
$\displaystyle=\sum_{{\ell=0}}^{{\infty}}{{h^{u}_{\ell}x^{\ell}}}=\sum_{{\ell=2}}^{{\infty}}{{h^{u}_{\ell}x^{\ell}}}=\sum_{{n=0}}^{{\infty}}{{h^{u}_{2n+2}x^{2n+2}}}$
$\displaystyle=\sum_{{n=0}}^{{\infty}}{{\frac{1}{3^{n+2}}x^{2n+2}}}=\frac{x^{2}}{9}\sum_{{n=0}}^{{\infty}}{{\left(\frac{x^{2}}{3}\right)^{n}}}=\frac{\frac{x^{2}}{9}}{1-\frac{x^{2}}{3}}=\boxed{\frac{x^{2}}{9-3x^{2}}}.$

∎

######  Definition 2.33.

We define a downward twist path of order $n$ on $\Delta^{\ast}_{\infty}$
starting at the wide corner to be the path

$T^{d}_{n}=\underbrace{E\cdots E}_{\text{$n+1$ steps}}S_{d}E.$

The probability of a GSAW on $\Delta^{\ast}_{\infty}$ starting at the wide
corner having $T^{d}_{n}$ as its first segment is

$\frac{1}{2\cdot 3^{n+2}}.$

The length of $T^{d}_{n}$ is $n+3$.

######  Lemma 2.34.

Let $t^{d}_{\ell}$ be the probability that a GSAW on $\Delta^{\ast}_{\infty}$
starting at the wide corner has $T^{d}_{n}$ as its first segment where
$n+3=\ell$. Then the ordinary generation function $T^{d}(x)$ of $t^{d}_{\ell}$
is

$T^{d}(x)=\frac{x^{3}}{18-6x}.$

###### Proof.

In order to create $T^{d}_{n}$ on $\Delta^{\ast}_{\infty}$, the path must move
$n+1$ $E$ steps each with probability $1/3$, then a $S_{d}$ step with
probability $1/3$ and then an $E$ step with probability $1/2$. Thus the
probability of a GSAW on $\Delta^{\ast}_{\infty}$ starting at the wide corner
having $T^{d}_{n}$ as its first segment is $1/(2\cdot 3^{n+2})$.

Thus

$\displaystyle T^{d}(x)$
$\displaystyle=\sum_{{\ell=0}}^{{\infty}}{{t^{d}_{\ell}x^{\ell}}}=\sum_{{\ell=3}}^{{\infty}}{{t^{d}_{\ell}x^{\ell}}}=\sum_{{n=0}}^{{\infty}}{{t^{d}_{n+3}x^{n+3}}}$
$\displaystyle=\sum_{{n=0}}^{{\infty}}{{\frac{1}{2\cdot
3^{n+2}}x^{n+3}}}=\frac{x^{3}}{18}\sum_{{n=0}}^{{\infty}}{{\left(\frac{x}{3}\right)^{n}}}=\frac{\frac{x^{3}}{18}}{1-\frac{x}{3}}=\boxed{\frac{x^{3}}{18-6x}}.$

∎

######  Definition 2.35.

We define a downward hook path of order $n$ on $\Delta^{\ast}_{\infty}$
starting at the wide corner to be the path

$H^{d}_{n}=\underbrace{E\cdots E}_{\text{$n+1$ steps}}S_{d}\underbrace{W\cdots
W}_{\text{$n+1$ steps}}.$

The probability of a GSAW on $\Delta^{\ast}_{\infty}$ starting at the wide
corner having $H^{d}_{n}$ as its first segment is

$\frac{1}{2\cdot 3^{n+2}}.$

The length of $H^{d}_{n}$ is $2n+3$.

######  Lemma 2.36.

Let $h^{d}_{\ell}$ be the probability that a GSAW on $\Delta^{\ast}_{\infty}$
starting at the wide corner has $H^{d}_{n}$ as its first segment where
$2n+3=\ell$. Then the ordinary generation function $H^{d}(x)$ of
$h^{d}_{\ell}$ is

$H^{d}(x)=\frac{x^{3}}{18-6x^{2}}.$

###### Proof.

In order to create $H^{d}_{n}$ on $\Delta^{\ast}_{\infty}$, the path must move
$n+1$ $E$ steps each with probability $1/3$, then a $S_{d}$ step with
probability $1/3$ and then an $E$ step with probability $1/2$. The remaining
$W$ steps are forced to exist, since there are no other options. Thus the
probability of a GSAW on $\Delta^{\ast}_{\infty}$ starting at the wide corner
having $H^{d}_{n}$ as its first segment is $1/(2\cdot 3^{n+2})$.

Thus

$\displaystyle H^{d}(x)$
$\displaystyle=\sum_{{\ell=0}}^{{\infty}}{{h^{d}_{\ell}x^{\ell}}}=\sum_{{\ell=3}}^{{\infty}}{{h^{d}_{\ell}x^{\ell}}}=\sum_{{n=0}}^{{\infty}}{{h^{d}_{2n+3}x^{2n+3}}}$
$\displaystyle=\sum_{{n=0}}^{{\infty}}{{\frac{1}{2\cdot
3^{n+2}}x^{2n+3}}}=\frac{x^{3}}{18}\sum_{{n=0}}^{{\infty}}{{\left(\frac{x^{2}}{3}\right)^{n}}}=\frac{\frac{x^{3}}{18}}{1-\frac{x^{2}}{3}}=\boxed{\frac{x^{3}}{18-6x^{2}}}.$

∎

####  2.3.3 Solving the Triangular Case

######  Definition 2.37.

Let $w_{\ell}$ be the probability that a GSAW on $\Delta^{\ast}_{\infty}$
starting at the wide corner terminates with length $\ell$. Let $n_{\ell}$ be
the probability that a GSAW on $\Delta^{\ast}_{\infty}$ starting at the narrow
corner terminates with length $\ell$.

Let $N(x)$ be the ordinary generation function of $n_{\ell}$ and $W(x)$ be the
ordinary generation function of $w_{\ell}$.

######  Lemma 2.38.

It is the case that

$N(x)=\frac{x}{2}N(x)+\frac{x}{2}W(x).$

###### Proof.

Consider a GSAW on $\Delta^{\ast}_{\infty}$ that starts at the narrow corner.
Either it move $E$ with probability $1/2$ or it moves $N_{u}$ with probability
$1/2$.

If it moves $E$, then the rest of the path is a GSAW on
$\Delta^{\ast}_{\infty}$ starting at the wide corner by symmetry. If it moves
$N_{u}$, then the rest of the path is a GSAW on $\Delta^{\ast}_{\infty}$
starting at the wide corner by symmetry. Thus

$N(x)=\frac{x}{2}N(x)+\frac{x}{2}W(x).$

∎

######  Lemma 2.39.

It is the case that

$W(x)=H^{d}(x)+H^{u}(x)+T^{u}(x)W(x)+T^{d}(x)N(x)+\frac{x^{2}}{3}N(x).$

###### Proof.

Consider a GSAW on $\Delta^{\ast}_{\infty}$ that starts at the wide corner.
The first step must either be a $N_{d}$ step, a $N_{u}$ step for an $E$ step.
With $1/3$ probability, the path takes a $N_{d}$ step, which must immediately
be followed by an $E$ step since it is the only option. In this case two steps
have been taken and the rest of the path is a GSAW on $\Delta^{\ast}_{\infty}$
starting at the narrow corner.

If the first step is a $N_{u}$ step or $E$ step, then the GSAW must start with
either a $H^{u}_{n},H^{d}_{n},T^{u}_{n}$,$T^{d}_{n}$ or $C_{n}$ path. If it is
a $H^{d_{n}}$ or $H^{u}_{n}$ path, the GSAW terminates. If it is a $T^{u}_{n}$
path then the rest of the path is a GSAW on $\Delta^{\ast}_{\infty}$ starting
at the wide corner. If it is a $T^{d}_{n}$ path then the rest of the path is a
GSAW on $\Delta^{\ast}_{\infty}$ starting at the narrow corner. If it is a
$C_{n}$ path then the rest of the path is a GSAW on $\Delta^{\ast}_{\infty}$
starting at the narrow corner.

Thus

$W(x)=H^{d}(x)+H^{u}(x)+T^{u}(x)W(x)+T^{d}(x)N(x)+C(x)N(x)+\frac{x^{2}}{3}N(x).$

∎

######  Theorem 2.40.

$N(x)=\frac{x^{3}(x+2)(x-3)}{(x^{2}-3)(x^{4}-6x^{3}+2x^{2}-30x+36)}$

and

$W(x)=\frac{x^{2}(x+2)(x-3)(x-2)}{(3-x^{2})(x^{4}-6x^{3}+2x^{2}-30x+36)}$

###### Proof.

From lemma 2.38 we can solve for $N(x)$ to get

$N(x)=\frac{xW(x)}{2-x}$

Thus the equation from lemma 2.39 can be written as

$W(x)=H^{d}(x)+H^{u}(x)+T^{u}(x)W(x)+\frac{xW(x)T^{d}(x)}{2-x}+\frac{xC(x)W(x)}{2-x}+\frac{x^{3}W(x)}{3(2-x)}.$

Solving for $W(x)$ we get that

$W(x)=\frac{H^{d}(x)+H^{u}(x)}{1-T^{u}(x)-\frac{xT^{d}(x)}{2-x}-\frac{xC(x)}{2-x}-\frac{x^{3}}{3(2-x)}}.$

Substituting in the formulas for the known generation functions we get that

$W(x)=\frac{x^{2}(x+2)(x-3)(x-2)}{(3-x^{2})(x^{4}-6x^{3}+2x^{2}-30x+36)}$

and so

$N(x)=\frac{x^{3}(x+2)(x-3)}{(x^{2}-3)(x^{4}-6x^{3}+2x^{2}-30x+36)}$

∎

######  Corollary 2.41.

The probability that a GSAW on $\Delta^{\ast}_{\infty}$ starting at either the
wide or narrow corner terminates is 1.

######  Corollary 2.42.

The expected number of steps taken before a GSAW on $\Delta^{\ast}_{\infty}$
starting at the wide corner terminates is $91/6$ with variance $793/4$. The
expected number of steps taken before a GSAW on $\Delta^{\ast}_{\infty}$
starting at the narrow corner terminates is $103/6$ with variance $801/4$.

####  2.3.4 The double sided case

######  Definition 2.43.

Let $\delta_{\ell}$ be the probability that a GSAW on $\Delta_{\infty}$
terminates with length $\ell$.

Let $\Delta(x)$ be the ordinary generation function of $\delta_{\ell}$.

We observe that by symmetry, every starting point on $\Delta_{\infty}$ is the
same.

######  Theorem 2.44.

$\Delta(x)=\frac{x^{4}(2+x)(x^{4}+x^{3}-6x-12)}{4(x^{2}-3)^{2}(x^{4}-6x^{3}+2x^{2}-30x+36)}$

###### Proof.

Without loss of generality assume we start at $(0,0)$ on $\Delta_{\infty}$.
Then the first step must be one of $W,E,N_{d}$, and $N_{u}$. By symmetry we
may assume that it is either a $N_{u}$ or $E$ step.

If the first step of the path is a $N_{u}$, then the next step will prevent
the path from looping back and cause the rest of the path is be a GSAW on
$\Delta_{\infty}$ If the second step is an $E$ step then the rest of the path
is a GSAW on $\Delta_{\infty}$ starting at the wide corner. This has a $1/3$
probability of happening given that the first step was $N_{u}$. Otherwise the
second step is either a $W$ or $S_{u}$ step and the rest of the path is a GSAW
on $\Delta_{\infty}$ starting at the narrow corner.

If the first step of the path is an $E$ step, then one of the following must
happen.

  1. 1.

The Path Hooks Back:

The path makes a $H^{u}_{n}$ or $H^{d}_{n}$ path. Since these paths only
visits the vertex that can access the other side at the end, the generation
functions are the same. A extra $W$ step is taken, at which point the rest of
the path is a GSAW on $\Delta_{\infty}$ starting at the narrow corner.

  2. 2.

The Path Twists:

The path makes a $T^{u}_{n}$ or $T^{d}_{n}$ path. Since these paths never
visits the vertex that can access the other side at the end, the generation
functions are the same. The rest of the path is a GSAW on $\Delta_{\infty}$
starting at the corresponding corner.

  3. 3.

The Path Becomes Crooked:

The path makes a $C_{n}$ path at which point the rest of the path is a GSAW on
$\Delta_{\infty}$ starting at the narrow corner.

  4. 4.

The Path Takes a $N_{d}$ step:

If the path takes a $N_{d}$ step, then it can either take a $W$ or $E$ step.
However, in both cases the rest of the path is a GSAW on $\Delta_{\infty}$
starting at the narrow corner.

Thus we have that

$\displaystyle S(x)=$
$\displaystyle\frac{x}{2}\left(\frac{2x}{3}N(x)+\frac{x}{3}W(x)\right)$
$\displaystyle+\frac{x}{2}\left[\left(H^{d}(x)+H^{u}(x)\right)xN(x)+T^{u}(x)W(x)+T^{d}(x)N(x)+C(x)N(x)+\frac{x^{2}}{3}N(x)\right]$

Since the other functions are known, substituting them in gives

$S(x)=\frac{x^{4}(2+x)(x^{4}+x^{3}-6x-12)}{4(x^{2}-3)^{2}(x^{4}-6x^{3}+2x^{2}-30x+36)}.$

∎

######  Corollary 2.45.

The probability that a GSAW on $\Delta_{\infty}$ terminates is 1.

######  Corollary 2.46.

The expected number of steps taken before a GSAW on $\Delta_{\infty}$ starting
at the wide corner terminates is $941/48\approx 19.6$ with variance
$51919/256\approx 202.8$ (standard deviation $\approx 14.2$).

###  2.4 Biased Square Ladders

####  2.4.1 Definitions

######  Definition 2.47.

Let $G=(V,E)$ be a graph. Then a nearest-neighbor self-attraction GSAW is a
GSAW where each step is as follows. Let $P=(v_{1},v_{2},\cdots,v_{n})$ be a
path on the graph G. Let $M=N(v_{n})\setminus P$ be the set of all neighbors
of $v_{n}$ that are not in the path.

For any vertex $w$ in $G$ not already on the path, its energy is
$E(w)=C^{\lvert{N(w)\cap(P\setminus v_{n})}\rvert}$, where $C$ is a positive
constant. Thus the energy of a vertex is a constant raised to the power of the
number of neighbors already in the path.

The probability of $P$ moving to the neighboring vertex $w^{\ast}$ is

$\frac{E(w^{\ast})}{\sum\limits_{w\in M}E(w)}$

$v_{1}$$v_{2}$$w_{1}$$w_{2}$$w_{3}$ Figure 4: Since $w_{1},w_{2},$ and $w_{3}$
have no neighbors that belong to $P$ that are not $v_{2}$ their energy is
$C^{0}=1$, and so the probability of visiting any one of them is $1/3$.
$v_{1}$$v_{2}$$v_{3}$$w_{1}$$w_{2}$$w_{3}$ Figure 5: Since $w_{1}$ and $w_{2}$
have no neighbors that belong to $P$ that are not $v_{3}$ their energy is
$C^{0}=1$. The vertex $w_{3}$ has one neighbor that belongs to $P$ that is not
$v_{3}$ and so its energy is $C^{1}=C$. Thus the probabilities of $w_{1}$ or
$w_{2}$ being the next vertex is $\frac{1}{2+C}$ and the probability of
$w_{3}$ being the next vertex are each $\frac{C}{2+C}$

####  2.4.2 Precursor Functions

######  Lemma 2.48.

Let $h^{\ast}_{\ell,w}$ be the probability that a GSAW with nearest-neighbor
weighting on $L^{\ast}_{\infty}$ terminates as a hook path of length $\ell$
and width $w$. Then the bivariate ordinary generation function $H^{\ast}(x,y)$
of $h^{\ast}_{\ell,w}$ is

$H^{\ast}(x,y)=\frac{C}{1+C}\cdot\frac{x^{3}y}{4-2x^{2}y}$

###### Proof.

Since we are only considering hook paths that terminate, $H_{0}$ is not
considered.

The first $n+1$ steps all have probability $1/2$ of happening since their
neighbors are adjacent to the path. However after moving $N$, the $E$ step has
no neighbor in the path and the $W$ step as one neighbor in the path. Thus the
probability of taking the first $W$ step is $C/(1+C)$.

Thus for the remaining hook paths $H^{\ast}_{n}$, each as length $2n+1$ and
probability $(1/2)^{n+1}\frac{C}{1+C}$.

Thus

$\displaystyle H^{\ast}(x,y)$
$\displaystyle=\sum_{{\ell=0}}^{{\infty}}{{\sum_{{w=0}}^{{\infty}}{{h^{\ast}_{\ell,w}x^{\ell}y^{w}}}}}=\sum_{{w=0}}^{{\infty}}{{h^{\ast}_{2w+1,w}x^{2w+1}y^{w}}}=\sum_{{k=1}}^{{\infty}}{{h^{\ast}_{2k+1,k}x^{2k+1}y^{k}}}$
$\displaystyle=\sum_{{k=1}}^{{\infty}}{{\left(\frac{1}{2}\right)^{k+1}\frac{C}{1+C}x^{2k+1}y^{k}}}=\sum_{{k=0}}^{{\infty}}{{\left(\frac{1}{2}\right)^{k+2}\left(\frac{C}{1+C}\right)x^{2k+3}y^{k+1}}}$
$\displaystyle=\frac{x^{3}y}{4}\left(\frac{C}{1+C}\right)\sum_{{k=0}}^{{\infty}}{{\left(\frac{x^{2}y}{2}\right)^{k}}}=\frac{C}{1+C}\cdot\frac{\frac{x^{3}y}{4}}{1-\frac{x^{2}y}{2}}=\boxed{\frac{C}{1+C}\cdot\frac{x^{3}y}{4-2x^{2}y}}.$

∎

######  Lemma 2.49.

Let $t^{\ast}_{\ell,w}$ be the probability that the first $\ell$ steps of a
GSAW with nearest-neighbor weighing on $L^{\ast}_{\infty}$ is a twist path of
length $\ell$ and width $w$. Then the bivariate ordinary generating function
$T^{\ast}(x,y)$ of $t^{\ast}_{\ell,w}$ is

$T^{\ast}(x,y)=\frac{x^{2}y}{2}+\frac{1}{1+C}\frac{x^{3}y^{2}}{4-2xy}.$

###### Proof.

We observe that the minimum length of a twist path is 2, and that for any
twist path $\ell=1+w$. If the twist path is of length two, then it must first
move $N$ with probability $1/2$ and then it has no options but to move $E$.

Otherwise it first makes an $E$ step with probability $1/2$ and continues to
make $E$ steps with the same probability, until it takes a $N$ step with
probability $1/2$. Since there now exist points to the left, the probability
of the last $E$ step is $1/(1+C)$. Thus

$\displaystyle T^{\ast}(x,y)$
$\displaystyle=\sum_{{\ell=0}}^{{\infty}}{{\sum_{{w=0}}^{{\infty}}{{t^{\ast}_{\ell,w}x^{\ell}y^{w}}}}}=\sum_{{\ell=2}}^{{\infty}}{{t^{\ast}_{\ell,\ell-1}x^{\ell}y^{\ell-1}}}=t^{\ast}_{2,1}x^{2}y+\sum_{{\ell=3}}^{{\infty}}{{t_{\ell,\ell-1}x^{\ell}y^{\ell-1}}}$
$\displaystyle=t^{\ast}_{2,1}x^{2}y+\sum_{{k=0}}^{{\infty}}{{t_{k+3,k+2}x^{k+3}y^{k+2}}}=\frac{x^{2}y}{2}+\sum_{{k=0}}^{{\infty}}{{\frac{1}{1+C}\left(\frac{1}{2}\right)^{k+2}x^{k+3}y^{k+2}}}$
$\displaystyle=\frac{x^{2}y}{2}+\frac{x^{3}y^{2}}{(1+C)4}\sum_{{k=0}}^{{\infty}}{{\left(\frac{xy}{2}\right)^{k}}}=\frac{x^{2}y}{2}+\frac{\left(\frac{x^{3}y^{2}}{(1+C)4}\right)}{1-\frac{xy}{2}}=\boxed{\frac{x^{2}y}{2}+\frac{x^{3}y^{2}}{(1+C)(4-2xy)}}.$

∎

$\scriptstyle\cdots\,$ Figure 6: In this case, the path starts in the same
place, but there exists two point to the left which are considered to be “part
of the path” for the purpose of nearest neighbor calculations. A GSAW on such
a set-up will be called a GSAW on $\underline{L}^{\ast}_{\infty}$

######  Lemma 2.50.

Let $\underline{h}^{\ast}_{\ell,w}$ be the probability that a GSAW with
nearest-neighbor weighing on $\underline{L}^{\ast}_{\infty}$ terminates as a
hook path of length $\ell$ and width $w$. Then the bivariate ordinary
generating function $\underline{H}^{\ast}(x,y)$ of
$\underline{h}^{\ast}_{\ell,w}$ is

$\underline{H}^{\ast}(x,y)=\frac{C^{2}x^{3}y}{2(1+C)(1+C^{2})}+\frac{Cx^{5}y^{2}}{2(1+C)^{2}(2-x^{2}y)}$

###### Proof.

Since we are only considering hook paths that terminate,
$\underline{H}^{\ast}_{0}$ is not considered.

The first step has probability $1/(1+C)$ probability of happening. The next
$\ell$ steps all have probability $1/2$ of happening since their neighbors are
not adjacent to the path. However after moving $N$, the $E$ step has no
neighbor in the path and the $W$ step has either one or two neighbors in the
path. If $\ell=3$, then this step has two neighbors and has probability
$C^{2}/(1+C^{2})$ of happening, otherwise it has probability $C/(1+C)$ of
happening. The rest of the steps are then determined.

Thus

$\displaystyle\underline{H}^{\ast}(x,y)$
$\displaystyle=\sum_{{\ell=0}}^{{\infty}}{{\sum_{{w=0}}^{{\infty}}{{\underline{h}^{\ast}_{\ell,w}x^{\ell}y^{w}}}}}=\sum_{{w=0}}^{{\infty}}{{\underline{h}^{\ast}_{2w+1,w}x^{2w+1}y^{w}}}=\underline{h}^{\ast}_{3,1}x^{3}y+\sum_{{w=2}}^{{\infty}}{{\underline{h}^{\ast}_{2w+1,w}x^{2w+1}y^{w}}}$
$\displaystyle=\frac{C^{2}x^{3}y}{2(1+C)(1+C^{2})}+\sum_{{k=0}}^{{\infty}}{{\underline{h}^{\ast}_{2k+1,k}x^{2k+5}y^{k+2}}}$
$\displaystyle=\frac{C^{2}x^{3}y}{2(1+C)(1+C^{2})}+\sum_{{k=0}}^{{\infty}}{{\frac{C}{2^{k+2}(1+C)^{2}}x^{2k+5}y^{k+2}}}$
$\displaystyle=\frac{C^{2}x^{3}y}{2(1+C)(1+C^{2})}+\frac{Cx^{5}y^{2}}{4(1+C)^{2}}\sum_{{k=0}}^{{\infty}}{{\left(\frac{x^{2}y}{2}\right)^{k}}}$
$\displaystyle=\frac{C^{2}x^{3}y}{2(1+C)(1+C^{2})}+\frac{Cx^{5}y^{2}}{4(1+C)^{2}}\frac{1}{1-\frac{x^{2}y}{2}}$
$\displaystyle=\boxed{\frac{C^{2}x^{3}y}{2(1+C)(1+C^{2})}+\frac{Cx^{5}y^{2}}{2(1+C)^{2}(2-x^{2}y)}}$

∎

######  Lemma 2.51.

Let $\underline{t}_{\ell,w}$ be the probability that the first $\ell$ steps of
a GSAW with nearest-neighbor weighing on $\underline{L}^{\ast}_{\infty}$ is a
twist path of length $\ell$ and width $w$. Then the bivariate ordinary
generating function $\underline{T}^{\ast}(x,y)$ of $\underline{t}_{\ell,w}$ is

$\underline{T}^{\ast}(x,y)=\frac{Cx^{2}y}{C+1}+\frac{x^{3}y^{2}}{2(1+C)(1+C^{2})}+\frac{x^{4}y^{3}}{2(1+C)^{2}(2-xy)}.$

###### Proof.

We observe that the minimum length of a twist path is 2, and that for any
twist path $\ell=1+w$.

If the twist path is of length two, then it must first move $N$ with
probability $C/(C+1)$ and then it has no other options but to move $E$.

Otherwise it first makes an $E$ step with probability $1/(C+1)$. From here
there are two options, it moves $N$ with probability 1/2, but then must move
$E$ with probability $1/(1+C^{2})$ since the vertex west of it is adjacent to
the path and the floor. This is the only twist path of length two.

If this doesn’t happen, then it continues to move east at which point when it
does move north there is only one vertex adjacent in the backwards direction.
Thus the final $E$ step will happen with probability $1/(C+1)$ and continues
to make $E$ steps with the same probability, until it takes a $N$ step with
probability $1/2$. Since there now exist points to the left, the probability
of the last $E$ step is $1/(1+C)$. Thus

$\displaystyle\underline{T}^{\ast}(x,y)$
$\displaystyle=\sum_{{\ell=0}}^{{\infty}}{{\sum_{{w=0}}^{{\infty}}{{\underline{t}^{\ast}_{\ell,w}x^{\ell}y^{w}}}}}=\sum_{{\ell=2}}^{{\infty}}{{\underline{t}^{\ast}_{\ell,\ell-1}x^{\ell}y^{\ell-1}}}=\underline{t}^{\ast}_{2,1}x^{2}y+\underline{t}^{\ast}_{3,2}x^{3}y^{2}+\sum_{{\ell=3}}^{{\infty}}{{\underline{t}_{\ell,\ell-1}x^{\ell}y^{\ell-1}}}$
$\displaystyle=\frac{Cx^{2}y}{C+1}+\frac{x^{3}y^{2}}{2(C+1)(C^{2}+1)}+\sum_{{k=0}}^{{\infty}}{{\frac{x^{k+3}y^{k+2}}{2^{k+1}(C+1)^{2}}}}$
$\displaystyle=\frac{Cx^{2}y}{C+1}+\frac{x^{3}y^{2}}{2(C+1)(C^{2}+1)}+\frac{x^{3}y^{2}}{2}\sum_{{k=0}}^{{\infty}}{{\left(\frac{xy}{2}\right)^{k}}}$
$\displaystyle=\frac{Cx^{2}y}{C+1}+\frac{x^{3}y^{2}}{2(C+1)(C^{2}+1)}+\frac{x^{3}y^{2}}{2}\frac{1}{1-\frac{xy}{2}}$
$\displaystyle=\boxed{\frac{x^{3}y^{2}}{2(1+C)(1+C^{2})}+\frac{x^{4}y^{3}}{2(1+C)^{2}(2-xy)}}.$

∎

####  2.4.3 The One Sided Case

######  Theorem 2.52.

Let $\underline{p}^{\ast}_{\ell,w}$ be the probability that a GSAW with
nearest-neighbor weighing on $\underline{L}^{\ast}_{\infty}$ terminates having
taking $\ell$ steps and a width of $w$. Then the bivariate ordinary generating
function $\underline{L}^{\ast}_{\infty}(x,y)$ of
$\underline{p}^{\ast}_{\ell,w}$ is

$\underline{L}^{\ast}_{\infty}(x,y)=\frac{\underline{H}^{\ast}(x,y)}{1-\underline{T}^{\ast}(x,y)}.$

###### Proof.

We first consider an arbitrary GSAW with nearest-neighbor weighing on
$\underline{L}^{\ast}_{\infty}$. We observe that with probability 1 the GSAW
makes a $N$ step at some point since the only way to avoid such a step is an
infinite series of $E$ steps which has probability 0 of happening. After the
GSAW makes the $N$ step it must either take an $E$ step or $W$ step. If it
takes a $W$ step then it forms a hook path and terminates. It is takes an $E$
step then it forms a twist path and must continue. However, at the end of the
twist path, the remaining spaces reachable from the current position is
equivalent to starting a new GSAW with nearest-neighbor weighing on
$\underline{L}^{\ast}_{\infty}$.

Thus every GSAW with nearest-neighbor weighing on
$\underline{L}^{\ast}_{\infty}$ is either a hook path or a twist path followed
by another GSAW with nearest-neighbor weighing on
$\underline{L}^{\ast}_{\infty}$.

Thus

$\underline{L}^{\ast}_{\infty}(x,y)=\underline{T}^{\ast}(x,y)\underline{L}^{\ast}_{\infty}(x,y)+\underline{H}^{\ast}(x,y).$

Solving for $\underline{L}^{\ast}_{\infty}(x,y)$ we get

$\underline{L}^{\ast}_{\infty}(x,y)=\frac{\underline{H}^{\ast}(x,y)}{1-\underline{T}^{\ast}(x,y)}.$

∎

######  Theorem 2.53.

Let $p^{\ast}_{\ell,w}$ be the probability that a GSAW with nearest-neighbor
weighing on $L^{\ast}_{\infty}$ terminates having taking $\ell$ steps and a
width of $w$. Then the bivariate ordinary generating function
$L^{\ast}_{\infty}(x,y)$ of $p^{\ast}_{\ell,w}$ is

$L^{\ast}_{\infty}(x,y)=T^{\ast}(x,y)\underline{L}^{\ast}_{\infty}(x,y)+H^{\ast}(x,y).$

###### Proof.

We consider an arbitrary GSAW with nearest-neighbor weighing on
$L^{\ast}_{\infty}$. Use similar logic as before we have that such a GSAW
either makes a hook path and terminates or makes a twist path and then the
rest is a GSAW with nearest-neighbor weighing on
$\underline{L}^{\ast}_{\infty}$.

Thus

$L^{\ast}_{\infty}(x,y)=T^{\ast}(x,y)\underline{L}^{\ast}_{\infty}(x,y)+H^{\ast}(x,y).$

∎

######  Corollary 2.54.

The probability that a GSAW with nearest-neighbor weighing on
$L^{\ast}_{\infty}$ or $\underline{L}^{\ast}_{\infty}$ terminates is 1.

######  Corollary 2.55.

The expected number of steps taken before a GSAW with nearest-neighbor
weighing on $L^{\ast}_{\infty}$ terminates is

$\frac{16+42C+51C^{2}+59C^{3}+36C^{4}+4C^{5}}{2C+4C^{2}+6C^{3}+4C^{4}}$

with variance

$\scalebox{1.2}{$\frac{256+1104C+2488C^{2}+3998C^{3}+4981C^{4}+4864C^{5}+3769C^{6}+2292C^{7}+1000C^{8}+288C^{9}+48C^{10}}{4C^{2}(1+C)^{2}(1+C+2C^{2})^{2}}$}.$

The expected width is

$\frac{C^{4}+7C^{3}+8C^{2}+6C+6}{2C^{3}+C^{2}+C}$

with variance

$\frac{(C+1)\left(3C^{7}+9C^{6}+33C^{5}+59C^{4}+62C^{3}+84C^{2}+34C+36\right)}{C^{2}\left(2C^{2}+C+1\right)^{2}}.$

######  Corollary 2.56.

The expected number of steps taken before a GSAW with nearest-neighbor
weighing on $\underline{L}^{\ast}_{\infty}$ terminates is

$\frac{4C^{4}+14C^{3}+12C^{2}+14C+8}{2C^{3}+C^{2}+C}$

with variance

$\frac{2\left(8C^{8}+24C^{7}+72C^{6}+119C^{5}+159C^{4}+169C^{3}+127C^{2}+74C+32\right)}{C^{2}\left(2C^{2}+C+1\right)^{2}}.$

The expected width is

$\frac{2C^{4}+6C^{3}+7C^{2}+7C+6}{2C^{3}+C^{2}+C}$

with variance

$\frac{2\left(2C^{8}+6C^{7}+21C^{6}+45C^{5}+60C^{4}+74C^{3}+59C^{2}+35C+18\right)}{C^{2}\left(2C^{2}+C+1\right)^{2}}.$

####  2.4.4 The Double Sided Case

######  Theorem 2.57.

Let $H(x,y)$ be the bivariate ordinary generating function for paths for which
the first segment is a hook path on $L_{\infty}$. Then

$H(x,y)=\frac{x^{2}y}{3}+\frac{2Cx^{4}y^{2}}{3(1+C)(2-x^{2}y)}$

######  Theorem 2.58.

Let $T(x,y)$ be the bivariate ordinary generating function for paths for which
the first segment is a twist path on $L_{\infty}$. Then

$T(x,y)=\frac{2x^{3}y^{2}}{3(1+C)(2-xy)}$

######  Theorem 2.59.

Let $L_{\infty}(x,y)$ be the bivariate ordinary generating function for a GSAW
that terminates. Then

$L_{\infty}(x,y)=(H(x,y)+T(x,y))\underline{L}^{\ast}_{\infty}(x,y)$

######  Corollary 2.60.

The probability that a GSAW with nearest-neighbor weighing on $L_{\infty}$
terminates is 1.

######  Corollary 2.61.

The expected number of steps taken before a GSAW with nearest-neighbor
weighing on $L_{\infty}$ terminates is

$\frac{2\left(6C^{5}+41C^{4}+56C^{3}+51C^{2}+38C+12\right)}{3C(C+1)\left(2C^{2}+C+1\right)}$

with variance

$\scalebox{1.2}{$\frac{2\left(72C^{10}+360C^{9}+1312C^{8}+2975C^{7}+4693C^{6}+5864C^{5}+5822C^{4}+4551C^{3}+2773C^{2}+1242C+288\right)}{9C^{2}(C+1)^{2}\left(2C^{2}+C+1\right)^{2}}$}.$

The expected width is

$\frac{6C^{4}+32C^{3}+28C^{2}+28C+18}{6C^{3}+3C^{2}+3C}$

with variance

$\frac{2\left(18C^{8}+54C^{7}+229C^{6}+445C^{5}+590C^{4}+686C^{3}+541C^{2}+315C+162\right)}{9C^{2}\left(2C^{2}+C+1\right)^{2}}.$

## 3\. Discussion

Figure 7 shows the trapping probability distributions in the square and
triangular strips from the generating functions in Theorems 2.21 and 2.44.
Several features are apparent which can be compared to those observed in
infinite lattices (Figure 9, Appendix). There is strong even-odd asymmetry for
small trapping length in the square lattice, but not the triangular lattice.
The triangular lattice has a higher mean trapping length than the square
lattice, but the triangular probability distribution decays with a weaker
exponential tail compared to the square lattice. All of these features are
observed when comparing the infinite square and triangular lattices.

Figure 7: Trapping probability distribution of ladder graphs on the square and
triangular lattices, according to Theorems 2.21 and 2.44. Short walks on the
square lattice are much more likely to become trapped after an odd number of
steps. The trapping probability decays exponentially as approximately
$0.93^{N}$ for the triangular case and $0.90^{N}$ for the square case. The
vertical lines indicate the mean trapping lengths.

The decay constant of the exponential tails of the probability distributions
can be exactly solved as the reciprocals of the poles of the generating
functions that are closest to the origin [16]. For the square lattice, the
relevant pole is the reciprocal of the largest root of the cubic polynomial in
the denominator of the generating function. In the long-walk limit, the square
lattice probability distribution decays as
$\left(\cos(\pi/7)\right)^{N}\approx 0.901^{N}$. For the triangular lattice,
the relevant pole is the reciprocal of the largest real root of the quartic
polynomial in the denominator of the generating function. In the long-walk
limit, the triangular lattice probability distribution decays as approximately
$0.93^{N}$. The weaker exponential decay on the triangular lattice is
consistent with a longer mean trapping length, as well as the asymptotic
behavior on infinite lattices, seen in the inset of Figure 9.

The generating functions for the square and triangular lattices are equivalent
to inhomogeneous recursion relations. The square lattice has a third-order
recursion relation with alternating even and odd inhomogeneous terms decaying
as a negative power of two:

$P_{N}=\frac{P_{N-1}}{2}+\frac{P_{N-2}}{2}-\frac{P_{N-3}}{8}+\begin{cases}-\left(N-6\right)\cdot
2^{-(\frac{N+4}{2})}&\text{Even N}\\\ \ \ \left(N-3\right)\cdot
2^{-(\frac{N+3}{2})}&\text{Odd N}\end{cases}.$ (1)

The triangular lattice has a fourth-order recursion relation with strictly
positive inhomogeneous terms decaying as a negative power of three:

$P_{N}=\frac{5}{6}P_{N-1}-\frac{1}{18}P_{N-2}+\frac{1}{6}P_{N-3}-\frac{1}{36}P_{N-4}+\frac{1}{16}\cdot\begin{cases}\left(\frac{5}{2}N+7\right)\cdot
3^{-(\frac{N+2}{2})}&\text{Even N}\\\
\left(\frac{3}{2}N+\frac{7}{2}\right)\cdot 3^{-(\frac{N+1}{2})}&\text{Odd
N}\end{cases}.$ (2)

The initial values in these recursion relations are 1/24, 1/48, and 7/96 for
N=5, 6, 7 in the square case and 1/54, 11/324, 43/972, and 95/1944 for N=4, 5,
6, 7 for the triangular case. The characteristic polynomials of each
homogeneous component of the recursion relations have zeros that describe the
asymptotic behavior discussed previously. The inhomogeneous components,
representing the contribution to the probability of ladder graphs that cannot
be constructed by appending steps to smaller graphs, highlight the striking
parity effects seen only in the square lattice. Both inhomogeneous components
vanish with large N, reducing to the asymptotic homogeneous trend. In the
square lattice, the inhomogeneous terms alternate between positive and
negative, putting the probability on either side of a trendline. The
triangular inhomogeneous terms are strictly positive, and decay more strongly
as a power of one-third rather than one-half, resulting in a smooth
probability distribution.

The weighted walks on a square lattice have a mean trapping length (Corollary
2.61) that is non-monotonic with respect to the trapping length and is plot in
Fig. 8. There is a global minimum at $C\approx 1.63$ which in the
thermodynamic formalism [7] corresponds to approximately $kT/2$,111kT being
the thermal energy scale, the product of temperature $T$ and Boltzmann
constant $k$. slightly larger than for the infinite square lattice which has a
global minimum at $\approx kT/3$ or $C$=1.4. The asymptotic behavior of
Corollary 2.61 is that the mean trapping length grows as $\langle
N\rangle=2C$, which is equivalent to the exponential behavior seen in the
infinite lattice. Corollary 2.61 also admits values of $C$ below 1,
corresponding to walks that avoid self-adjacency. The mean trapping length
increases asymptotically as $C$ approaches zero, and may be interpreted as the
behavior as a polymer with strong electrostatic (rather than excluded volume)
repulsion. Each probability distribution for a weighted lattice walk has an
exponential decay constant that is the reciprocal of a quartic root (for
$C\neq$ 1). The decay constant has a global minimum at a value of $C\approx
1.75$, slightly greater than the position of the global minimum of the mean
trapping length , $C\approx 1.63$.

Figure 8: Mean trapping length as a function of the weighting factor $C$ for
biased walks according to Corollary 2.61. There is a global minimum at
$C=1.63$ and the growth is asymptotically linear in $C$.

## 4\. Conclusion

We have developed an exactly solvable model of the growing self-avoiding walk.
It allows us to exactly derive the mean trapping length of walks on square and
triangular lattices that are two sites high. Additionally, we have shown that
the exact probability distributions mirror the behavior seen in infinite
square and triangular lattices, as well as empirical behavior observed for
biased GSAWs. Restricting the lattice to two sites in height prevents
combinatorial explosion while admitting non-trivial behavior. Strips of height
greater than two are significantly more complex and will be discussed in Part
II [9]. We hope that this work inspires further investigation into exact
solutions for stochastic systems in statistical mechanics.

## 5\. Acknowledgements

We are grateful to Jay Pantone for insightful discussions during the writing
of this manuscript. We also acknowledge helpful suggestions from Tony Guttmann
and Nathan Clisby. ARK is supported by the National Science Foundation, grant
number 2105113.

## 6\. Appendix

###  6.1 Infinite Lattices: numerical results

To compare the ladder walks with those of unrestricted lattices, we compute
the trapping probability distribution on square, triangular, and honeycomb
lattices. A walk was initiated in the center of a 512 by 512 matrix, with
steps to unoccupied adjacent sites chosen by a random number generator in
MATLAB. Previously, the trapping distribution of 60,000 walks was reported by
Renner [13]. Here, we present histograms of the trapping distributions after
1,000,000 simulated walks. Approximately ten walks out of each million reached
the wall of simulation box, which we do not consider to have a significant
effect.

The even-odd asymmetry of the square lattice has been established [6, 7]. The
triangular lattice lacks this asymmetry and has a trapping probability
distribution that is much smoother. Trapping in the honeycomb lattice is most
likely at a multiple of four plus one. The square and honeycomb probability
distributions have very similar exponential behavior, while the triangular
case decays with a weaker constant.

Figure 9: Trapping probability distribution for GSAWs on the square,
triangular, and honeycomb lattices. Inset shows the same data on semi-
logarithmic axes. For walks trapped after a short distance, square lattice
walks are more likely to become trapped after an odd number of steps, the
triangular lattice imposes a smooth distribution, and walks on the honeycomb
lattice is most likely to be trapped at a multiple of four plus one. For walks
trapped after a long distance, the square and honeycomb lattices have the same
asymptotic exponenitial behavior while the triangular lattice has a weaker
exponential decay.

## References

  * Chuang et al. [2019] Hui-Min Chuang, Jeffrey G Reifenberger, Aditya Bikram Bhandari, and Kevin D Dorfman.  Extension distribution for dna confined in a nanochannel near the odijk regime.  _The Journal of Chemical Physics_ , 151(11):114903, 2019.
  * Clisby [2010] Nathan Clisby.  Accurate estimate of the critical exponent $\nu$ for self-avoiding walks via a fast implementation of the pivot algorithm.  _Physical review letters_ , 104(5):055702, 2010\.
  * Clisby et al. [2007] Nathan Clisby, Richard Liang, and Gordon Slade.  Self-avoiding walk enumeration via the lace expansion.  _Journal of Physics A: Mathematical and Theoretical_ , 40(36):10973, 2007.
  * Cotton [1980] JP Cotton.  Polymer excluded volume exponent v: An experimental verification of the n vector model for n= 0.  _Journal de Physique Lettres_ , 41(9):231–234, 1980.
  * Hemmer and Hemmer [1986] PC Hemmer and S Hemmer.  Trapping of genuine self-avoiding walks.  _Physical Review A_ , 34(4):3304, 1986.
  * Hemmer and Hemmer [1984] S Hemmer and PC Hemmer.  An average self-avoiding random walk on the square lattice lasts 71 steps.  _The Journal of Chemical Physics_ , 81(1):584–585, 1984.
  * Hooper and Klotz [2020] Wyatt Hooper and Alexander R Klotz.  Trapping in self-avoiding walks with nearest-neighbor attraction.  _Physical Review E_ , 102(3):032132, 2020.
  * Jensen [2004] Iwan Jensen.  Enumeration of self-avoiding walks on the square lattice.  _Journal of Physics A: Mathematical and General_ , 37(21):5503, 2004.
  * [9] Alexander R. Klotz, Jay Pantone, and Everett Sullivan.  Exactly-solvable self-trapping lattice walks. II. Lattices of arbitrary height.  _Forthcoming._
  * Lyklema and Kremer [1984] JW Lyklema and K Kremer.  The growing self avoiding walk.  _Journal of Physics A: Mathematical and General_ , 17(13):L691, 1984.
  * McKenzie and Moore [1971] DS McKenzie and MA Moore.  Shape of self-avoiding walk or polymer chain.  _Journal of Physics A: General Physics_ , 4(5):L82, 1971.
  * Odijk [1983] Theo Odijk.  The statistics and dynamics of confined or entangled stiff polymers.  _Macromolecules_ , 16(8):1340–1344, 1983.
  * Renner et al. [1996] A Renner, E Bornberg-Bauer, IL Hofacker, PK Schuster, and PF Stadler.  Self-avoiding walk models for non-random heteropolymers.  _Thesis_ , 1996.
  * Schram et al. [2011] Raoul D Schram, Gerard T Barkema, and Rob H Bisseling.  Exact enumeration of self-avoiding walks.  _Journal of Statistical Mechanics: Theory and Experiment_ , 2011(06):P06019, 2011.
  * Werner and Mehlig [2014] E Werner and B Mehlig.  Confined polymers in the extended de gennes regime.  _Physical review E_ , 90(6):062602, 2014.
  * Wilf [2005] Herbert S Wilf.  _generatingfunctionology_.  CRC press, 2005.