# Weakly prudent self-avoiding bridges.

1 Introduction

A self-avoiding walk (SAW) [omega] on a graph G is a sequence ([[omega].sub.0], [[omega].sub.1], ..., [[omega].sub.n]) of distinct vertices of G with consecutive vertices [[omega].sub.i]; [[omega].sub.i+1] adjacent. While any graph is a valid choice for G, the most frequently used are infinite lattices like the hypercubic lattice [Z.sup.d] or the honeycomb lattice H, and here we restrict the definition to these settings. SAWs were first considered by researchers in statistical physics [16], where they were used as models of long-chain polymers in solution. They were later taken up by combinatorialists and probability theorists, and there has since developed a large body of research on the topic; see [14] for a thorough review.

Despite decades of study, there is still remarkably little known about SAWs, especially in low (less than five) dimensions. In two and three dimensions, the number [c.sub.n] of SAWs of length n (up to translation) is expected to behave asymptotically like

[c.sub.n] ~ A[n.sup.[gamma]-1] [[mu].sup.n],

where A and [mu] are lattice-dependent constants and [gamma] depends only on the dimension. In two dimensions there are strong arguments (e.g. [15]) for the critical exponent being [gamma] = 43/32, but these are so far considered to be non-rigorous. The growth constant(i) p is currently unknown for all regular lattices in two or more dimensions, with the sole exception being the honeycomb lattice. There, its value [mu] = [square root of 2 + [square root of 2]] was conjectured in 1982 [15] and proven in 2012 [8]. For the square lattice Z2 (the setting of this article), the best current estimate [5] is

[mu] [approximately equal to] 2.63815853035(2).

Given the difficulty of the general SAW problem, one approach that has yielded many fruitful results is to consider subclasses of SAWs which obey extra restrictions on top of the self-avoiding constraint, the hope being that properties of the subclasses may shed light on general SAWs. Broadly speaking, one wishes to use restrictions which satisfy two (often competing) criteria:

i. the restrictions should be as loose as possible, so that the model "resembles", in some sense, the larger SAW model; and

ii. the restrictions should lead to some kind of (probably recursive) structure, so as to enable us to obtain solutions for their generating functions, coefficients, etc.

The simplest solved models on the square lattice obey a directedness constraint: they are forbidden from stepping in one (or more) direction on the lattice. Fully directed (sometimes just called directed) walks can step in at most two directions on the lattice (e.g. north and east), while partially directed walks can step in at most three directions (e.g. north, east and south). Such models can perhaps be viewed as leaning more towards criterion (ii) above than (i)--they have a simple recursive structure, but are far simpler than general SAWs. (ii) In particular, partially directed walks have an exponential growth rate of 1 + [square root of 2] [approximately equal to] 2.41 (cf. the growth constant [mu] [approximately equal to] 2.64 of SAWs).

More general than directed walks are prudent walks [6, 4]. These are SAWs which are forbidden from stepping towards a vertex they have already visited. Prudent walks can naturally be divided into four sub-classes (a more detailed explanation is given in the next section), and for three of these subclasses the generating functions have been solved. The most general of those three subclasses has a growth rate of about 2.48.

A larger growth rate, of about 2.54, is achieved by weakly directed walks [1]. These are walks for which any sub-walk connecting two visits to the same horizontal line of the lattice is partially directed. This is equivalent to saying that the irreducible factors (defined below) of a weakly directed walk are partially directed. The model considered in this article is defined in much the same spirit as weakly directed walks, and in fact (as the title may suggest) essentially combines the concepts of prudent walks and weakly directed walks.

We note here that larger growth rates (indeed, with sufficient computing power, growth rates arbitrarily close to that of SAWs) can be achieved by counting all irreducible SAW factors up to a maximum length k, and then constructing walks by concatenating those pieces [11]. The fact that the "solvability" of such models depends on computing power makes them, in our eyes, somewhat inelegant, and we are loathe to call them a "solvable" model in the same way as directed or prudent walks.

This extended abstract is organised as follows. In Section 2, we define weakly prudent bridges and give preliminary results. In Section 3, we derive the generating function of these walks. In Section 4, we give asymptotic results and in particular an estimate of the growth constant of weakly directed bridges. Finally, in Section 5, we discuss the random sampling of these walks.

