# Directed Percolation and Generalized Friendly Walkers

## Abstract

We show that the problem of directed percolation on an arbitrary lattice is equivalent to the problem of $`m`$ directed random walkers with rather general attractive interactions, when suitably continued to $`m=0`$. In 1+1 dimensions, this is dual to a model of interacting steps on a vicinal surface. A similar correspondence with interacting self-avoiding walks is constructed for isotropic percolation.

preprint: XXXX   

The problem of directed percolation (DP), first introduced by Broadbent and Hammersley , continues to attract interest even though it has so far defied all attempts at an exact solution, even in two dimensions. Although the problem was originally formulated statically on a lattice with a preferred direction, when the latter is interpreted as time the universal behavior close to the percolation threshold is also believed to describe the transition from a noiseless absorbing state to a noisy, active one, which occurs in a wide class of stochastic processes . It also maps onto reggeon field theory, which describes high-energy diffraction scattering in particle physics .

Some time ago, Arrowsmith, Mason and Essam  argued that the pair connectedness probability $`G(r,r^{})`$ for directed bond percolation on a two-dimensional diagonal square lattice can be related to the partition function for the weighted paths of $`m`$ ‘friendly’ walkers which all begin at $`r`$ and end at $`r^{}`$, when suitably continued to $`m=0`$. These are directed random walks which may share bonds of the lattice but do not cross each other (see Fig. 1). In fact, Arrowsmith et al  represented these configurations in other ways: either as vicious walkers, which never intersect, by moving the friendly walkers each one lattice spacing apart horizontally; or as integer flows on the directed lattice, to be defined explicitly below. Arrowsmith and Essam  showed that $`G(r,r^{})`$ is also related to a partition function for a $`\lambda `$-state chiral Potts model on the dual lattice, on setting $`\lambda =1`$, thus generalizing the well-known result of Fortuin and Kasteleyn for ordinary percolation.

In a more recent paper, Tsuchiya and Katori  have considered instead the order parameter of the DP problem, and have shown that in d=2 it is related to a certain partition function of the same $`\lambda =1`$ chiral Potts model, and also that, for arbitrary $`\lambda `$, the latter is equivalent to a partition function for $`m=(\lambda 1)/2`$ friendly walkers.

It is the purpose of this Letter to describe a broad generalization of these results. We demonstrate, in particular, a direct connection between a general connectedness function of DP and a corresponding partition function for $`m`$ friendly walkers when continued to $`m=0`$. We show that this holds on an arbitrary directed lattice in any number of dimensions, and for all variant models of DP, whether bond, site or correlated. Moreover the weights for a given number of walkers passing along a given bond or through a given site may be chosen in a remarkably arbitrary fashion, still yielding the same result at $`m=0`$.

We now describe the correspondence between these two problems in detail. A directed lattice is composed of a set of points in $`𝐑^d`$ with a privileged coordinate $`t`$, which we may think of as time. Pairs of these sites $`(r_i,r_j)`$ are connected by fixed bonds, oriented in the direction of increasing $`t`$, to form a directed lattice. In the directed bond problem, each bond is open with a probability $`p`$ and closed with a probability $`1p`$, and in the site problem it is the sites which have this property. In principle the probabilities $`p`$ could be inhomogeneous, and we could also consider site-bond percolation and situations in which different bonds and sites are correlated. Our general result applies to all these cases, but for clarity we shall restrict the argument to independent homogeneous directed bond percolation. The pair connectedness $`G(r,r^{})`$ is the probability that the points $`r`$ and $`r^{}`$ (with $`t<t^{}`$) are connected by a continuous path of bonds, always following the direction of increasing $`t`$.

On the same lattice, let us define the corresponding integer flow problem. Assign a non-negative integer-valued current $`n(r_i,r_j)`$ to each bond, in such a way that it always flows in the direction of increasing $`t`$, and is conserved at the vertices. At the point $`r`$ there is a source of strength $`m1`$, and at $`r^{}`$ a sink of the same strength. There is no flow at times earlier than that of $`r`$ or later than that of $`r^{}`$. Such a configuration may be thought of as representing the worldlines of $`m`$ particles, or walkers, where more than one walker may share the same bond. The configurations are labeled by distinct allowed values of the $`n(r_i,r_j)`$, so that they are counted in the same way as are those of identical bosons. Alternatively, in $`1+1`$ dimensions, we may regard the walkers as distinct but with worldlines which are not allowed to cross. In the partition sum, each bond is counted with a weight $`p(n(r_i,r_j))`$. In the simplest case we take $`p(0)=1`$ and $`p(n)=p`$ for $`n1`$ (although we shall show later that this may be generalized). Since $`p>p^n`$ for $`n>1`$, there is an effective attraction between the walkers, leading to the description ‘friendly’. The partition function is then