2 Definitions and preliminary results

2.1 Weakly prudent bridges

We begin by setting out some definitions relating to prudent walks. Where possible, we use the same terminology as in [4]. Define a prefix of a walk [omega] = ([[omega].sub.0], ..., [[omega].sub.n]) to be a sub-walk ([[omega].sub.0], ..., [[omega].sub.i]) with 0 [less than or equal to] i [less than or equal to] n.

Definition 1 The bounding box of a SAW [omega] is the smallest rectangle on the lattice which encloses w.

It is straightforward to see that the endpoint of any prudent walk must lie on the boundary of its bounding box. (If not, then the walk must have stepped off the boundary into the interior of its bounding box, and such a step could not possibly be prudent.) This leads to a natural sub-classification of prudent walks.

Definition 2 For a given S [subset or equal to] {north, east, south, west} [equivalent to] {N, E, S, W} a prudent walk [omega] is S-prudent if, for every prefix [omega]' of [omega], the endpoint of [omega]' lies on (at least) one of the S sides of its bounding box. If [absolute value of S] = k then we say that [omega] is k-sided.

Note that a 1-sided prudent walk is in fact a partially directed walk. (iii)

An important point to note here is that prudent walks are, in general, irreversible--that is, [omega] = ([[omega].sub.0], ..., [[omega].sub.n]) being a prudent walk does not mean [omega]' = ([[omega].sub.n], ..., [[omega].sub.0]) will be prudent. This is different to directed walks, where the reversal of a fully or partially directed walk will also be fully or partially directed. In light of this, we introduce the following, "new" class of walk:

Definition 3 A SAW [omega] = ([[omega].sub.0], ..., [[omega].sub.n]) is co-prudent if its reversal [omega]' = ([[omega].sub.n], ..., [[omega].sub.0]) is prudent. More specifically, [omega] is S-co-prudent if [omega]' is S-prudent, and is k-sided if [absolute value of S] = k.

Let y([upsilon]) be the y-coordinate of vertex v. Then [omega] = ([[omega].sub.0], ..., [[omega].sub.n]) is a self- avoiding bridge if y([[omega].sub.0]) < y([[omega].sub.i]) [less than or equal to] y([[omega].sub.n]) for 1 [less than or equal to] i [less than or equal to] n. (We could instead have y([[omega].sub.0]) [less than or equal to] y([[omega].sub.i]) < y([[omega].sub.n])--it makes no difference from an enumerative point of view.) The usefulness of bridges stems from the fact that they can be freely concatenated without risk of intersection--see [10, 11, 12, 3] for a number of applications. A bridge is irreducible if it cannot be written as the concatenation of two or more smaller bridges. Every bridge can be uniquely decomposed into a sequence of irreducible bridges.

We are now prepared to define our objects of interest:

Definition 4 A self-avoiding bridge [omega] is weakly prudent if each of its irreducible bridges is prudent or co-prudent. If all those irreducible bridges are k-sided then we say [omega] is k-sided.

If k = 1 then all the irreducible bridges are partially directed, and we exactly recover the weakly directed bridges of [1]. The next most general case is thus k = 2, and it is this case that we will consider in this article. A 2-sided weakly prudent bridge is shown in Figure 1 (left).

Note that in [1], the authors give two equivalent definitions for weakly directed bridges--they are bridges whose irreducible components are partially directed, or equivalently, bridges which are partially directed between any two visits to the same horizontal line. For k [greater than or equal to] 2, the analogous definitions are not the same for weakly prudent walks--for example, Figure 1 (right) shows an irreducible bridge which is prudent between any two visits to a horizontal line, but not prudent overall.

Finally, we give a name to a subset of self-avoiding bridges which will lighten notation throughout the rest of the article.

Definition 5 Let x([upsilon]) denote the x-coordinate of a vertex [upsilon]. A self-avoiding bridge [omega] = ([[omega].sub.0], ..., [[omega].sub.n]) is a ramp if x([[omega].sub.i]) [less than or equal to] x([[omega].sub.n]) for 0 [less than or equal to] i [less than or equal to] n.

2.2 Irreducible factors and generating functions

Here we set out exactly what the objects are that we will be enumerating, before considering their generating functions in the next section. Let W [equivalent to] W(t) be the generating function of 2-sided weakly prudent bridges. By definition, we have:

W = [I/1 - I], (1)

where I [equivalent to] I(I) is the generating function of irreducible 2-sided prudent or co-prudent bridges. To compute the generating function I, we use the following two elementary lemmas, for which we omit the proofs.

Lemma 6 The irreducible bridges of a 2-sided weakly prudent bridge are NE- or NW-prudent or SE- or SW-co-prudent,

Lemma 7 An irreducible bridge is both 2-sided prudent and co-prudent if and only if it is partially directed,

Let [P.sub.I] [equivalent to] [P.sub.I] (I) tee the generating function of irreducible NE-prudent ramps, and let [D.sub.I] [equivalent to] [D.sub.I] (t) be the generating function of irreducible partially directed ramps. Using the two lemmas, we have:

I = 4[P.sub.I] - 2[D.sub.I] - I. (2)

Combining (1) and (2) then provides a way to compute the generating function of weakly prudent bridges in terms of the generating functions of irreducible prudent ramps and irreducible partially directed ramps. We compute these functions in Section 3.

3 Recursive constructions and generating functions

In this section we describe ways of constructing irreducible 2-sided prudent bridges, encode those constructions as functional equations satisfied by generating functions, and give solutions to those equations. Since we're now only dealing with the 2-sided case, we will henceforth just use "prudent" to refer to NE-prudent walks or bridges.

In this extended abstract, we give details for only one of the methods and briefly describe another one in Section 3.4.

3.1 Partially directed ramps

We begin with the simplest objects that we need to consider, partially directed ramps. Recall that by (2), we need DI, the generating function of irreducible partially directed ramps. Fortunately this generating function has already been derived in [1], and so we present the result while referring the reader to that article for a detailed derivation.

Proposition 8 (Bacher & Bousquet-Melou) The generating function DI of irreducible partially directed ramps is

[D.sub.I] = [D/1 + D], (3)

where D [equivalent to] D(t) is the generating function of (not necessarily irreducible) partially directed ramps. This generating function is given by

D = [[infinity].summation over (k=0)] [[t.sup.k+1]/[G.sub.k]], (4)

where [G.sub.k] [equivalent to] [G.sub.k] (t) is the sequence of polynomials defined by

[G.sub.-1] = 1, [G.sub.0] = 1 - t, and for k [greater than or equal to] 1, [G.sub.k] = (1 - t + [t.sup.2] + [t.sup.3])[G.sub.k-1] - [t.sup.2][G.sub.k-2].

3.2 Factorisation of prudent ramps

The equation (3), used in the derivation of the generating function [D.sub.I], is a consequence of the following fact: a partially directed ramp can be decomposed uniquely into a concatenation of irreducible partially directed ramps, and conversely any sequence of irreducible partially directed ramps can be concatenated to give a unique partially directed ramp. In this section we aim to find a corresponding factorisation of prudent ramps.

Unfortunately, factorising prudent ramps into irreducible bridges does not work: while the irreducible bridges of a prudent bridge will certainly be prudent, the concatenation of a sequence of irreducible prudent bridges need not be prudent. For irreducible prudent ramps, it is the other way around: the concatenation of a sequence of prudent ramps will also be a prudent ramp, but not all prudent ramps can be decomposed into a sequence of irreducible ramps.

To work around this problem, we define the following walks, slightly more general than irreducible prudent ramps. Examples are given in Figure 2.

Definition 9 If a ramp [omega] can be written as the concatenation [alpha] [omicron] [beta] of two shorter ramps, we say [omega] is r-reducible, otherwise [omega] is r-irreducible.

Note that all irreducible ramps are also r-irreducible, but the converse is not true (see Figure 2, right). To go from r-irreducible ramps to irreducible ones, we need the following definition as wells as two lemmas, which we give without proof.

Definition 10 A prudent ramp [omega] is a hook-ramp if it satisfies two properties:

* [omega] has a prefix [[omega].sup.*] of the form [[omega].sup.*] = {N, W, ..., W} containing at least one west step, and

* the walk [omega]\[[omega].sup.*] (i.e. [omega] with [[omega].sup.*] removed from its start) is a ramp.

Lemma 11 Every prudent ramp has a unique decomposition into r-irreducible prudent ramps; conversely, the concatenation of any number of r-irreducible prudent ramps is a prudent ramp.

Lemma 12 Let [omega] be a prudent ramp and [[omega].sup.(1)] [omicron] ... [omicron] [[omega].sup.(l)] be its decomposition into r-irreducible prudent ramps, Then [[omega].sup.(1)] is irreducible if and only if [omega] is not a hook-ramp,

Let P, [??] and [P.sub.R] be the generating functions of prudent ramps, hook-ramps, and r-irreducible prudent ramps, respectively. As a consequence of the two above lemmas, we have:

P = [[P.sub.R]/1 - [P.sub.R]], P - [??] = [[P.sub.I]/1 - [P.sub.R]], and hence [P.sub.I] = [P - [??]/1 + P]. (5)

3.3 Enumeration of prudent ramps and hook-ramps

Here, we compute the generating functions P and [??] defined above. To do this, we first define generating functions counting slightly" more general objects.

We say that a non-empty walk [omega] = ([[omega].sub.0], ..., [[omega].sub.n]) is positive if y([[omega].sub.0]) < y([[omega].sub.i]) for 1 [less than or equal to] i [less than or equal to] n. Define the generating functions

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [e.sub.n,i,j] (resp. [n.sub.n,i,j]) is the number of positive NE-prudent walks of length n which end on the east (resp. north) side of their box, with distance i from the endpoint to the north-east corner of the box and distance j + 1 from the endpoint to the south side of the box.

The variables u and [upsilon] are called catalytic variables--the idea being that they are included in the generating functions to facilitate recursive constructions, but the distances they measure are ultimately of no interest. Since prudent ramps are exactly positive prudent walks ending at a distance zero from the north-east corner of their box, we have P = E(0,1).

Lemma 13 The generating functions E and N satisfy the functional equations

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (6)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (7)

Proof (sketch): We generate walks recursively, by considering how a walk of given dimensions n, i, j can be extended by adding steps. We use the same ideas as presented in [4] for constructing prudent walks. There, Bousquet-Melou partitions walks according to their last inflating step (LIS)--the last step which moved one of the relevant k sides of the bounding box of a k-sided walk. Here, the last inflating step could have been north or east. For convenience, we do not consider the initial north step as inflating.

We divide walks ending on the east side of their box according to their LIS:

* No inflating step: The only walk ending on the east side of its box with no inflating steps is the single north step, with generating function t.

* LIS east: Before the LIS, the walk must have ended on the east side of its box; after, it can step north as far as the top of the box or south as far as the line y = 1. Such walks are counted by

[t/1 - [tu.sup.-1] - [upsilon]] (E(u, [upsilon]) - [tu.sup.-1] [upsilon]E(t[upsilon], [upsilon])) + [[t.sup.2]u[[upsilon].sup.-1]/1 - tu[[upsilon].sup.-1]] (E(u, [upsilon]) - E(u, tu)).

* LIS north: Before the LIS, the walk must have ended on the north side of its box; after, it must step east to the north-east corner of the box. Such walks are counted by t[upsilon]N(t, [upsilon]).

This decomposition gives the equation (6). Walks ending on the north side of their box are handled similarly:

* No inflating step: this is a north step followed by a (possibly empty) sequence of west steps.

* LIS east: before the LIS, the walk must have ended on the east side of its box; after, it must step north to the north-east corner of the box.

* LIS north: before the LIS, the walk must have ended on the north side of its box; after, it can step east as far as the north-east corner of the box, or west for an arbitrary distance.

We thus get the equation (7).

Proposition 14 The generating function P of NE-prudent ramps is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (8)

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

U([upsilon]) [equivalent to] U (t, [upsilon]) is the unique power series solution of the equation t - (1 - t[upsilon] + [t.sup.2] + [t.sup.3] [upsilon])U + t[U.sup.2] = 0:

U([upsilon]) = [1 - t[upsilon] + [t.sup.2] + [t.sup.3] [upsilon] - [square root of [(1 - t[upsilon] + [t.sup.2] + [t.sup.3] [upsilon]).sup.2] - 4[t.sup.2]]/2t],

and q [equivalent to] q(t) = U(1).

Proof (sketch): The proof is done with the kernel method [13, 2, 17], and more specifically its variant the iterated kernel method [19]. The general idea is to generate more equations satisfied by the generating functions by finding values of the catalytic variables which cancel the kernels - the coefficients of the generating functions on the left-hand sides of (6) and (7).

We start by making the substitution u [??] U([upsilon]) in (7), which by definition of U([upsilon]) cancels the left- hand side. This leads to the equation:

0 = [t/1 - tU([upsilon])] - [[t.sup.2] [upsilon]/U([upsilon]) - t] N(t, [upsilon]) + tE(t[upsilon], [upsilon]).

We use this equation to eliminate the N(t, [upsilon]) from (6):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (9)

Then, we make the substitutions (u, [upsilon]) [??] (q[upsilon], [upsilon]) and (u, [upsilon]) [??] (q[upsilon], [q.sup.2] [upsilon]) in (9), which both cancel the left-hand side. This leads to two equations relating the power series E(t[upsilon], [upsilon]), E(q[upsilon], tq[upsilon]) and E(t[q.sup.2] [upsilon], [q.sup.2] [upsilon]). Eliminating E(q[upsilon], tq[upsilon]), we finally get:

E(t[upsilon], [upsilon]) = A([upsilon]) + B([upsilon])E(t[q.sup.2] [upsilon], [q.sup.2][upsilon]),

where A([upsilon]) and B([upsilon]) are as written in the proposition. Iterating this equation, we get (with a convergence argument):

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Finally, substituting (u, [upsilon]) [??] (0, 1) in (9) gives the desired generating function P = E(0, 1) as a function of E (t, 1).

The generating function [??] of prudent hook-ramps is handled in the exact same manner. Due to the lack of space, we do not give the proofs. We define positive prudent hook-walks in the same manner as hook-ramps and let [??](u, [upsilon]) [equivalent to] E(t, u, [upsilon]) (resp. [??](u, [upsilon]) [equivalent to] N(t, u, [upsilon])) be the generating function of positive prudent hook-walks ending on the east (resp. north) side of their box, where the catalytic variables u and [upsilon] play roles similar as above. We get the following results.

Lemma 15 The generating functions E and N satisfy the functional equations

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (11)

Proposition 16 The generating function P = P(t) of NE-prudent hook-ramps is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (12)

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

and B([upsilon]), U([upsilon]) and q are as defined in Proposition 14.

Combining (5), (8) and (12), we obtain an explicit expression for [P.sub.I]. With the results of Sections 2.2 and 3.1, we thus get an expression for the generating function W of weakly prudent bridges.

3.4 Direct enumeration of irreducible prudent ramps

In this section, we briefly mention another way of computing the generating function [P.sub.I] of irreducible prudent ramps. Instead of using the combinatorial machinery of factorisation into r-irreducible ramps, we can generate irreducible prudent ramps directly. This requires the use of three catalytic variables instead of two and a system of four equations rather than two.

As a testament to the usefulness of the kernel method, this system can still be solved. It gives a solution for [P.sub.I] with a slightly more complicated structure (an infinite sum of functions which are themselves infinite sums of algebraic functions). Full details will appear in a longer version of this article.

4 Analysis and asymptotics

In order to study the asymptotic behaviour of the number wn of weakly prudent bridges, we will examine the analytic properties of the generating function W. The relationship between the asymptotics of [w.sub.n] and the properties of W can be determined via a process known as singularity analysis--see [9] for the definitive discussion of the topic.

4.1 NE-prudent ramps and hook-ramps

As we have seen, the generating function W can be written as a rational function of generating functions of other objects, and so its analytic properties can be determined by looking at those intermediate functions. Here, we state the central result regarding the generating functions P and [??].