$$Z(r;r^{};m)\underset{\mathrm{allowed}\mathrm{configs}}{}\underset{(r_i,r_j)}{}p(n(r_i,r_j))$$

This expression is a polynomial in $`m`$ and so may be evaluated at $`m=0`$. The statement of the correspondence between DP and the integer flow problem for the case of the pair connectedness is then

$$G(r;r^{})=Z(r;r^{};0).$$

Note that since the weights $`p(n)`$ behave non-uniformly as $`n0`$, the continuation of $`Z(r;r^{};m)`$ to $`m=0`$ is not simply the result of taking zero walkers (which would be $`Z=1`$): rather it is the non-trivial answer $`G`$. Similar results hold for more generalized connectivities. For example, if we have points $`(r_1^{},r_2^{},\mathrm{},r_l^{})`$ all at the same time $`t^{}>t`$, we may consider the probability $`G(r;r_1^{},r_2^{},\mathrm{},r_l^{})`$ that all these points, irrespective of any others, are connected to $`r`$. The corresponding integer flow problem has a source of strength $`ml`$ at $`r`$, and sinks of arbitrary (but non-zero) strength at each point $`r_j^{}`$. In this case

$$G(r;r_1^{},r_2^{},\mathrm{},r_l^{})=(1)^{l1}Z(r;r_1^{},r_2^{},\mathrm{},r_l^{};m=0)$$

where the partition function is defined with the same weights as before. Since the order parameter for DP may be defined as the limit as $`t^{}t\mathrm{}`$ of $`P(t^{}t)`$, the probability that any site at time $`t^{}`$ is connected to $`r`$, and this may be written using an inclusion-exclusion argument as

$$P(t^{}t)=\underset{r^{}}{}G(r;r^{})\underset{r_1^{},r_2^{}}{}G(r;r_1^{},r_2^{})+\mathrm{}$$

(where the sums over the $`r_j^{}`$ are all restricted to the fixed time $`t^{}`$), we see that it is in fact given by the $`m=0`$ evaluation of the partition function for all configurations of $`m`$ walkers which begin at $`r`$ and end at time $`t^{}`$. This generalizes the result of Tsuchiya and Katori  to an arbitrary lattice. Although this continuation to $`m=0`$ is reminiscent of the replica trick, it is in fact quite different. Moreover it is mathematically well-defined, since, as we argue below, $`Z`$ is a finite sum of terms, each of which, with the simple weights given above, is a polynomial in $`m`$.

We now give a summary of the proof, which is elementary. The connectedness function $`G(r;r_1^{},r_2^{},\mathrm{},r_l^{})`$ is given  by the weighted sum of all graphs $`𝒢`$ which have the property that each vertex may be connected backwards to $`r`$ and forwards to at least one of the $`r_j^{}`$. (Alternatively, $`𝒢`$ is a union of directed paths from $`r`$ to one of the $`r_j^{}`$.) Each such graph is weighted by a factor $`p`$ for each bond and $`(1)`$ for each closed loop. A simple example is shown in Fig. 2. A given graph corresponds to summing over all configurations in which the bonds in $`𝒢`$ are open, irrespective of all other bonds in the lattice. The factors of $`(1)`$ are needed to eliminate double-counting. It is useful to decompose vertices in $`𝒢`$ with coordination number $`>3`$ by inserting permanently open bonds into them in such a way that the only vertices are those in which two directed bonds merge to form one ($`21`$), and vice versa. This does not affect the connectedness properties. We may then associate the factors of $`(1)`$ with each $`12`$ vertex in $`𝒢`$, as long as we incorporate an overall factor $`(1)^{l1}`$ in $`G`$. With each graph $`𝒢`$ we associate a restricted set of integer flows, called proper flows, such that $`n1`$ for each bond in $`𝒢`$, and $`n=0`$ on each bond not in $`𝒢`$. Those corresponding to the graphs in Fig. 2 are shown in Fig. 3. Note that the last graph corresponds to $`m1`$ configurations of integer flows, which gives precisely the required factor of $`(1)`$ when we set $`m=0`$. In general, summing over all allowed integer flows will generate the sum over all allowed $`𝒢`$, with correct weights $`p`$: the non-trivial part is to show that we recover the correct factors of $`(1)`$ when we set $`m=0`$.