Theorem 17 The generating functions P of NE-prudent ramps and P of NE-prudent hook ramps, given by Propositions 14 and 16, are analytic for [absolute value of t] < [rho], where [rho] [approximately equal to] 0.403 is the smallest positive root of the polynomial 1 - 2x - 2[x.sup.2] + 2[x.sub.3]. They are meromorphic on the disc [absolute value of t] < [sigma] where [sigma] = [square root of 2] - 1 [approximately equal to] 0.414, with an infinite sequence of simple poles on the real interval [[rho], [sigma]) which accumulate at [sigma]. The functions P and [??] are thus non-D-finite.

The poles between [rho] and [sigma] occur at t = [t.sub.2l], l [greater than or equal to] 0, defined as the unique root in t [member of] (0, [sigma]) of the equation (q - t)(U([q.sup.2l]) - t)/[t.sup.2] = 1. At l = 0 we have [t.sub.0] = [rho], and [t.sup.2l] < [t.sub.2(l+1)] with [t.sub.2l] [right arrow] [sigma] as l [right arrow] [infinity].

Unfortunately, despite (5) giving a relationship between P, [??] and [P.sub.I], we are unable to conclude that [P.sub.I] is non-D-finite, though we strongly expect this to be the case.

4.2 Weakly prudent bridges

The complicated nature of the generating function W of weakly directed bridges leaves us unable to locate any of its singularities exactly. In particular, we are unable to prove that W is not D-finite. However, we are able to find upper and lower bounds to very high precision.

Proposition 18 The dominant singularity [t.sub.c] of W satisfies

[t.sub.lower] < [t.sub.c] < [t.sub.upper],

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Thus [t.sub.c] is, correct to 101 digits,

[t.sub.c] [approximately equal to] 0.387871715348303762035973053063437193777254172060850 39570640936754499315178424994556331712759062537114.

From (1), singularities of W will occur at points where I = 1, or possibly at singularities of I. Regarding the latter, we know that any singularities of I cannot lie within the region [absolute value of t] < [rho], since irreducible 2-sided prudent (or co-prudent) bridges are a subset of 2-sided prudent walks. It suffices then to look for points satisfying I(t) = 1 within this region. The smallest (in absolute value) such point must be [t.sub.c], the dominant singularity of W. Since W is a power series in t with non-negative coefficients, by Pringsheim's theorem, its dominant singularity [t.sub.c] must occur on the positive real axis.

While we do have an explicit form for I, its structure (involving an infinite sum of algebraic functions) prevents us from performing exact inverse calculations, so we are forced to turn to numerical approximations.

The bounds [t.sub.lower] and [t.sub.upper] are calculated as follows:

* For the upper bound, we need a function [f.sub.upper] (t) satisfying [f.sub.upper] (t) < I(t). We use the polynomial obtained by truncating the power series of I at 6144 terms. The bound [t.sub.upper] is then the point at which [f.sub.upper] (t) = 1.

* For the lower bound, we need a function [f.sub.lower](t) satisfying [f.sub.lower](t) [greater than or equal to] I(t). We use

[f.sub.lower](t) = [f.sub.upper](t) + 4Q(t) - 4[f.sub.pru](t),

where Q(t) is the generating function of NE-prudent walks which end at the north-east corner of their box (obtained from Proposition 5 of [4]), and [f.sub.pru](t) is the polynomial obtained by truncating the power series of Q(t) at 6144 terms. The bound tlower is then the point at which [f.sub.lower](t) = 1.

Corollary 19 The number [w.sub.n] of weakly prudent bridges of length n is asymptotically

[w.sub.n] ~ c[[tau].sup.n],

where [tau] = [t.sup.-1] [approximately equal to] 2.57817201 and c is a positive constant.

This follows from the basic principles of singularity analysis [9]. The pole at [t.sub.c] is simple, since the derivative of I is non-negative at [t.sub.c] (it is a non-negative power series with radius of convergence at least [rho] > [t.sub.c]).

5 Random sampling

Finally, we were able to build an algorithm to randomly generate uniformly distributed weakly directed bridges. The algorithm belongs to the family of Boltzmann samplers [7], and is more precisely a critical Boltzmann sampler (Section 7.1 of the same reference). The algorithm outputs a bridge of length n in time O(n).