This follows from the following simple lemma: if $`A(n)`$ is a polynomial in $`n`$, and we define the polynomial $`B(m)_{n=1}^{m1}A(n)`$, then $`B(0)=A(0)`$. We give a proof which shows that the result may be generalized to other functions: write $`A(n)`$ as a Laplace transform $`A(n)=_C(ds/2\pi i)e^{ns}\stackrel{~}{A}(s)`$. Then $`B(m)=_C(ds/2\pi i)\left((e^se^{ms})/(1e^s)\right)\stackrel{~}{A}(s)`$, so that $`B(0)=_C(ds/2\pi i)\stackrel{~}{A}(s)=A(0)`$. An immediate corollary is that if $`A(n_1,n_2,\mathrm{})`$ is a polynomial in several variables, and $`B(m)_{n=1}^{m1}A(n,mn,\mathrm{})`$, then $`B(0)=A(0,0,\mathrm{})`$. We use this to proceed by induction on the number of $`12`$ vertices in $`𝒢`$. Beginning with the vertex which occurs at the earliest time, the contribution to $`Z`$ from the proper flow on $`𝒢`$, when evaluated at $`m=0`$, is, apart from a factor $`(1)`$, equal to that for another graph $`𝒢^{}`$ which will have one fewer $`12`$ vertex. However, $`𝒢^{}`$ differs from the previously allowed set of graphs $`𝒢`$ in that it may have more than one vertex at which current may flow into the graph. For this reason we extend the definition of the allowed set of graphs to include those in which every vertex is connected to at least one ‘input’ point $`(r_1,r_2,\mathrm{})`$ and at least one ‘output’ point $`(r_1^{},r_2^{},\mathrm{})`$. In the corresponding integer flow problem, currents $`(m_1,m_2,\mathrm{})`$ flow in at the inputs, whereas the only restriction on the outputs is that non-zero current should flow out. The partition function is then the weighted sum over all such allowed integer flows. Induction on the number of $`12`$ vertices then shows that this partition function, evaluated at $`m_j=0`$, gives the corresponding DP graph correctly weighted. (The induction starts from graphs with no $`12`$ vertices which involve no summations and for which the result is trivial.)

Since our main result relies only on the lemma it follows also for rather general weights $`p(n)`$. The only requirement is that $`p(n)`$ grow no faster than an exponential at large $`n`$, and that, when continued to $`n=0`$, it give the value $`p1`$. In this case, $`Z`$ will no longer be a polynomial in $`m`$, but, since by the inductive argument above it is given by a sum of convolutions of $`p(n)`$, its continuation to $`m=0`$ will be well-defined through its Laplace transform representation. For example, we could take $`p(n)=p^{1n}`$ for $`n1`$. This raises the possibility of choosing some suitable set of weights for which the integer flow problem, at least in $`1+1`$ dimensions, is integrable, for example by Bethe ansatz methods. Unfortunately our results in this direction are, so far, negative. In the case of bond percolation on a diagonal square lattice let $`Z(x_1,x_2,\mathrm{},x_m;t)`$ be the partition function under the constraint that the walkers arrive at $`\{x_1,x_2,\mathrm{},x_m\}`$ at time $`t`$, the physical region being $`\{x_1x_2\mathrm{}x_m\}`$. Turning the master equation for $`Z`$ in an eigenvalue problem  and writing the eigenfunction $`\psi _m(x_1,x_2,\mathrm{}x_m)`$ in the usual Bethe ansatz form, one gets for $`\psi _2(x_1,x_2)=A_{12}e^{i(x_1k_1+x_2k_2)}+A_{21}e^{i(x_1k_2+x_2k_1)}`$ the following condition on the amplitudes:

$$\frac{A_{21}}{A_{12}}=\frac{e^{i(k_1k_2)}ϵ\left(e^{i(k_1+k_2)}+e^{i(k_1+k_2)}\right)}{e^{i(k_1k_2)}ϵ\left(e^{i(k_1+k_2)}+e^{i(k_1+k_2)}\right)}$$

(the same as that which appears in the XXZ spin chain ) where $`ϵ=p(2)/p(1)^21`$. Requiring that the $`m`$-particle scattering should factorise into a product of these two-body $`S`$-matrices places constraints on the weights $`p(n)`$. In general these equations appear too difficult to solve, except in the weak interaction limit ($`ϵ1/2`$), where we find

$$2^n=2q(n)+\underset{s=1}{\overset{n1}{}}q(ns)q(s)(1\lambda s(ns))+O(\lambda ^2)$$

where $`q(s)=p(s)/(p(1))^s`$, $`\lambda =2ϵ1`$. This may be solved for successive $`q(n)`$, but it is easy to see by applying the above lemma that, when continued to $`n=0`$, it will always yield the value $`1`$, rather than $`p`$ as required. We conclude that the $`m=0`$ continuation of this integrable case does not correspond to DP. It is nevertheless interesting that integrable models of such interacting walkers can be formulated.

In 1+1 dimensions, our generalized friendly walker model maps naturally onto a model of a step of total height $`m`$ on a vicinal surface, by assigning integer height variables $`h(R)`$ to the sites $`R`$ of the dual lattice, such that $`h=0`$ for $`x\mathrm{}`$, $`h=m`$ for $`x+\mathrm{}`$, and $`h`$ increases by unity every time the path of a walker is crossed. The weights for neighboring dual sites $`R`$ and $`R^{}`$ are $`p(h(R^{})h(R))`$. This is slightly different from, and simpler than, the chiral Potts model studied in .

A similar correspondence between percolation and interacting random walks is valid also for the isotropic case. The pair connectedness $`G(r,r^{})`$ may be represented by a sum of graphs $`𝒢`$, just as in DP . Each graph consists of a union of oriented paths from $`r`$ to $`r^{}`$, As before, each bond is counted with weight $`p`$ and each loop carries a factor $`(1)`$. Note that graphs which contain a closed loop of oriented bonds are excluded. Such contributions cannot occur in DP because of the time-ordering. The correspondence with integer flows or friendly walkers follows as before. The latter picture is particularly simple. $`m`$ walkers begin at $`r`$ and end at $`r^{}`$. When two or more walkers occupy the same bond, they must flow parallel to each other. Since they cannot form closed loops, they are self-avoiding. Moreover, walkers other than those which begin and end at $`r`$ and $`r^{}`$, which could also form closed loops, are not allowed. Each occupied bond has weight $`p(n)`$ as before, and the separate configurations are counted using Bose statistics. $`G(r,r^{})`$ is then given by the continuation to $`m=0`$ of the partition function. We conclude that ordinary percolation is equivalent to the continuation to $`m=0`$ of a problem of $`m`$ oriented self-avoiding walks, with infinite repulsive interactions between anti-parallel segments on the same bond, but attractive parallel interactions. In two dimensions, this is again dual to an interesting height model, in which neighboring heights satisfy $`|h(R^{})h(R)|m`$, but local maxima or minima of $`h(R)`$ are excluded. For example, the order parameter of percolation is given by the continuation to $`m=0`$ of the partition function for a screw dislocation of strength $`m`$ in this model.

To summarize, we have shown that the DP problem is simply related to the integer flow problem, or equivalently that of $`m`$ bosonic ‘friendly’ walkers, when suitably continued to $`m=0`$. This holds on an arbitrary directed lattice in any number of dimensions, and with rather general weights. It is to be hoped that this correspondence might provide a new avenue of attack on the unsolved problem of directed percolation.

The authors acknowledge useful discussions with F. Essler and A. J. Guttmann, and thank T. Tsuchiya and M. Katori for sending a copy of their paper prior to publication. This research was supported in part by the Engineering and Physical Sciences Research Council under Grant GR/J78327.