Due to the lack of space, we leave the details to a longer version. An example of output of the algorithm is shown in Figure 3.

References

[1] A. Bacher and M. Bousquet-Melou. Weakly directed self-avoiding walks. Journal of Combinatorial Theory, Series A, 118(8):2365-2391, 2011.

[2] C. Banderier, M. Bousquet-Melou, A. Denise, P. Flajolet, D. Gardy, and D. Gouyou-Beauchamps. Generating functions for generating trees. Discrete Mathematics, 246(1-3):29-55, 2002.

[3] N. R. Beaton, M. Bousquet-Melou, J. de Gier, H. Duminil-Copin, and A. J. Guttmann. The critical fugacity for surface adsorption of self-avoiding walks on the honeycomb lattice is 1 + %/2. Preprint, arXiv:1109.0358, 2012.

[4] M. Bousquet-Melou. Families of prudent self-avoiding walks. Journal of Combinatorial Theory, Series A, 117(3):313-344, 2010.

[5] N. Clisby and I. Jensen. A new transfer-matrix algorithm for exact enumerations: self-avoiding polygons on the square lattice. Journal of Physics A: Mathematical and Theoretical, 45(11):115202, 15 pp, 2012.

[6] E. Duchi. On some classes of prudent walks. In FPSAC'05, 2005.

[7] Philippe Duchon, Philippe Flajolet, Guy Louchard, and Gilles Schaeffer. Boltzmann samplers for the random generation of combinatorial structures. Combin. Probab. Comput., 13(4-5):577-625, 2004.

[8] H. Duminil-Copin and S. Smirnov. The connective constant of the honeycomb lattice equals [square root of 2 + [square of root of 2]]. Annals of Mathematics, 175(3):1653-1665, 2012.

[9] P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009.

[10] J. M. Hammersley and D. J. A. Welsh. Further results on the rate of convergence to the connective constant of the hypercubical lattice. The Quarterly Journal of Mathematics, 13(1):108-110, 1962.

[11] I. Jensen. Improved lower bounds on the connective constants for two-dimensional self-avoiding walks. Journal of Physics A: Mathematical and General, 37(48):11521-11529, 2004.

[12] H. Kesten. On the number of self-avoiding walks. Journal of Mathematical Physics, 4(7):960-969, 1963.

[13] D. E. Knuth. The Art of Computer Programming, vol. 1: Fundamental Algorithms. Addison-Wesley, Reading, MA, third edition, 1997.

[14] N. Madras and G. Slade. The Self-Avoiding Walk. Probability and Its Applications. Birkhauser, Boston, MA, 1993.

[15] B. Nienhuis. Exact critical point and critical exponents of O(n) models in two dimensions. Physical Review Letters, 49(15):1062-1065, 1982.

[16] W. J. C. Orr. Statistical treatment of polymer solutions at infinite dilution. Transactions of the Faraday Society, 43:12-27, 1947.

[17] H. Prodinger. The kernel method: a collection of examples. Seminaire Lotharingien de Combinatoire. Lothar. Combin., 50:Art. B50f, 19pp., 2003/04.

[18] E. J. J. van Rensburg. Statistical mechanics of directed models of polymers in the square lattice. Journal of Physics A: Mathematical and General, 36(15):R11-R61, 2003.

[19] E. J. J. van Rensburg, T. Prellberg, and A. Rechnitzer. Partially directed paths in a wedge. Journal of Combinatorial Theory, Series A, 115(4):623-650, 2008.

(i) Some authors refer to this quantity as the connective constant.

(ii) Directed walks do, however, lend themselves well to elegant polymer models in statistical mechanics - see [18] for an overview.

(iii) For 3-sided prudent walks, this definition is in fact slightly different to that used in [4], but that will not be an issue here.

Axel Bacher (1) * and Nicholas R. Beaton (2) ([dagger])

(1) RISC, Johannes Kepler universitat Linz, Austria

(2) MASCOS and Department of Mathematics and Statistics, The University of Melbourne, Australia

* Email: axel.bacher@risc.jku.at. I am funded by the project SFB F050-04 of the FWF.

([dagger]) Email: nrbeaton@unimelb.edu.au.