text:
# Optimal Constructions of Hybrid AlgorithmsA preliminary version of this work appeared in Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 372–381, 1994. The first author was supported in part by NSF Grant CCR-9101385. The other three authors were supported in part by AFOSR Contract F49620-92-J-0125, DARPA Contract N00014-91-J-1698, and DARPA Contract N00014-92-J-1799. This work was performed while the third and the fourth authors were with Department of Mathematics and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA 02139.

## 1 Introduction

We study on-line strategies for solving problems with hybrid algorithms. There is a problem $`Q`$ and $`w`$ basic algorithms for solving $`Q`$. For some $`\lambda w`$, we have a computer with $`\lambda `$ disjoint memory areas, each of which can be used to run a basic algorithm and store its intermediate results. In the worst case, only one basic algorithm can solve $`Q`$ in finite time, and all the other basic algorithms run forever without solving $`Q`$. To solve $`Q`$ with a hybrid algorithm constructed from the basic algorithms, we run a basic algorithm for some time, then switch to another, and continue this process until $`Q`$ is solved. The goal is to solve $`Q`$ in the least amount of time.

This optimization problem can be conveniently formulated as one of exploring an unknown environment with multiple robots . At an origin, there are $`w`$ paths leading off into unknown territories. On one of the paths, there is a goal at an unknown distance $`n`$ from the origin, and none of the other paths has a goal. Initially, there are $`\lambda `$ robots standing at the origin. The robots can move back and forth on the paths to search for the goal. The objective is to minimize the total distance traveled by all the robots before the goal is found.

We use the notion of a competitive ratio, introduced by Sleator and Tarjan , to measure the efficiency of an exploration algorithm $`𝒜`$. Let cost($`𝒜`$) be the (worst-case or expected) total distance traveled by all the robots using $`𝒜`$. Given a constant $`c`$, we say that $`𝒜`$ has a competitive ratio $`c`$ if $`\text{cost}(𝒜)cn+o(n)`$.

An extreme case where there is only one robot, i.e., $`\lambda =1`$, was studied by many researchers. In particular, Baeza-Yates, Culberson and Rawlins  presented an optimal deterministic algorithm. Kao, Reif and Tate  reported a randomized algorithm, proved its optimality for $`w=2`$, and conjectured its optimality for all $`w>2`$. In these two algorithms, the single robot searches the $`w`$ paths in a cyclic fashion, and the returning positions on the paths form a geometric sequence. (A returning position on a path refers to a point where the robot starts moving towards the origin after advancing away from it.)

Another extreme case where the number of robots equals the number of paths, i.e., $`\lambda =w`$, was studied by Azar, Broder and Manasse , who showed that the smallest competitive ratios are $`w`$ for both deterministic and randomized algorithms. This ratio $`w`$ can be achieved by the simple algorithm in which each robot explores a single path and keeps moving forward until the goal is found.

The general case $`1<\lambda <w`$ has not been well understood, and its difficulty is twofold. Since $`\lambda >1`$, an exploration algorithm must coordinate its robots in order to achieve optimality. Moreover, since $`\lambda <w`$, some robots must move back and forth on two or more paths, and their returning positions on those paths are crucial for optimality. Our main results are that for all values of $`\lambda `$ and $`w`$, we construct

* a deterministic algorithm with the smallest possible competitive ratio, and
* an efficient randomized algorithm that is provably optimal for $`\lambda =1`$.

Our deterministic algorithm resolves an open question of Baeza-Yates et al.  on exploration using multiple robots. The optimality proof for our randomized algorithm with $`\lambda =1`$ settles the conjecture of Kao et al.  in the affirmative. Our results also imply that randomization can help reduce the competitive ratios if and only if $`\lambda <w`$.

We discuss our deterministic exploration algorithm in §2 and the randomized algorithm in §3. The paper concludes with some directions for future research in §4.

Throughout the paper, we label the $`w`$ paths by $`0,1,\mathrm{},w1`$ and the $`\lambda `$ robots by $`1,2,\mathrm{}\lambda `$.

## 2 An optimal deterministic exploration algorithm

Let $`D(w,\lambda )`$ denote the smallest competitive ratio for all deterministic exploration algorithms. The main result of this section is the next theorem.

###### Theorem 2.1

$`D(w,\lambda )=\lambda +2\frac{\left(w\lambda +1\right)^{w\lambda +1}}{\left(w\lambda \right)^{w\lambda }}.`$

Baeza-Yates et al.  studied the case $`\lambda =1`$, and their results can be restated as

$`D(w,1)=1+2{\displaystyle \frac{w^w}{\left(w1\right)^{w1}}}.`$ (1)
Theorem 2.1 generalizes (1) and answers the open question in  on optimal exploration using multiple robots. To prove Theorem 2.1, we describe our deterministic algorithm in §2.1 and give a lower bound proof in §2.2.

### 2.1 A deterministic exploration algorithm

We first review the exploration algorithm for $`\lambda =1`$ given by Baeza-Yates et al. . This algorithm, referred to as $`𝒟(w,1)`$, is used as a subroutine in our algorithm for general $`\lambda `$. Let

$$f(w,i)=\{\begin{array}{cc}\left(\frac{w}{w1}\right)^i& \text{for}i0,\hfill \\ 0& \text{for}i<0.\hfill \end{array}$$

In algorithm $`𝒟(w,1)`$, the single robot searches the $`w`$ paths in a fixed cyclic order. The search proceeds in $`stages`$, starting from stage 0. In stage $`i`$, the robot searches path $`imodw`$ until position $`f(w,i)`$ and moves back to the origin if the goal is not found by then. If the goal is at position $`f(w,i)+1`$, then the robot finds it in stage $`i+w`$, traveling a total distance of $`f(w,i)+1+2_{j=0}^{i+w1}f(w,j)`$. Baeza-Yates et al. showed that the smallest competitive ratio of $`𝒟(w,1)`$ is

$`\overline{lim}_i\mathrm{}{\displaystyle \frac{f(w,i)+1+2_{j=0}^{i+w1}f(w,j)}{f(w,i)+1}}1+2{\displaystyle \frac{w^w}{\left(w1\right)^{w1}}}.`$ (2)
In our algorithm for general $`\lambda `$, for each $`k<\lambda `$, the $`k`$-th robot only searches path $`k`$. These $`\lambda 1`$ robots simply advance on their own paths and never move towards the origin. Let $`w^{}=w\lambda +1`$. The $`\lambda `$-th robot explores the remaining $`w^{}`$ paths using $`𝒟(w^{},1)`$. The algorithm proceeds in rounds until the goal is found. In the $`i`$-th round, the robots move as follows:

* The $`\lambda `$-th robot chooses some path $`p`$ according to $`𝒟(w^{},1)`$ and searches it from the origin to position $`f(w^{},iw^{})`$.
* All the robots then move in parallel from position $`f(w^{},iw^{})`$ to position $`f(w^{},i+1w^{})`$ on the paths where they stand.
* The $`\lambda `$-th robot continues to search path $`p`$ from position $`f(w^{},i+1w^{})`$ to position $`f(w^{},i)`$ and then moves back to the origin.

We next analyze the above algorithm. If the goal is at position $`f(w^{},iw^{})+1`$ on some path, it is found in round $`i`$. By the time the goal is found, the first $`\lambda 1`$ robots have each traveled a distance of $`f(w^{},iw^{})+1`$, and the $`\lambda `$-th robot a distance of $`f(w^{},iw^{})+1+2_{j=0}^{i1}f(w^{},j)`$. Hence, the smallest competitive ratio of the above exploration algorithm is

$$\overline{lim}_i\mathrm{}\frac{\lambda \left(f(w^{},iw^{})+1\right)+2_{j=0}^{i1}f(w^{},j)}{f(w^{},iw^{})+1}.$$

By (2), the above formula is upper bounded by

$$\lambda +2\frac{w_{}^{}{}_{}{}^{w^{}}}{\left(w^{}1\right)^{w^{}1}}=\lambda +2\frac{\left(w\lambda +1\right)^{w\lambda +1}}{\left(w\lambda \right)^{w\lambda }},$$

which equals the competitive ratio stated in Theorem 2.1.

### 2.2 A matching lower bound

Here, we prove that our deterministic algorithm in §2.1 is optimal by deriving a matching lower bound on the smallest competitive ratio $`r_𝒜`$ of any arbitrary deterministic exploration algorithm $`𝒜(w,\lambda )`$ with $`w`$ paths and $`\lambda `$ robots. Let $`t_0`$ to be the time when $`𝒜(w,\lambda )`$ commences. For $`i>0`$, $`t_i`$ denotes the $`i`$-th time when a robot of $`𝒜(w,\lambda )`$ starts moving towards the origin on some path. $`𝒜(w,\lambda )`$ can be partitioned into phases where phase $`i`$ starts at $`t_{i1}`$ and ends at $`t_i`$. The notion of a phase differs from that of a round in §2.1.

###### Lemma 2.2

Given $`𝒜(w,\lambda )`$, there is a deterministic exploration algorithm $`𝒜^{}(w,\lambda )`$ such that $`r_𝒜^{}r_𝒜`$ and $`𝒜^{}(w,\lambda )`$ satisfies the following three properties:

* No two robots search the same path in the same phase.
* No robot moves towards the origin if some robot stays at the origin.
* As soon as a robot starts moving towards the origin on some path, all the other robots stop moving until that robot moves back to the origin and then advances on another path to a previously unsearched location.

Proof.  Straightforward.

If $`\lambda =1`$, i.e., there is only one robot, then $`𝒜(w,1)`$ can be characterized by a sequence $`\{(h_i,a_i),i1\}`$ where $`a_i`$ is the index of the path where the robot starts moving towards the origin in phase $`i`$, and $`h_i`$ is the distance that the robot searches on path $`a_i`$ in phase $`i`$. By simple calculation, the ratio $`r_𝒜`$ of $`𝒜(w,1)`$ equals

$`1+2\overline{lim}_i\mathrm{}\left({\displaystyle \frac{h_1+\mathrm{}+h_{i^{}1}}{h_i}}\right),`$ (3)
where $`i^{}`$ is the smallest index such that $`i^{}>i`$ and $`a_i^{}=a_i`$. Motivated by this finding, for any given $`\{(h_i,a_i),i1\}`$, we define the corresponding ratio sequence $`\{H_i,i1\}`$ by

$`H_i={\displaystyle \frac{h_1+\mathrm{}+h_{i^{}1}}{h_i}}`$ (4)
where $`i^{}`$ is the smallest index with $`i^{}>i`$ and $`a_i^{}=a_i`$. Using $`H_i`$, (3) can be written as

$$1+2\overline{lim}_i\mathrm{}H_i.$$

A sequence $`\{(h_i,a_i),i1\}`$ is a $`w`$-sequence if $`h_i>0`$ and $`a_i`$ is an integer for all $`i`$ as well as $`|\{ia_i=j\}|=\mathrm{}`$ for at least $`w`$ integers $`j`$. A $`w`$-sequence $`\{(h_i,a_i),i1\}`$ is a cyclic sequence if $`a_i=imodw`$. Since the integers $`a_i`$ are uniquely specified in a cyclic sequence, we represent a cyclic sequence by $`\{s_i,i1\}`$. The corresponding ratio sequence, denoted by $`\{S_i,i1\}`$, is thus defined by

$`S_i={\displaystyle \frac{s_1+\mathrm{}+s_{i+w1}}{s_i}}.`$ (5)
###### Fact 1

$`(`$see $`)`$ For every cyclic $`w`$-sequence, $`\overline{lim}_i\mathrm{}S_i\frac{w^w}{\left(w1\right)^{w1}}.`$

###### Lemma 2.3

For each $`w`$-sequence $`\{(h_i,a_i),i1\}`$, there exists a cyclic $`w`$-sequence $`\{s_i,i1\}`$ such that $`\overline{lim}_i\mathrm{}H_i\overline{lim}_i\mathrm{}S_i`$.

Proof.  See Appendix A.

Intuitively, Lemma 2.3 shows that we can modify a deterministic exploration algorithm to search the paths in a cyclic order without increasing its competitive ratio.

###### Lemma 2.4

If $`𝒜(w,\lambda )`$ has a finite competitive ratio and satisfies the properties of Lemma 2.2, then there exists a $`\left(w\lambda +1\right)`$-sequence $`\{(h_i,a_i),i1\}`$ such that

$$r_𝒜\lambda +2\overline{lim}_i\mathrm{}H_i,$$

where $`\{H_i,i1\}`$ is as defined in (4).

Proof.  First, we inductively define the sequence $`\{(h_i,a_i),i1\}`$ and a sequence of $`w`$-dimensional vectors $`\pi _i=(\pi _i(0),\mathrm{},\pi _i(w1))`$. Then, we prove the inequality claimed in the lemma.

We first define $`(h_1,a_1)`$ and $`\pi _1`$ by looking at the first phase of $`𝒜(w,\lambda )`$. Assume that at time $`t_1`$, a robot starts moving towards the origin on path $`j`$. Let $`h_1`$ be the distance that the robot has searched on path $`j`$. Define

$$\pi _1=(0,1,2,\mathrm{},w1)\text{and}a_1=\pi _1(j).$$

Once $`\pi _{i1}`$ is defined, we define $`(h_i,a_i)`$ and $`\pi _i`$ by looking at phase $`i`$ of $`𝒜(w,\lambda )`$. Recall that phase $`i`$ starts at time $`t_{i1}`$ and ends at time $`t_i`$. Assume that path $`l`$ is the unique path that is not searched in phase $`i1`$ but is searched in phase $`i`$. Also assume that at time $`t_i`$, a robot starts moving towards the origin on path $`k`$. Let $`h_i`$ be the distance that the robot has searched on path $`k`$. For $`j=0,\mathrm{},w1`$, let

$$\pi _i(j)=\{\begin{array}{cc}\pi _{i1}(l)\hfill & \text{if}j=k,\hfill \\ \pi _{i1}(k)\hfill & \text{if}j=l,\hfill \\ \pi _{i1}(j)\hfill & \text{if}jk\text{and}jl;\hfill \end{array}$$

i.e., we switch the $`k`$-th entry and the $`l`$-th entry of $`\pi _{i1}`$ to obtain $`\pi _i`$. Let $`a_i=\pi _i(k)`$.

Since $`𝒜(w,\lambda )`$ has a finite competitive ratio, $`\{(h_i,a_i),i1\}`$ is an infinite sequence. For every $`i1`$, $`t_i`$ is the time when a robot starts moving towards the origin on some path $`p`$. Let $`i^{}>i`$ be the index such that phase $`i^{}`$ is the first phase that path $`p`$ is searched again after $`t_i`$. Such $`i^{}`$ exists and is finite.

###### Claim 2.1

For all $`i1`$, $`a_i^{}=a_i`$ and $`a_ja_i`$ for $`j=i+1,\mathrm{},i^{}1`$.

To prove this claim, assume that $`a_i=\pi _i(k)`$, i.e., a robot starts moving towards the origin on path $`k`$ immediately after $`t_i`$. In phase $`i+1`$, that robot moves back on path $`k`$ to the origin and then searches another path $`l`$ with $`lk`$. Then, some robot starts moving towards the origin on path $`k_1`$ with $`k_1k`$ right after $`t_{i+1}`$. Since $`kl`$ and $`kk_1`$, by the definition of $`\pi _{i+1}`$,

$$\pi _{i+1}(k)=\pi _i(k).$$

By the choice of $`i^{}`$, path $`k`$ must be idle from $`t_{i+1}`$ to $`t_{i^{}1}`$. Hence,

$`\pi _j(k)=\pi _{j1}(k)=\mathrm{}=\pi _{i+1}(k)=\pi _i(k)=a_i.`$ (6)
Moreover, $`a_j\pi _j(k)`$. Thus, from (6),

$`a_ja_i\text{for}j=i+1,\mathrm{},i^{}1.`$ (7)
By the choice of $`i^{}`$, path $`k`$ is reused in phase $`i^{}`$. Assume that a robot searches path $`k_2`$ immediately after $`t_i^{}`$. By the inductive procedure for defining $`\pi _i^{}`$ and $`a_i^{}`$,

$`\pi _i^{}(k_2)=\pi _{i^{}1}(k)\text{and}a_i^{}=\pi _i^{}(k_2).`$ (8)
Combining (6) and (8), we have $`a_i^{}=a_i`$. This and (7) conclude the proof of Claim 2.1.

###### Claim 2.2

$`\{(h_i,a_i),i1\}`$ is a $`\left(w\lambda +1\right)`$-sequence.

To prove this claim, the only nontrivial property of the sequence that we need to verify is that there are at least $`\left(w\lambda +1\right)`$ integers $`j`$ such that $`|\{ia_i=j\}|=+\mathrm{}`$. By Claim 2.1, it suffices to prove that there exist $`\left(w\lambda +1\right)`$ integers $`j`$ such that

$$a_i=j\text{for some}i.$$
(9)
Without loss of generality, we label the $`w`$ paths in such a way that

* the label of the path where a robot starts moving towards the origin immediately after $`t_1`$ is 0;
* paths $`1,2,\mathrm{},w\lambda `$ are not searched before $`t_1`$;
* $`i_1<i_2<\mathrm{}<i_{w\lambda }`$ where $`i_j`$ is the first phase in which path $`j`$ is searched.

By the assumption on $`a_0`$ and the definition of $`a_1`$,

$$a_1=0.$$
(10)
For $`j=1,\mathrm{},w\lambda `$, let $`j^{}`$ be the label of the path where a robot starts moving towards the origin immediately after $`t_{i_j}`$. By the definitions of $`\{\pi _i,i1\}`$ and $`\{(h_i,a_i),i1\}`$, $`\pi _{i_j}(j^{})=\pi _{i_j1}(j)=\mathrm{}=\pi _1(j)=j.`$ Therefore,

$$a_{i_j}=\pi _{i_j}(j^{})=j\text{for}1jw\lambda .$$

By this and (10), at least $`w\lambda +1`$ integers $`j`$ satisfy (9), finishing the proof of Claim 2.2.

Continuing the proof of Lemma 2.4, for each $`i1`$, let $`p`$ be the path where a robot starts moving towards the origin right after $`t_i`$. Let $`T`$ be the first time when path $`p`$ is searched for exactly distance $`h_i`$ in phase $`i^{}`$. By the properties stated in Lemma 2.2, the $`\lambda `$ robots stand at different paths at time $`T`$. Let $`d_1,d_2,\mathrm{},d_{\lambda 1}`$ be the distances that the robots except the one on path $`p`$ are from the origin at time $`T`$. Let $`d_j=\mathrm{min}\{d_1,d_2,\mathrm{},d_{\lambda 1}\}`$. There are two cases.

Case 1: $`d_jh_i`$. If the goal is on path $`p`$ at distance $`h_i+1`$, then when $`𝒜(w,\lambda )`$ finds the goal, its performance ratio is at least

$`{\displaystyle \frac{d_1+d_2+\mathrm{}+d_{\lambda 1}}{h_i+1}}+{\displaystyle \frac{2\left(h_1+\mathrm{}+h_{i^{}1}\right)+h_i+1}{h_i+1}}`$ (11)
$``$ $`{\displaystyle \frac{h_i}{h_i+1}}\left(\lambda +{\displaystyle \frac{2\left(h_1+\mathrm{}+h_{i^{}1}\right)}{h_i}}\right).`$
Case 2: $`d_j<h_i`$. Let $`p^{}`$ be a path that has been searched up to distance $`d_j`$ at time $`T`$. If the goal is on path $`p^{}`$ at distance $`d_j+1`$, then when $`𝒜(w,\lambda )`$ finds the goal, its performance ratio is at least

$`{\displaystyle \frac{d_1+d_2+\mathrm{}+d_j+1+\mathrm{}+d_{\lambda 1}}{d_j+1}}+{\displaystyle \frac{2\left(h_1+\mathrm{}+h_{i^{}1}\right)+h_i}{d_j+1}}`$ (12)
$``$ $`{\displaystyle \frac{d_j+1}{d_j}}\left(\lambda +{\displaystyle \frac{2\left(h_1+\mathrm{}+h_{i^{}1}\right)}{h_i}}\right).`$
Since $`𝒜(w,\lambda )`$ has a finite competitive ratio, $`lim_i\mathrm{}h_i=lim_j\mathrm{}d_j=+\mathrm{}.`$ Therefore, by (11) and (12),

$$r_𝒜\overline{lim}_i\mathrm{}\left(\lambda +\frac{2\left(h_1+\mathrm{}+h_{i^{}1}\right)}{h_i}\right)=\lambda +2\overline{lim}_i\mathrm{}H_i.$$

This and Claims 2.1 and 2.2 conclude the proof of Lemma 2.4

Fact 1 and Lemmas 2.2, 2.3 and 2.4 give a lower bound proof for Theorem 2.1.

## 3 A randomized exploration algorithm

We give our randomized exploration algorithm for general $`\lambda `$ in §3.1 and prove its optimality for $`\lambda =1`$ in §3.2.

### 3.1 A randomized exploration algorithm for general $`\lambda `$

We first review the randomized search algorithm of Kao et al.  for $`\lambda =1`$, which we refer to as $`(w,1)`$. Choose $`r_w>1`$ such that

$$\frac{r_w^w1}{\left(r_w1\right)\mathrm{ln}r_w}=\underset{r>1}{\mathrm{min}}\frac{r^w1}{\left(r1\right)\mathrm{ln}r}.$$

Such $`r_w`$ exists and is unique . $`(w,1)`$ proceeds as follows:

1. $`\sigma `$ a random permutation of $`\{0,\mathrm{},w1\}`$;
2. $`ϵ`$ a random real number uniformly chosen from $`[0,1)`$;
3. $`dr_w^ϵ`$;
4. $`i1`$;
5. repeat
explore path $`\sigma \left(i\right)`$ up to distance $`d`$;
if goal not found then return to origin;
$`ddr_w`$;
$`i\left(i+1\right)modw`$;
6. until the goal is found.

Let $`R(w,\lambda )`$ denote the smallest competitive ratio for randomized exploration algorithms for $`w`$ paths and $`\lambda `$ robots. Let

$$\overline{R}(w)=1+\frac{2}{w}\frac{r_w^w1}{\left(r_w1\right)\mathrm{ln}r_w}.$$

###### Fact 2

$`(`$see $`)`$ $`R(w,1)\overline{R}(w).`$

We now construct our randomized exploration algorithm for general $`\lambda `$ using $`(w,1)`$ as a subroutine. First, we pick a random permutation $`\sigma `$ of $`\{0,1,\mathrm{},w1\}`$. For the first $`\lambda 1`$ robots, robot $`i`$ searches only path $`\sigma \left(i\right)`$. These robots search their own paths at the same constant speed. The $`\lambda `$-th robot searches the remaining $`w\lambda +1`$ paths using $`(w\lambda +1,1)`$ also at a constant speed. The speeds are coordinated by a parameter $`v`$ such that at any given time, the total distance traveled by the $`\lambda `$-th robot is $`v`$ times the distance traveled by each of the first $`\lambda 1`$ robots. By choosing an appropriate $`v`$, we can prove the next theorem.

###### Theorem 3.1

$`R(w,\lambda )\frac{1}{w}\left(\left(\lambda 1\right)+\sqrt{\left(w\lambda +1\right)\overline{R}(w\lambda +1)}\right)^2`$.

Proof.  The smallest competitive ratio of our exploration algorithm is at most

$$\frac{\lambda 1}{w}\left(\left(\lambda 1\right)+v\right)+\frac{w\lambda +1}{w}\left(\frac{\lambda 1}{v}+1\right)\overline{R}(w\lambda +1).$$

At $`v=\sqrt{\left(w\lambda +1\right)\overline{R}(w\lambda +1)}`$, this expression assumes its minimum

$$\frac{1}{w}\left(\left(\lambda 1\right)+\sqrt{\left(w\lambda +1\right)\overline{R}(w\lambda +1)}\right)^2.$$

Combining Theorem 2.1 and 3.1, we can prove the following corollary.

###### Corollary 3.2

If $`\lambda <w`$, then the smallest competitive ratio of randomized exploration algorithms is always smaller than that of deterministic ones.

Proof.  By Theorems 2.1 and 3.1, we only need to prove

$`{\displaystyle \frac{1}{w}}\left(\left(\lambda 1\right)+\sqrt{\left(w\lambda +1\right)\overline{R}(w\lambda +1)}\right)^2<\lambda +2{\displaystyle \frac{\left(w\lambda +1\right)^{w\lambda +1}}{\left(w\lambda \right)^{w\lambda }}}.`$ (13)
Let $`a=\overline{R}(w\lambda +1)`$, by Fact 2, which is a competitive ratio of a randomized exploration algorithm with one robot and $`w\lambda +1`$ paths. Let $`b=1+2\frac{\left(w\lambda +1\right)^{w\lambda +1}}{\left(w\lambda \right)^{w\lambda }}`$, by Theorem 2.1, which is the smallest competitive ratio of deterministic algorithms also for one robot and $`w\lambda +1`$ paths. Since $`a<b`$ , to prove (13), it is suffice to show that

$`{\displaystyle \frac{1}{w}}\left(\left(\lambda 1\right)+\sqrt{\left(w\lambda +1\right)a}\right)^2\lambda 1+a,`$
which is equivalent to $`\left(a\sqrt{w\lambda +1}\right)^20`$.

### 3.2 A matching lower bound for $`\lambda =1`$

The next theorem shows that our randomized algorithm is optimal for $`\lambda =1`$.

###### Theorem 3.3

$`R(w,1)\overline{R}(w).`$

The proof of this theorem uses a strengthened version of Fact 3 below. Let $`\stackrel{}{s}=\{s_i,i0\}`$ denote an infinite sequence of positive numbers. Let

$$S_w=\{\{s_i,i0\}|\underset{i\mathrm{}}{lim}s_i=\mathrm{},s_0=1,\text{and for all}i0,s_{i+w}>s_i\}.$$

For any $`ϵ>0`$ and $`\stackrel{}{s}=\{s_i,i0\}S_w`$, let

$$G_w(ϵ,\stackrel{}{s})=ϵ\underset{i=0}{\overset{\mathrm{}}{}}\frac{s_i+\mathrm{}+s_{i+w1}}{s_i^{1+ϵ}}.$$

An exploration algorithm with one robot is called cyclic if it searches the paths one after another in a cyclic order.

###### Fact 3

$`(`$see $`)`$ The smallest competitive ratio of any cyclic randomized exploration algorithm is at least

$$\underset{ϵ>0}{sup}\underset{\stackrel{}{s}S_w}{inf}\{1+\frac{2}{w}G_w(ϵ,\stackrel{}{s})\}.$$

Note that if $`w=2`$, i.e., there are only two paths, then every exploration algorithm is cyclic. This is not true for $`w3`$. Ma and Yin  strengthened Fact 3 by removing the cyclic assumption about exploration algorithms.

###### Fact 4

$`(`$see $`)`$ The lower bound stated in Fact 3 also holds for any arbitrary randomized exploration algorithms that may or may not be cyclic.

Proof.  By Yao’s formulation of von Neumann’s minimax principle , it suffice to lower bound the competitive ratios of all deterministic algorithms against a chosen probability distribution. The proof idea is to show that an optimal algorithm against the distribution used by Kao et al.  for Fact 3 can be modified to be cyclic.

By Fact 4, to prove Theorem 3.3, we only need to prove the next theorem. Let

$$C_w=\frac{r_w^w1}{\left(r_w1\right)\mathrm{ln}r_w}.$$

###### Theorem 3.4

$`sup_{ϵ>0}inf_{\stackrel{}{s}S_w}G_w(ϵ,\stackrel{}{s})C_w`$.

The proof of Theorem 3.4 is divided into three parts. In §3.2.1, we lower bound the infinite sum $`G_w(ϵ,\stackrel{}{s})`$ by the finite sum

$$H(k,\stackrel{}{s}(ϵ))=\frac{ϵ+_{i=0}^{k1}\frac{s_i(ϵ)+\mathrm{}+s_{i+w1}(ϵ)}{\left(s_i(ϵ)\right)^{1+ϵ}}}{\mathrm{ln}s_k(ϵ)}.$$

In §3.2.2, we lower bound this finite sum by $`C_w`$. Finally in §3.2.3, we complete the proof of Theorem 3.4.

#### 3.2.1 Lower bounding $`G_w(ϵ,\stackrel{}{s})`$ by $`H(k,\stackrel{}{s}(ϵ))`$

###### Lemma 3.5

For all $`ϵ>0`$, there exists $`\{s_i(ϵ),i0\}S_w`$ such that for all $`k`$ with $`s_k(ϵ)>1`$,

$$\underset{\stackrel{}{s}S_w}{inf}G_w(ϵ,\stackrel{}{s})H(k,\stackrel{}{s}(ϵ)).$$

Proof.  By the definition of infimum, for all $`ϵ>0`$, there exists $`\stackrel{}{s}(ϵ)=\{s_i(ϵ),i0\}S_w`$ such that

$`\underset{\stackrel{}{s}S_w}{inf}G_w(ϵ,\stackrel{}{s})+ϵ^2`$
$``$ $`G_w(ϵ,\stackrel{}{s}(ϵ))`$
$`=`$ $`ϵ{\displaystyle \underset{i=0}{\overset{k1}{}}}{\displaystyle \frac{s_i(ϵ)+\mathrm{}+s_{i+w1}(ϵ)}{\left(s_i(ϵ)\right)^{1+ϵ}}}+\left(s_k(ϵ)\right)^ϵ\left(ϵ{\displaystyle \underset{i=k}{\overset{\mathrm{}}{}}}{\displaystyle \frac{\frac{s_i(ϵ)}{s_k(ϵ)}+\mathrm{}+\frac{s_{i+w1}(ϵ)}{s_k(ϵ)}}{\left(\frac{s_i(ϵ)}{s_k(ϵ)}\right)^{1+ϵ}}}\right).`$
Since $`\stackrel{}{s^{}}(ϵ)=\{s_i^{}(ϵ)=\frac{s_{k+i}(ϵ)}{s_k(ϵ)},i0\}`$ is in $`S_w`$,

$`\underset{\stackrel{}{s}S_w}{inf}G_w(ϵ,\stackrel{}{s})+ϵ^2`$ $`=`$ $`\left(ϵ{\displaystyle \underset{i=0}{\overset{k1}{}}}{\displaystyle \frac{s_i(ϵ)+\mathrm{}+s_{i+w1(ϵ)}}{\left(s_i(ϵ)\right)^{1+ϵ}}}\right)+\left(s_k(ϵ)\right)^ϵG_w(ϵ,\stackrel{}{s^{}})`$
$``$ $`\left(ϵ{\displaystyle \underset{i=0}{\overset{k1}{}}}{\displaystyle \frac{s_i(ϵ)+\mathrm{}+s_{i+w1}(ϵ)}{\left(s_i(ϵ)\right)^{1+ϵ}}}\right)+\left(s_k(ϵ)\right)^ϵ\underset{\stackrel{}{s}S_w}{inf}G_w(ϵ,\stackrel{}{s}).`$
Since $`s_k(ϵ)>1`$ and $`\frac{ϵ}{1x^ϵ}\frac{1}{\mathrm{ln}x}`$ for all $`x>1`$,

$`\underset{\stackrel{}{s}S_w}{inf}G_w(ϵ,\stackrel{}{s})`$ $``$ $`{\displaystyle \frac{ϵ}{1\left(s_k(ϵ)\right)^ϵ}}\left(ϵ+{\displaystyle \underset{i=0}{\overset{k1}{}}}{\displaystyle \frac{s_i(ϵ)+\mathrm{}+s_{i+w1}(ϵ)}{\left(s_k(ϵ)\right)^{1+ϵ}}}\right)`$
$``$ $`{\displaystyle \frac{1}{\mathrm{ln}s_k(ϵ)}}\left(ϵ+{\displaystyle \underset{i=0}{\overset{k1}{}}}{\displaystyle \frac{s_i(ϵ)+\mathrm{}+s_{i+w1}(ϵ)}{\left(s_k(ϵ)\right)^{1+ϵ}}}\right).`$
###### Lemma 3.6

There exist a strictly increasing integer sequence $`\{p_i,i0\}`$ and a sequence $`\stackrel{}{s}(ϵ_n)`$ such that

$$\underset{n\mathrm{}}{lim}H(k_n,\stackrel{}{s}(ϵ_n))\text{exists and is finite}$$

and

$$\underset{ϵ>0}{sup}\underset{\stackrel{}{s}S_w}{inf}G_w(ϵ,\stackrel{}{s})\underset{n\mathrm{}}{lim}H(k_n,\stackrel{}{s}(ϵ_n)),$$

where $`ϵ_n=\frac{1}{p_n^2}`$, $`0<p_nk_np_n+w1,`$ and $`s_{k_n}(ϵ_n)=\mathrm{max}\{s_{p_n}(ϵ_n),\mathrm{},s_{p_n+w1}(ϵ_n)\}.`$

Proof.  This lemma follows from the fact that by Fact 4 and Lemma 3.5, $`H(k,\stackrel{}{s}(ϵ))`$ is bounded.

#### 3.2.2 Lower Bounding $`H(k,\stackrel{}{s}(ϵ))`$ by $`C_w`$

This is the most difficult part of the proof of Theorem 3.4 and requires six technical lemmas, namely, Lemmas 3.7 through 3.12. The proofs of these lemmas are given in Appendix B.

We first rewrite

$`H(k_n,\stackrel{}{s}(ϵ_n))`$ $`=`$ $`{\displaystyle \frac{1}{\mathrm{ln}s_k(ϵ_n)}}\left(ϵ_n+{\displaystyle \underset{i=0}{\overset{k_n1}{}}}{\displaystyle \frac{s_i(ϵ_n)+\mathrm{}+s_{i+w1}(ϵ_n)}{\left(s_i(ϵ_n)\right)^{1+ϵ_n}}}\right)`$
$`=`$ $`{\displaystyle \frac{1}{\mathrm{ln}s_k(ϵ_n)}}\left(ϵ_n+{\displaystyle \underset{j=0}{\overset{w1}{}}}{\displaystyle \underset{i=0}{\overset{k_n1}{}}}{\displaystyle \frac{s_{i+j}(ϵ_n)}{\left(s_i(ϵ_n)\right)^{1+ϵ_n}}}\right).`$
Hence, by Lemma 3.6, there is a constant $`C`$ such that

$$CH(k_n,\stackrel{}{s}(ϵ_n))\frac{ϵ_n+\underset{j=0}{\overset{w1}{}}L_n(j)}{\mathrm{ln}s_k(ϵ_n)},$$
(14)
where

$$L_n\left(0\right)=\underset{i=0}{\overset{k_n1}{}}\frac{1}{\left(s_i(ϵ_n)\right)^{ϵ_n}}$$

and

$$L_n(j)=\underset{i=0}{\overset{k_nj}{}}\frac{s_{i+j}(ϵ_n)}{\left(s_i(ϵ_n)\right)^{1+ϵ_n}}$$

for $`j=1,\mathrm{},w1`$. Note that $`s_{k_n}>1`$ implies $`\mathrm{ln}s_{k_n}>0`$.

To further lower bound $`H(k_n,\stackrel{}{s}(ϵ_n))`$, we first work on $`L_n(0)`$ to show that $`s_{k_n}(ϵ_n)\mathrm{}`$ as $`n\mathrm{}`$. Then, we work on $`L_n(1)`$ to show that $`s_n(ϵ_n)`$ grows somewhat smoothly at a rate exponential in $`n`$. Finally, we lower bound all $`L_n(j)`$.

The next lemma is frequently used in this section.

###### Lemma 3.7

For every positive integer $`m`$ and for all $`ϵ,x_0,\mathrm{},x_m>0`$,

$$\frac{x_1}{x_0^{1+ϵ}}+\frac{x_2}{x_1^{1+ϵ}}+\mathrm{}+\frac{x_m}{x_{m1}^{1+ϵ}}\frac{m}{\left(1+ϵ\right)^m}\left(\frac{x_m^{\left(\frac{1}{1+ϵ}\right)^m}}{x_0}\right)^{E_ϵ\left(m\right)}$$

where $`E_ϵ\left(m\right)=\frac{ϵ\left(1+ϵ\right)^m}{\left(1+ϵ\right)^m1}.`$

The next two lemmas give some properties of the sequence $`\{s_{k_n}(ϵ_n),k0\}`$.

###### Lemma 3.8

$`lim_n\mathrm{}s_{k_n}(ϵ_n)=\mathrm{}.`$

For all $`n`$, pick $`h_n\{k_nw+1,\mathrm{},k_n1\}`$ such that

$$s_{h_n}(ϵ_n)=\mathrm{min}\{s_{k_nw+1}(ϵ_n),\mathrm{},s_{k_n1}(ϵ_n)\}.$$

Since $`p_n\mathrm{}`$ as $`n\mathrm{}`$, we assume without loss of generality that $`k_nw+10`$. Since $`s_{k_n}(ϵ_n)>1`$, there exists a unique $`\nu _n`$ such that

$$s_{h_n}(ϵ_n)=\left(s_{k_n}(ϵ_n)\right)^{1\nu _n}.$$

By the choice of $`k_n`$ and the monotonicity of $`S_w`$, $`s_{k_n}(ϵ_n)s_{h_n}(ϵ_n)`$ and thus $`\nu _n0`$.

###### Lemma 3.9

$`lim_n\mathrm{}\nu _n=0`$ and for some finite $`\mathrm{\Delta }>1`$, $`lim_n\mathrm{}\left(s_{k_n}(ϵ_n)\right)^{\frac{1}{k_n}}=\mathrm{\Delta }.`$

The next lemma estimates $`L_n(0)`$ and $`L_n(1)`$.

###### Lemma 3.10

$`lim_n\mathrm{}\frac{L_n(0)}{\mathrm{ln}s_{k_n}(ϵ_n)}\frac{1}{\mathrm{ln}\mathrm{\Delta }}`$ and $`lim_n\mathrm{}\frac{L_n(1)}{\mathrm{ln}s_{k_n}(ϵ_n)}\frac{\mathrm{\Delta }}{\mathrm{ln}\mathrm{\Delta }}.`$

The next two lemmas estimate $`L_n\left(2\right),\mathrm{},L_n\left(w1\right).`$ For all integers $`n0`$, let $`b_n=ϵ_n+C\mathrm{ln}s_{k_n}(ϵ_n).`$ In light of Lemma 3.8, we assume $`\mathrm{ln}s_{k_n}(ϵ_n)1`$ and thus $`b_n1`$; otherwise we can replace $`\{p_n,n0\}`$ with a subsequence for which these bounds hold.

###### Lemma 3.11

For all $`n0`$ and $`i\{0,1,\mathrm{},w1\}`$, $`b_n^{\left(w1\right)\left(1+ϵ_n\right)^{w1}}s_i(ϵ_n).`$

###### Lemma 3.12

For $`j=2,\mathrm{},w1`$ and $`u=0,\mathrm{},j1`$, $`lim_n\mathrm{}L_n(j)\frac{\mathrm{\Delta }^j}{\mathrm{ln}\mathrm{\Delta }}.`$

#### 3.2.3 Proof of Theorem 3.4

From (14) and Lemmas 3.10 and 3.12, we have $`lim_n\mathrm{}H(k_n,\stackrel{}{s}(ϵ_n))\frac{1+\mathrm{\Delta }+\mathrm{}+\mathrm{\Delta }^{w1}}{\mathrm{ln}\mathrm{\Delta }}.`$ By the definition of $`r_w`$ and the fact $`\mathrm{\Delta }>1`$ from Lemma 3.9, $`\frac{1+\mathrm{\Delta }+\mathrm{}+\mathrm{\Delta }^{w1}}{\mathrm{ln}\mathrm{\Delta }}=\frac{\mathrm{\Delta }^w1}{\left(\mathrm{\Delta }1\right)\mathrm{ln}\mathrm{\Delta }}C_w.`$ Combining this with Lemma 3.6, we complete the proof of Theorem 3.4 and thus that of Theorem 3.3.

## 4 Future research directions

Our deterministic exploration algorithm is optimal for all $`\lambda `$, but our randomized algorithm is only shown to be optimal for $`\lambda =1`$. For general $`\lambda `$, it may be possible to obtain better or even optimal competitive ratios by holding $`\lambda 1`$ robots still while one robot moves towards the origin, as in our deterministic algorithm. This technique is not essential in our deterministic algorithm, but there is evidence that it may be useful in the randomized case. We further conjecture that there exists an optimal randomized algorithm in which one robot searches $`w\lambda +1`$ paths and each of the other robots searches only one of the remaining paths.

Our exploration algorithms minimize the total distance traveled by all the robots. It would be of interest to minimize the total parallel exploration time. We conjecture that the optimal competitive ratios of parallel time are achieved when the paths are partitioned as even as possible.

In the layered graph traversal problem , one robot searches for a certain goal in a graph. The robot can shortcut between paths without going through the origin, and while exploring one path, it can obtain free information about the other paths. An analog of our work would be to study how to search a layered graph with multiple robots.

## Acknowledgments

We thank Dan Kleitman for invaluable help with the cyclic assumption of exploration algorithms and thank Tom Leighton, Ron Rivest, Steve Tate, and Shang-Hua Teng for many useful discussions.

## Appendix A Proof of Lemma 2.3

The sequence $`\{(h_i,a_i),i1\}`$ characterizes a deterministic exploration algorithm $`𝒜(w,1)`$, and the smallest competitive ratio of this algorithm is $`1+2\overline{lim}_i\mathrm{}H_i`$. If $`𝒜(w,1)`$ does not have a finite competitive ratio, then Lemma 2.3 holds trivially. Thus, we assume that $`𝒜(w,1)`$ has a finite competitive ratio.

###### Claim A.1

$`lim_i\mathrm{}h_i=\mathrm{}`$.

Proof.  Assume for contradiction that the claim does not hold. Then there exist a constant $`M<\mathrm{}`$ and a subsequence $`\{h_{i_k},k1\}`$ of $`\{h_i,i1\}`$ such that $`h_{i_k}M`$ for all $`k`$. Therefore,

$`\overline{lim}_i\mathrm{}H_i`$ $``$ $`\overline{lim}_k\mathrm{}H_{i_k}`$
$`=`$ $`\overline{lim}_k\mathrm{}{\displaystyle \frac{h_1+\mathrm{}+h_{i_k^{}1}}{h_{i_k}}}`$
$``$ $`{\displaystyle \frac{1}{M}}\overline{lim}_k\mathrm{}\left(h_1+\mathrm{}+h_{i_k^{}1}\right),`$
which equals $`\mathrm{}`$ from the assumption that $`𝒜(w,1)`$ has a finite competitive ratio.

By Claim A.1, for any $`M<\mathrm{}`$, $`|\{h_ih_iM\}|`$ is finite. Hence, we can sort $`\{h_i,i1\}`$ into a sorted sequence $`\{s_i,i1\}`$. Observe that

$`s_1+\mathrm{}+s_ih_1+\mathrm{}+h_i,\text{for all }i1\text{.}`$ (15)
The sequence $`\{s_i,i1\}`$ is our desired cyclic $`w`$-sequence, and its corresponding ratio sequence $`\{S_i,i1\}`$ is uniquely defined as in (5). To prove $`\overline{lim}_i\mathrm{}H_i\overline{lim}_i\mathrm{}S_i`$, it suffices to show that for each $`j`$ large enough, there is a $`j^{}`$ such that

$`S_jH_j^{}\text{ and }j^{}\mathrm{}\text{ as }j\mathrm{}.`$ (16)
For any fixed $`j`$ that is sufficiently large, we consider two cases.

Case 1: There exists some $`tj+w1`$ such that $`h_ts_j`$. Since $`t^{}>t`$ is the smallest index with $`a_t^{}=a_t`$, $`t^{}1tj+w1`$. Hence, by (15),

$`S_j={\displaystyle \frac{s_1+\mathrm{}+s_{j+w1}}{s_j}}{\displaystyle \frac{h_1+\mathrm{}+h_{j+w1}}{s_j}}{\displaystyle \frac{h_1+\mathrm{}+h_{t^{}1}}{h_t}}=H_t.`$ (17)
Let $`j^{}=t`$. Then, (16) follows from (17) and the fact $`j^{}j`$.

Case 2: $`h_t>s_j`$ for all $`tj+w1`$. Since $`\{h_1,\mathrm{},h_{j+w2}\}`$ contains all $`h_t`$ with $`h_ts_j`$, $`\{h_1,\mathrm{},h_{j+w2}\}`$ contains $`\{s_1,\mathrm{}s_j\}`$ as a subset. Thus,

$`|\{h_th_t>s_j\text{and}1tj+w2\}|\left(j+w2\right)j=w2.`$ (18)
Since $`\{(h_i,a_i),i1\}`$ is a $`w`$-sequence, there are $`w`$ distinct integers $`v_1,v_2,\mathrm{},v_w`$, each appearing infinitely many times in $`\{a_i,i1\}`$. Since $`j`$ is sufficiently large, we can assume without loss of generality that each $`v_k`$ appears at least once in $`\{a_1,\mathrm{},a_j\}`$. For $`k`$ with $`1kw`$, let $`j(k)j+w2`$ be the largest index with $`a_{j(k)}=v_k`$. Among $`h_{j(1)},\mathrm{},h_{j\left(w\right)}`$, by (18), at least two, say, $`h_{j\left(k_1\right)}`$ and $`h_{j\left(k_2\right)}`$, are less than $`s_j`$. By the choices of $`j\left(k_1\right)`$ and $`j\left(k_2\right)`$, both $`j^{}\left(k_1\right)`$ and $`j^{}\left(k_2\right)`$ are at least $`j+w1`$. Without loss of generality, we assume $`j^{}\left(k_1\right)>j+w1`$. By (15),

$`S_j={\displaystyle \frac{s_1+\mathrm{}+s_{j+w1}}{s_j}}`$
$`{\displaystyle \frac{h_1+\mathrm{}+h_{j+w1}}{s_j}}{\displaystyle \frac{h_1+\mathrm{}+h_{j^{}\left(k_1\right)1}}{h_{l_1}}}=H_{j\left(k_1\right)}.`$
Now, let $`j^{}=j\left(k_1\right)`$. Since $`v_{k_1}`$ appears infinitely many times in $`\{a_i,i1\}`$, $`j\left(k_1\right)\mathrm{}`$ as $`j\mathrm{}`$. Now, (16) follows from (A).

Cases 1 and 2 together complete the proof of Lemma 2.3.

## Appendix B Proofs of Lemmas 3.7 through 3.12

### B.1 Proof of Lemma 3.7

$`{\displaystyle \frac{x_1}{x_0^{1+ϵ}}}+{\displaystyle \frac{x_2}{x_1^{1+ϵ}}}+\mathrm{}+{\displaystyle \frac{x_m}{x_{m1}^{1+ϵ}}}`$
$`>`$ $`{\displaystyle \frac{1}{1+ϵ}}{\displaystyle \frac{x_1}{x_0^{1+ϵ}}}+{\displaystyle \frac{1}{\left(1+ϵ\right)^2}}{\displaystyle \frac{x_2}{x_1^{1+ϵ}}}+\mathrm{}+{\displaystyle \frac{1}{\left(1+ϵ\right)^m}}{\displaystyle \frac{x_m}{x_{m1}^{1+ϵ}}}`$ $`\left(\text{because}1+ϵ>1\right)`$
$``$ $`{\displaystyle \frac{1}{E_ϵ\left(m\right)}}\left({\displaystyle \frac{x_m^{\left(\frac{1}{1+ϵ}\right)^m}}{x_0}}\right)^{E_ϵ\left(m\right)}`$ $`\left(\text{arithmetic mean}\text{geometric mean}\right)`$
$``$ $`{\displaystyle \frac{m}{\left(1+ϵ\right)^m}}\left({\displaystyle \frac{x_m^{\left(\frac{1}{1+ϵ}\right)^m}}{x_0}}\right)^{E_ϵ\left(m\right)}.`$ $`\left(\text{because}\left(1+ϵ\right)^m1+mϵ\right)`$
### B.2 Proof of Lemma 3.8

By the choice of $`k_n`$ and the monotonicity of $`S_w`$, we have $`s_{k_n}(ϵ_n)s_i(ϵ_n)`$ for all $`i=0,\mathrm{},k_n`$. Hence,

$$L_n(0)\frac{k_n}{\left(s_{k_n}(ϵ_n)\right)^{ϵ_n}}.$$
(20)
Then, the lemma follows from the facts that $`k_n\mathrm{}`$ and $`ϵ_n0`$ as $`n\mathrm{}`$ and that by (14) and (20)

$$C\frac{ϵ_n+\frac{k_n}{\left(s_{k_n}(ϵ_n)\right)^{ϵ_n}}}{\mathrm{ln}s_{k_n}(ϵ_n)}.$$

### B.3 Proof of Lemma 3.9

First, we have

$$L_n(1)=\underset{i=0}{\overset{h_n1}{}}\frac{s_{i+1}(ϵ_n)}{\left(s_i(ϵ_n)\right)^{1+ϵ_n}}+\underset{i=h_n}{\overset{k_n1}{}}\frac{s_{i+1}(ϵ_n)}{\left(s_i(ϵ_n)\right)^{1+ϵ_n}}.$$

Noticing $`s_0(ϵ_n)=1`$ and applying Lemma 3.7 to the above two summations, we have

$$L_n(1)L_n^{}(1)+L_n^{\prime \prime }(1),$$
(21)
where

$$L_n^{}(1)=\frac{h_n}{\left(1+ϵ_n\right)^{h_n}}\left(\left(s_{h_n}(ϵ_n)\right)^{\left(\frac{1}{1+ϵ_n}\right)^{h_n}E_{ϵ_n}\left(h_n\right)}\right)$$

and

$$L_n^{\prime \prime }(1)=\frac{k_nh_n}{\left(1+ϵ_n\right)^{k_nh_n}}\left(\frac{\left(s_{k_n}(ϵ_n)\right)^{\left(\frac{1}{1+ϵ_n}\right)^{k_nh_n}}}{s_{h_n}(ϵ_n)}\right)^{E_{ϵ_n}\left(k_nh_n\right)}.$$

Now, we can rewrite $`L_n^{\prime \prime }(1)`$ as

$$L_n^{\prime \prime }(1)=\frac{k_nh_n}{\left(1+ϵ_n\right)^{k_nh_n}}\left(s_{k_n}(ϵ_n)\right)^{\beta _n^{\prime \prime }},$$

where

$$\beta _n^{\prime \prime }=\left(\left(\frac{1}{1+ϵ_n}\right)^{k_nh_n}1+\nu _n\right)E_{ϵ_n}\left(k_nh_n\right).$$

We also rewrite $`L_n^{}(1)`$ as

$$L_n^{}(1)=\frac{h_n}{\left(1+ϵ_n\right)^{h_n}}\left(s_{k_n}(ϵ_n)\right)^{\beta _n^{}},$$
(22)
where

$$\beta _n^{}=\left(1\nu _n\right)\left(\frac{1}{1+ϵ_n}\right)^{h_n}E_{ϵ_n}\left(h_n\right).$$

By Lemma 3.8 and the fact that by (14) and (21)

$$C\frac{ϵ_n+L_n^{}(1)+L_n^{\prime \prime }(1)}{\mathrm{ln}s_{k_n}(ϵ_n)},$$

we conclude that for some constant $`c`$,

$$0\frac{L_n^{}(1)}{\mathrm{ln}s_{k_n}(ϵ_n)}c\text{and}0\frac{L_n^{\prime \prime }(1)}{\mathrm{ln}s_{k_n}(ϵ_n)}c\text{for all}n.$$
(23)
Since $`1k_nh_nw1`$ and $`\nu _n0`$, no subsequence of $`\{\beta _n^{\prime \prime },n0\}`$ can approach $`\mathrm{}`$ or converge to a finite negative number. On the other hand, by Lemma 3.8 and (23), no subsequence of $`\{\beta _n^{\prime \prime },n0\}`$ can approach $`+\mathrm{}`$ or converge to a finite positive number. Thus, $`lim_n\mathrm{}\beta _n^{\prime \prime }=0`$ and consequently, $`lim_n\mathrm{}\nu _n=0.`$ By (22),

$$\frac{L_n^{}(1)}{\mathrm{ln}s_{k_n}(ϵ_n)}=\frac{\frac{h_n}{k_n}}{\left(1+ϵ_n\right)^{h_n}}\frac{\left(\left(s_{k_n}(ϵ_n)\right)^{\frac{1}{k_n}}\right)^{k_n\beta _n^{}}}{\mathrm{ln}\left(s_{k_n}(ϵ_n)\right)^{\frac{1}{k_n}}}.$$

Since $`1k_nh_nw1`$ and $`0k_n\frac{1}{\sqrt{ϵ_n}}w1`$,

$$\underset{n\mathrm{}}{lim}\frac{\frac{h_n}{k_n}}{\left(1+ϵ_n\right)^{h_n}}=1,\underset{n\mathrm{}}{lim}k_n\beta _n^{}=1,\text{and thus}\underset{n\mathrm{}}{lim}\frac{L_n^{}(1)}{\mathrm{ln}s_{k_n}(ϵ_n)}=\underset{n\mathrm{}}{lim}\frac{\left(s_{k_n}(ϵ_n)\right)^{\frac{1}{k_n}}}{\mathrm{ln}\left(s_{k_n}(ϵ_n)\right)^{\frac{1}{k_n}}}.$$

Using Lemma 3.8, (23) and an argument similar to the proof for $`lim_n\mathrm{}\nu _n=0`$, we can show that for some constant $`\mathrm{\Delta }`$

$$\underset{n\mathrm{}}{lim}\left(s_{k_n}(ϵ_n)\right)^{\frac{1}{k_n}}=\mathrm{\Delta }>1.$$

### B.4 Proof of Lemma 3.10

This lemma follows from Lemma 3.9 and the fact that $`1k_nh_nw1`$ and $`0k_n\frac{1}{\sqrt{ϵ_n}}w1`$. The calculations are similar to those for proving Lemma 3.9.

### B.5 Proof of Lemma 3.11

Since $`b_n1`$, it suffices to show that for all $`i`$,

$$b_n^{d_i}s_i(ϵ_n),$$

where $`d_i=_{i^{}=0}^{i1}\left(1+ϵ_n\right)^i^{}`$. We can prove this inequality by induction on $`i`$. The base case follows from the fact that $`s_0(ϵ_n)=1`$ and $`b_n1`$. The induction step follows from the fact that by Fact 4 and Lemma 3.5,

$$C\frac{ϵ_n+\frac{s_{i+1}(ϵ_n)}{\left(s_i(ϵ_n)\right)^{1+ϵ_n}}}{\mathrm{ln}s_{k_n}(ϵ_n)}.$$

### B.6 Proof of Lemma 3.12

$`L_n(j)`$ $`=`$ $`{\displaystyle \underset{u=0}{\overset{j1}{}}}\left({\displaystyle \underset{\stackrel{0ik_nj}{iu(modj)}}{}}{\displaystyle \frac{s_{i+j}(ϵ_n)}{\left(s_i(ϵ_n)\right)^{ϵ_n}}}\right)`$
$`=`$ $`{\displaystyle \underset{u=0}{\overset{j1}{}}}\left({\displaystyle \underset{i^{}=0}{\overset{g(j,u)1}{}}}{\displaystyle \frac{s_{u+\left(i^{}+1\right)j}(ϵ_n)}{\left(s_{u+i^{}j}(ϵ_n)\right)^{ϵ_n}}}\right)`$
$``$ $`{\displaystyle \underset{u=0}{\overset{j1}{}}}L_n^{}(j,u),`$
where

$$g(j,u)=\frac{k_nu}{j}$$

and

$$L_n^{}(j,u)=\frac{g(j,u)}{\left(1+ϵ_n\right)^{g(j,u)}}\left(\frac{\left(s_{h_n}(ϵ_n)\right)^{\left(\frac{1}{1+ϵ_n}\right)^{g(j,u)}}}{b_n^{\left(w1\right)\left(1+ϵ_n\right)^{w1}}}\right)^{E_{ϵ_n}\left(g(j,u)\right)}.$$

The term $`L_n^{}(j,u)`$ is obtained by applying Lemma 3.7 to the inner summation in the right-hand side of the above equalities. The derivation also uses the fact that because $`k_nw+1u+g(j,u)jk_n`$,

$$s_{u+g(j,u)j}(ϵ_n)s_{h_n}(ϵ_n)$$

and the fact that by Lemma 3.11

$$b_n^{\left(w1\right)\left(1+ϵ_n\right)^{w1}}s_u(ϵ_n).$$

On the other hand, for each $`j=2,\mathrm{},w1`$ and $`u=0,\mathrm{},j1`$,

$$\underset{n\mathrm{}}{lim}\frac{L_n^{}(j,u)}{\mathrm{ln}s_{k_n}(ϵ_n)}=\frac{\mathrm{\Delta }^j}{j\mathrm{ln}\mathrm{\Delta }},$$

which can be verified using Lemma 3.9, the fact $`1k_nh_nw1`$ and $`0k_n\frac{1}{\sqrt{ϵ_n}}w1`$, and calculations similar to those in the proof of Lemma 3.9.


format: text

text:
# I Introduction

## I Introduction

When reactive processes take place in low dimensional spaces, the mean field (MF) laws of classical kinetics, in which each particle is assumed to interact with the system as a whole, become questionable. In this simple one-particle picture, information about special geometric constraints or many-particle correlation effects is absent. However, these features become increasingly important as the dimensionality of the space decreases and may eventually give rise to a crossover between universal macroscopic MF behavior and specific, strongly lattice-dependent behavior below a critical dimension $`d_c`$. The critical dimension $`d_c`$ is found to depend on the characteristics of the support (such as average coordination number) and the stoichiometry of the reactive dynamics, i.e., its degree of nonlinearity.

The crossover phenomenon mentioned above is not specific of reactive systems, but is common to many other statistical systems (interacting spins, random walks, etc.). To understand its real nature, it is necessary to resort to a more refined description in which relevant fluctuation effects in concentration and occupation number space can be accounted for. In view of the difficulties encountered by a full-scale microscopic analysis, one typically tries to devise “minimal” models which contain the necessary ingredients to observe a significant departure of MF behavior at sufficiently low dimensions. A probabilistic, time-continuous approach of this kind for a detailed study of fluctuations is provided by Master equation (ME) techniques, in which the local dynamics is specified by transition rates between different microscopic states. In the ME approach, one is typically led to a set of evolution equations for the moments of the probability density, which can be taken as a starting point to compute the most characteristic macroscopic observables, generally associated with the first low-order moments. However, if the transition rates are nonlinear, the low-order moments will not obey closed equations but will rather be linked to the higher order ones by an infinite hierarchy of coupled equations. In the general case, these hierarchies cannot be solved in a closed form. Suitable truncation techniques may then help to overcome this difficulty.

A more recent, very successful method to study the evolution of low dimensional reactive systems is based on Monte Carlo (MC) simulations , in which the microscopic state of the system is updated at discrete time steps according to a given dynamical rule. One of our goals in this paper is to stablish a link between the physics underlying this simulational approach and the ME formalism. To this end, we shall formulate mathematically the evolution law prescribed by the MC algorithm as a stochastic dynamical system whose state variables are Boolean occupation numbers for the state of each lattice site . As we shall see, this cellular automaton (CA) model yields a set of moment equations similar to that obtained from a time-continuous ME.

So far, most of the literature devoted to the effects of dimensionality on reactive dynamics has focused on diffusion-controlled reactions . In these systems, deviations of MF behavior at low dimensions may be expected due to the reduced effective mobility of the reactants. There are, however, situations in which diffusion can be neglected within the time scale of interest, like e.g. chemical reactions in solid materials and certain radical isolation problems . Such systems of immobile reactants constitute the object of our study in this paper. Clearly, the absence of diffusion reduces the ability of each particle to interact with all the others, thus driving the system further away from the applicability conditions of MF theory. This effect is enhanced in the presence of short range interactions restricted to, say, nearest neighbours and hard core exclusion not allowing more than one particle per lattice site .

More specifically, we will study the 1D lattice dynamics in two particular examples of nonlinear irreversible associated with the cooperative desorption systems (CDs)

$`A+A`$ $`\stackrel{k_R}{}`$ $`A+S\text{cooperative partial desorption (CPD)}`$ (2)
$`A+A`$ $`\stackrel{k_R}{}`$ $`S+S.\text{cooperative total desorption (CTD).}`$ (3)
where $`A`$ is the reactive species, $`S`$ the empty lattice site and $`k_R`$ is the rate of reaction. Notice that steps (2)-(3) are typical parts of realistic, more complex reaction schemes as discussed further in the Conclusions. Despite their apparent simplicity, they display a complex non-MF behavior characterized by frozen, non universal, initial-condition-dependent steady states . The dependence on the initial conditions is the signature of the weak ergodic properties of the CDs, which is in turn related to the irreversibility of the reactive schemes (2)-(3). A remarkable feature of the CDs is the special structure of the underlying moment equations, which allows one to compute explicitly the coverage and the fluctuation dynamics and thus test in a very efficient way the applicability of diverse truncation approaches.

The paper is organized as follows. In section II, a comprehensive study of the one-dimensional CPD is presented. First, we introduce a particular biased implementation of the CPD and characterize its non-MF behavior using an intuitive argument. In II B, we introduce a stochastic dynamical rule which mimics the microscopic, time-discrete evolution of the system as prescribed by MC simulations and show that this dynamical rule characterizes properly the steady states of the system. In II C, we derive evolution equations for the first- and second-order moments of the probability distribution for the microscopic states and use the same formalism to obtain a hierarchy of coupled equations describing the time evolution of a particular subset of moments, namely those involving contiguous occupation numbers. These moments can be identified with the probabilities of finding a randomly chosen string of contiguous sites simultaneously occupied. In II D, it is found that the solution of the hierarchy for both microscopic and coarse-grained initial conditions leads to an explicit expression for the mean coverage of the lattice. We also derive equations for the coarse-grained dynamics of vacant sites in terms of generalized probabilities for occupied sites. Next, in II E, we present a general ME for an array of Boolean variables and show that, in the special case of the CPD, the evolution equations for the mean occupation number and the second-order moment are similar to those obtained in the CA approach. In section III, we study the relevance of inhomogeneous fluctuations in the CPD system. A set of evolution equations retaining only pair fluctuation correlations fails to reproduce the correct dynamics, the reason being the nonnegligibility of higher order fluctuation correlations. These can be calculated explicitly from sets of generalized moment equations, which also allow us to compute the dynamics of the vacant sites for clusters of small size. In section IV, we extend the main results of sections II and III to the CTD. The conclusions are summarized in section V, which also outlines a research strategy for future work in this area. In the Appendices, we deal with a symmetric version of the CPD and discuss its equivalence with the biased CPD. We also study the dynamics of particle islands.

## II  Boolean dynamics of the CPD: Model and exact results

### A Definition of the system and MF rate equation

Consider a 1D lattice with $`N`$ sites which may be either empty ($`S`$) or filled with a single particle ($`A`$). The reaction takes place according to the scheme of Fig. 1. At each time step $`\mathrm{\Delta }t`$, a lattice site is randomly chosen. If the selected site is filled, the particle desorbs with a certain probability (equal to the rate of reaction $`k_R`$) provided that its right neighbour site is also occupied; otherwise, nothing occurs. The classical rate equation for this CPD scheme (Eq. (2)) reads

$$\frac{dc(t)}{dt}=k_Rc(t)^2,$$
(4)
where $`c(t)`$ is the A particle concentration, here identified as the mean fraction of occupied sites, also referred as “coverage”. Its solution predicts a decay of the form

$$c(t)=\frac{c(0)}{1+c(0)k_Rt}.$$
(5)
to a zero-coverage steady state. However, as we see below, the restricted 1D geometry of the lattice allows for non MF steady states. It is indeed easily seen that all lattice configurations without contiguous particles cannot evolve in time. To understand this obvious MF failure in detail, we need to set up a model for the microscopic dynamics.

### B Boolean modeling and steady states

We stipulate that each site in the lattice is characterized by a Boolean occupation number:

$$n_i(t)=\{\genfrac{}{}{0pt}{}{1\text{if site i is occupied}}{0\text{if site i is empty}},i=1,\mathrm{},N.$$
(6)
Each site evolves according to the nonlinear dynamical rule

$$n_i(t+\mathrm{\Delta }t)=n_i(t)\xi _N^{(i)}(t)\xi _R(t)n_i(t)n_{i+1}(t),i=1,\mathrm{},N$$
(7)
where

$$\stackrel{}{\xi }_N(t)=\left(\begin{array}{c}\xi _N^{(1)}(t)\\ \mathrm{}\\ \xi _N^{(N)}(t)\end{array}\right),\xi _N^{(i)}(t)=0,1.$$
(8)
is a $`N`$-dimensional vector of stochastic Boolean decision variables. If, say, site $`i`$ is chosen, the $`i`$-th component will be one and all other components will be zero. Hence, the different components $`\xi _N^{(i)}(t)`$ in a given, single realization are correlated:

$$\underset{i=1}{\overset{N}{}}\xi _N^{(i)}(t)=1\xi _N^{(i)}(t)\xi _N^{(j)}(t)=\xi _N^{(i)}(t)\delta _{ij}.$$
(9)
Since at each time step $`\mathrm{\Delta }t`$, one site out of $`N`$ is randomly chosen, the mean value $`\overline{\xi _N^{(i)}(t)}`$ over an ensemble of realizations will be $`1/N`$. The additional stochastic variable $`\xi _R(t)`$ takes randomly the values $`1`$ and $`0`$ with probabilities $`p_R`$ and $`1p_R`$, respectively.

To have a well posed problem, we still have to specify the boundary conditions. We shall take periodic boundary conditions, which amounts to setting $`n_{N+1}(t)=n_1(t)`$ in the last equation (7).

Implicit in the above scheme is the idea that, at most, one reactive event may occur in the lattice in a given time interval $`\mathrm{\Delta }t`$, even if there are several a priori reactive pairs. The justification of such a prescription is that, typically, the ocurrence of a reaction requires to overcome an activation energy threshold. At ordinary temperatures (supposed to prevail here), this can be achieved only if a sufficiently strong fluctuation impinges on the system as a result, say, of the coupling between the adsorbate and the lattice. Since the probability of such an event is small, one may expect that reactions will occur asynchronously at different lattice sites, which is precisely what is stipulated in our evolution rule.

Eqs. (7) will be used in the sequel to describe the dynamics of the CPD at three different levels:

1. A “microscopic” level in which the exact microscopic dynamics, i.e. the initial condition $`\{n_i(0)\}`$ and the decision path represented by the variable sets $`\{\stackrel{}{\xi }_N(0),\mathrm{},\stackrel{}{\xi }_N(t)\}`$ and $`\{\xi _R(0),\mathrm{}\xi _R(t)\}`$, is assumed to be known in detail.
2. an intermediate level in which the system is prepared in such a way, that the initial condition is known in detail and one averages only over the subsequent dynamics, i.e. , over the different paths or realizations.
3. a “coarse-grained” description in which one averages over a statistical ensemble of realizations and a nonequilibrium ensemble of initial conditions.

After a time $`t_{st}`$ a steady state $`\{n_i^{st}\}`$ is attained. The dynamical rule (7) allows a straightforward characterization of these steady states. Since the first term in the r.h.s. of (7) cancels with the l.h.s., one has:

$$\xi _N^{(i)}(t)n_i^{st}n_{i+1}^{st}=0.$$
(10)
This holds for all times $`tt_{st}`$. Since $`\xi _N^{(i)}(t)`$ is a random variable, it will be nonzero at some time $`t`$ for any given site $`i`$, meaning that the product $`n_i^{st}n_{i+1}^{st}`$ must vanish for all $`i`$. This expresses the fact that two contiguous sites cannot be simultaneously occupied in a steady state. However, not all configurations satisfying this condition are attained with equal probability. For instance, if $`N`$ is even, we can be certain that the steady-state configuration with alternating occupied and empty sites will never be reached if we start with less than half the lattice filled. Therefore, a simple combinatorial counting of the non-evolving configurations fails to provide the correct mean steady-state coverage .

### C Moment equations and cluster dynamics

Let us now turn to the dynamics generated by Eqs. (7). First, we fix the initial configuration $`(n_1(0),\mathrm{},n_N(0))`$ of the lattice and take the average of Eq. (7) over an ensemble of different realizations. Using the statistical independence of $`\xi _N(t)`$, $`\xi _R(t)`$ and the occupation numbers $`n_i(t)`$, this yields

$$\overline{n_i(t+\mathrm{\Delta }t)}\overline{n_i(t)}=\frac{p_R}{N}\overline{n_i(t)n_{i+1}(t)},i=1,\mathrm{},N.$$
(11)
The quantity $`\frac{p_R}{N}`$ can be regarded as the probability that a reaction takes place at a given site $`i`$ in the time interval $`(t,t+\mathrm{\Delta }t)`$ given that site $`i`$ and $`i+1`$ are occupied. The rate of reaction is obtained by dividing this probability by the time step $`\mathrm{\Delta }t`$:

$$k_R=\frac{p_R}{N\mathrm{\Delta }t}$$
(12)
To derive the continuous-time limit of Eq. (11), we divide both sides by $`\mathrm{\Delta }t`$ and let this quantity go to zero in such a way that the reaction rate $`k_R`$ remains finite. This can be e.g. accomplished by letting the system size $`N`$ simultaneously go to infinity so that $`N\mathrm{\Delta }t=C`$. We shall choose the constant $`C`$ equal to unity, implying that, after one time unit, each lattice site has been visited once on average. With this choice, $`k_R`$ becomes numerically equal to the value of $`p_R`$. The resulting equation reads

$$\frac{d}{dt}\overline{n_i(t)}=k_R\overline{n_i(t)n_{i+1}(t)}$$
(13)
In a similar way, one can obtain an evolution equation for the second-order moment $`\overline{n_i(t)n_j(t)}`$. Multiplying (7) by $`n_j(t+\mathrm{\Delta }t)`$ and using (9), one finds

$$\overline{n_i(t+\mathrm{\Delta }t)n_j(t+\mathrm{\Delta }t)}\overline{n_i(t)n_j(t)}=\frac{p_R}{N}\overline{n_i(t)n_{i+1}(t)n_j(t)}\frac{p_R}{N}\overline{n_i(t)n_j(t)n_{j+1}(t)},ij$$
(14)
which in the continuous-time limit becomes

$$\frac{d}{dt}\overline{n_i(t)n_j(t)}=k_R\overline{n_i(t)n_{i+1}(t)n_j(t)}k_R\overline{n_i(t)n_j(t)n_{j+1}(t)}.$$
(15)
For $`j=i+1`$, Eq. (15) together with the Boolean property $`n_i^2(t)=n_i(t)`$ yields

$$\frac{d}{dt}\overline{n_i(t)n_{i+1}(t)}=k_R\overline{n_i(t)n_{i+1}(t)}k_R\overline{n_i(t)n_{i+1}(t)n_{i+2}(t)}$$
(16)
Unless otherwise specified, we shall set $`p_R=1`$ for simplicity, implying that $`k_R`$ is equal to unity. Note, however, that it is possible to absorb the reaction rate $`k_R`$ appearing in the time-continuous equations (13) and (15) in the time scale by means of a dimensionless variable $`\tau =k_Rt`$ .

An important feature of Eqs. (13) and (16) is that they couple in a linear fashion moments involving only contiguous sites. This turns out to be a generic property that also holds for the dynamics of higher order moments.

Let us now consider a more general subset of $`k`$ contiguous lattice sites $`i,\mathrm{},i+k1`$. The probability to find all sites occupied at time $`t`$, i.e., a cluster of size $`k`$, is given by the quantity

$$M_k^{(i)}(t)=\overline{\underset{j=i}{\overset{i+k1}{}}n_j(t)},i,k=1,\mathrm{},N.$$
(17)
To derive an evolution equation for $`M_k^{(i)}(t)`$, we must generalize Eqs. (13) and (16). Taking the dynamical rule (7) as a starting point, one obtains

$$\underset{j=i}{\overset{i+k1}{}}n_j(t+\mathrm{\Delta }t)\underset{j=i}{\overset{i+k1}{}}n_j(t)=\underset{j=i}{\overset{i+k2}{}}\xi _N^{(j)}(t)\xi _R(t)\underset{j=i}{\overset{i+k1}{}}n_j(t)\xi _N^{(i+k1)}(t)\xi _R(t)\underset{j=i}{\overset{i+k}{}}n_j(t),$$
(18)
where $`i=1,\mathrm{},N`$. Taking averages in (18) for $`k<N`$, one gets

$`M_k^{(i)}(t+\mathrm{\Delta }t)M_k^{(i)}(t)={\displaystyle \frac{(k1)}{N}}M_k^{(i)}(t){\displaystyle \frac{1}{N}}M_{k+1}^{(i)}(t).`$ (19)
We now introduce the global quantity

$$\overline{P}_k^{(N)}(t)=\frac{1}{N}\underset{i=1}{\overset{N}{}}M_k^{(i)}(t),$$
(20)
representing the probability of finding $`k`$ filled adjacent sites in the $`N`$-site lattice. Summing over the site index $`i`$ in Eqs. (19), we find

$$\overline{P}_k^{(N)}(t+\mathrm{\Delta }t)\overline{P}_k^{(N)}(t)=\frac{(k1)}{N}\overline{P}_k^{(N)}(t)\frac{1}{N}\overline{P}_{k+1}^{(N)}(t),k<N.$$
(21)
Taking the continuous-time limit of (21) for a given finite value of $`k`$, a set of evolution equations for $`\overline{P}_k(t)=lim_N\mathrm{}\overline{P}_k^{(N)}(t)`$ is obtained:

$$\frac{d\overline{P}_k(t)}{dt}=(k1)\overline{P}_k(t)\overline{P}_{k+1}(t),k=1,2,\mathrm{},k_{max},$$
(22)
where the integer $`k_{max}`$ is the size of the largest cluster. The first term on the r.h.s. of (22) corresponds to a destruction of a k-particle cluster by the interaction of two particles inside the cluster, while the second term stands for its destruction by desorption of its rightmost particle, which requires an additional occupied site, i.e., a cluster of $`k+1`$ sites.

If the lattice contains only clusters of finite size, then $`k_{max}<\mathrm{}`$ and the hierarchy of equations (22) is truncated by the condition $`\overline{P}_{k_{max}+1}(t)0`$. The last equation (22) reads then

$$\frac{d\overline{P}_{k_{max}}(t)}{dt}=(k_{max}1)\overline{P}_{k_{max}}(t).$$
(23)
### D Solution of hierarchy and mean coverage for microscopic and coarse-grained initial conditions

Suppose that we start with a given initial configuration $`\left\{n_i(0)\right\}`$ characterized by the nonvanishing set of probabilities

$$\{\overline{P}_1(0),\overline{P}_2(0),\mathrm{},\overline{P}_{k_{max}}(0)\}.$$
(24)
Using the linearity of Eqs. (22), one can show that the solution for $`t>0`$ is of the form

$$\overline{P}_k(t)=\mathrm{exp}((k1)t)\underset{j=0}{\overset{k_{max}k}{}}\frac{(\mathrm{exp}(t)1)^j}{j!}\overline{P}_{k+j}(0),k=1,\mathrm{},k_{max}.$$
(25)
Note that for $`t\mathrm{}`$ only $`\overline{P}_1`$ survives, representing the probability that a randomly chosen site be occupied. Clearly, this probability is equal to the ratio between the average number of occupied sites and the total number of sites, i.e., the mean coverage of the lattice $`c(t)`$. In the long-time limit, one has:

$$c(\mathrm{})=\overline{P}_1(\mathrm{})=\underset{N\mathrm{}}{lim}\frac{\overline{N_A(\mathrm{})}}{N}=\underset{j=0}{\overset{k_{max}1}{}}\frac{(1)^j}{j!}\overline{P}_{j+1}(0).$$
(26)
We see that the asymptotic value of the coverage depends on all details of the initial cluster distribution. The validity of Eq. (26) is confirmed by MC simulations (Fig. 2(a) ). The simulations were performed according to the time-discrete rule (7). The data correspond to a chain ring of $`100`$ particles and the initial configurations:

$`C1`$ $`=`$ $`11111111111111110111111111111011110111111111111111011111111111111111`$
$`11101111111011011111111011111010`$
$`C2`$ $`=`$ $`01111001111110010011110111110111011111111110100011111111011011001111`$
$`11011101001111101011111111101111`$
$`C3`$ $`=`$ $`11010101101001100100101010010010000101001011101001001001011001001111`$
$`01100011111001011001101001100111`$
$`C4`$ $`=`$ $`10011100111000010011011000001000000000010000100100100100011000101000`$
$`01001010010101000011001101100010`$
Let us now assume the more realistic situation in which the initial configuration of the system is not known in detail, but is characterized only through the particle coverage $`p`$. If we consider a uniform ensemble of all random microscopic configurations with a given $`p`$, the system will initially be translationally invariant and this property will propagate in time. Thus, the probabilities of finding $`k`$ consecutive filled sites $`i,\mathrm{},i+k1`$

$$P_k^{(N)}(t)=\underset{j=i}{\overset{i+k1}{}}n_j(t),k=1,\mathrm{}N$$
(27)
(the angular brackets $`\mathrm{}`$ stand for the averaging over realizations and initial states) will not depend on the evaluation site $`i`$. After averaging Eq. (19) over the initial conditions and going over to the time continuum, one obtains:

$$\frac{dP_k(t)}{dt}=(k1)P_k(t)P_{k+1}(t)k=1,2,\mathrm{},$$
(28)
which is formally identical to Eq. (22) for $`\overline{P}_k`$ with $`k_{max}\mathrm{}`$. However, the initial conditions are now simpler. Since the initial occupancies of each site are statistically independent, one has:

$$P_k(0)=p^k,k=1,2,\mathrm{}$$
(29)
A solution satisfying the initial conditions (29) can be easily found by using an ansatz suggested in . One obtains

$`P_1(t)`$ $`=`$ $`p\mathrm{exp}[p(\mathrm{exp}(t)1)],`$ (31)
$`P_k(t)`$ $`=`$ $`p^{k1}\mathrm{exp}\left[(k1)t\right]P_1(t),k=2,3,\mathrm{}`$ (32)
Again, the survival expectancy $`P_1(t)`$ corresponds to the mean coarse-grained coverage $`c(t)=lim_N\mathrm{}\frac{N_A\left(t\right)}{N}`$. For short times, the series expansion of (31) yields:

$$c(t)=P_1(t)=pp^2t+\frac{p^2(p+1)}{2}t^2+o(t^3)$$
(33)
It is interesting to compare this with the short-time asymptotics of the exact solution of the MF equation (4) for $`k_R=1`$:

$$c_{MF}(t)=\frac{p}{1+pt}=pp^2t+p^3t^2+o(t^3)$$
(34)
Thus, we see that the first MF deviation appears in the second order term. For long times, one observes an exponential decay into an absorbing state characterized by the asymptotic coverage

$$c(\mathrm{})=p\mathrm{exp}(p)$$
(35)
Formulae (29) for the transient behavior and (35) for the asymptotics are confirmed by time-discrete MC simulations (Fig. 2(b) ). As in the previous case, all $`P_k(t)`$ with $`k2`$ vanish for $`t\mathrm{}`$. Note that Eqs. (29) are formally obtained from Eqs. (25) by averaging over a uniform distribution of microscopic states with global coverage $`p`$. This amounts to allowing for clusters of arbitrarily large size , i.e., $`k_{max}\mathrm{}`$.

So far, we have only considered the dynamics of particles, but it is also of interest to ask for the time evolution of empty intervals of a given size inside the lattice. Clearly, the number of empty intervals must grow as the reactions proceed. To set up explicit equations for clusters of vacant sites (“holes”), we consider the time-discrete evolution equation for the complementary occupation number $`s_i(t)=1n_i(t)`$:

$$s_i(t+\mathrm{\Delta }t)s_i(t)=\xi _N^{(i)}n_i(t)n_{i+1}(t),i=1,\mathrm{},N.$$
(36)
By averaging this equation over an ensemble of realizations and a uniform initial distribution of microscopic states with a coverage $`p`$ one gets:

$$\frac{dS_1(t)}{dt}=P_2(t),$$
(38)
where $`S_1(t)=s_i(t)`$. Eq. (38) is in agreement with the conservation law $`\frac{d}{dt}(P_1(t)+S_1(t))=0`$.

The dynamics of hole multimers can be derived starting from the evolution equation for the product $`{\displaystyle \underset{k=i}{\overset{i+k1}{}}}s_k(t)`$. The general form of the evolution equation for $`S_k(t)={\displaystyle \underset{k=i}{\overset{i+k1}{}}}s_k(t)`$ becomes more and more complicated with increasing cluster size. The next three equations read

$`{\displaystyle \frac{dS_2(t)}{dt}}`$ $`=`$ $`P_2(t)P_3(t),`$ (39)
$`{\displaystyle \frac{dS_3(t)}{dt}}`$ $`=`$ $`P_2(t)P_3(t)+P_4(t)P_{1,2}^{(2)}(t),`$ (40)
$`{\displaystyle \frac{dS_4(t)}{dt}}`$ $`=`$ $`P_2(t)P_3(t)+P_4(t)P_5(t)P_{1,2}^{(2)}(t)+P_{1,3}^{(2)}(t)+P_{2,2}^{(2)}(t)P_{1,2}^{(3)}(t),`$ (41)
where the quantities $`P_{n,m}^{(l)}(t)`$ on the r.h.s. of Eqs. (40)-(41) are the joint probabilities of finding two fully occupied strings of length $`n`$ and $`m`$ separated by $`l`$ lattice spacings. The initial conditions for which these equations must be solved are

$$S_k(0)=(1p)^k,k=1,2,\mathrm{}$$
(42)
Eqs. (38) and (39) can be integrated straightforwardly, since the functions on the r.h.s. are already explicitly known. In section III, we show how to obtain explicit expressions for the probabilities $`S_3(t)`$ and $`S_4(t)`$ by solving a generalized hierarchy for the joint probabilities $`P_{n,m}^{(l)}(t)`$.

### E  Comparison with the ME approach

An alternative way of deriving moment equations in the framework of a time-continuous approach is provided by the Master equation (ME). Let us again consider a set of $`N`$ Boolean variables $`\{n\}=(n_1,\mathrm{},n_N)`$ arranged on the sites of a 1D lattice with periodic boundaries ($`n_{N+1}=n_1`$). Starting from an arbitrary state, the evolution of the probability density $`P(\{n\};t)`$ is governed by a ME of the form:

$$\frac{dP(\{n\};t)}{dt}=\underset{j}{}w_j(\{n\}\{n^{}\},t)P(\{n\};t)+\underset{j}{}w_j(\{n^{}\}\{n\},t)P(\{n^{}\};t)$$
(43)
where $`\{n^{}\}=(n_1,\mathrm{},1n_j,\mathrm{},n_N)`$ and $`w_j(\{n\}\{n^{}\},t)`$ is the transition rate from the state $`\{n\}`$ to the state $`\{n^{}\}`$ at time $`t`$. To obtain an evolution equation for the average occupation number

$$n_i(t)=\underset{\{n\}}{}n_i(t)P(\{n\},t),$$
(44)
we multiply Eq. (43) by $`n_i(t)`$ and sum over all different configurations $`\{n\}`$. This yields:

$$\frac{d}{dt}n_i(t)=\left[12n_i(t)\right]w_i(\{n\}\{n^{}\},t)$$
(45)
For the time evolution of the second order moment one gets

$`{\displaystyle \frac{d}{dt}}n_i(t)n_j(t)`$ $`=`$ $`\left[n_j(t)2n_i(t)n_j(t)\right]w_i(\{n\}\{n^{}\},t)`$ (47)
$`+\left[n_i(t)2n_i(t)n_j(t)\right]w_j(\{n\}\{n^{}\},t)`$
For the CPD, the transition rate reads

$$w_j(\{n\}\{n^{}\},t)=k_Rn_i(t)n_{i+1}(t).$$
(48)
Using Eqs. (45) and (47) and the transition probability (48) with $`k_R=1`$, one can formally recover Eqs. (13) and (15) averaged over an ensemble of random initial conditions. As expected, this also holds for the higher order moments . Note that in the ME approach the double averaging over realizations and initial conditions is performed simultaneously via the probability distribution $`P(\{n\},t)`$. In the CA model, this has been done in two separate steps. One first chooses randomly an initial condition with a given $`p`$ and thereafter performs a series of different realizations. Next, one again selects a new random initial condition and a new set of realizations is carried out, and so on.

## III Truncation schemes and role of fluctuations in the CPD

The statistical properties of the N-site CPD system are described by the “Boltzmann-like” distribution functions $`c_{i_1,i_2\mathrm{},i_n}^{(N)}(t)=n_{i_1}(t)n_{i_2}(t),\mathrm{},n_{i_n}(t)`$, which can be expressed in terms of the mean occupations $`c_i^{(N)}(t)=n_i(t)`$ and a set of correlation functions

$$f_{i_1i_2,\mathrm{},i_n}^{(N)}(t_1;\mathrm{};t_n)=\delta n_{i_1}(t_1)\delta n_{i_2}(t_2)\mathrm{}\delta n_{i_n}(t_n),$$
(49)
where $`\delta n_i(t)=n_i(t)c_i^{(N)}(t)`$. In the following, we shall omit the superscript $`N`$ in the quantities $`c`$ and $`f`$ for the sake of notational simplicity. For $`n=2`$, and $`t_1=t_2=t`$, Eq. (49) defines the equal-time pair correlation function $`f_{i,j}(t)f_{i,j}(t;t)`$.

An approximate closure to the hierarchy equations can be obtained by performing an expansion in terms of correlation functions and keeping them up to a certain order, neglecting the higher-order ones. In this so-called Ursell expansion one defines the correlation functions $`f`$ through the relations

$`c_{i,j}(t)=c_i(t)c_j(t)+f_{i,j}(t),`$ (51)
$`c_{i,j,k}(t)=c_i(t)c_j(t)c_k(t)`$ $`+c_k(t)f_{i,j}(t)+c_i(t)f_{j,k}(t)+c_j(t)f_{i,k}(t)+f_{i,j,k}(t),`$ (53)
etc.
where the quantities $`f_{i,j}`$, $`f_{i,j,k}`$ account for the fluctuations:

$`f_{i,j}(t)`$ $`=`$ $`\delta n_i(t)n_j(t)`$ (55)
$`f_{i,j,k}(t)`$ $`=`$ $`\delta n_i(t)\delta n_j(t)\delta n_k(t),`$ (56)
etc. (57)
Different approximations emerge from Eqs. (III) when terms containing correlation functions of higher orders are neglected.

In the zeroth approximation all correlations between occupation numbers are neglected and the state of the system is completely specified by the mean occupation numbers $`c_i(t)`$. From Eq. (11) we have the MF equation

$$c_i(t+\mathrm{\Delta }t)=c_i(t)\frac{1}{N}c_i(t)c_{i+1}(t).$$
(58)
In the first approximation the rate equation (58) is extended with a term linear in the NN pair correlation $`f_{i,i+1}(t)`$,

$$c_i(t+\mathrm{\Delta }t)=c_i(t)\frac{1}{N}c_i(t)c_{i+1}(t)+\frac{1}{N}f_{i,i+1}(t).$$
(59)
Eq. (59) describes the corrections to the MF equation (58) caused by the fluctuations $`f_{i,i+1}(t)`$ that are built up by sequences of correlated reactions between the particles. These correlations are calculated from the second hierarchy equation (14) with $`j=i+1`$. Neglecting terms in $`o(1/N^2)`$ and higher in the r.h.s., we have

$`f_{i,i+1}(t+\mathrm{\Delta }t)`$ $`=`$ $`{\displaystyle \frac{1}{N}}c_{i+1}(t)f_{i,i+2}(t)+f_{i,i+1}(t){\displaystyle \frac{1}{N}}(c_i(t)c_{i+1}(t)c_i(t)[c_{i+1}(t)]^2.`$ (61)
$`.+c_{i+2}(t)f_{i,i+1}(t)c_{i+1}(t)f_{i,i+1}(t)+f_{i,i+1}(t))`$
Here the first term in the brackets represents the propagation to neighboring sites of fluctuations correlated over a distance of two lattice spacings. The other terms essentially contain the correlations created or destroyed by the reaction process; the terms linear in $`f_{i,i+1}`$ represent the effect of existing pre-reaction correlations, and the quantity

$$\frac{1}{N}c_i(t)c_{i+1}(t)+\frac{1}{N}c_i(t)[c_{i+1}(t)]^2$$
(62)
accounts for the correlations created by the reaction from a completely factorized state. The other pair correlations are calculated in a similar way from (14) with $`j=i+l`$:

$`f_{i,i+l}(t+\mathrm{\Delta }t)=f_l(t){\displaystyle \frac{1}{N}}c_i(t)f_{i+1,i+l}(t){\displaystyle \frac{1}{N}}\left(c_{i+1}(t)+c_{i+l+1}(t)\right)f_{i,i+l}(t)`$ (63)
$`{\displaystyle \frac{1}{N}}c_{i+l}(t)f_{i,i+l+1}(t)+o(1/N^2)+\text{ higher order terms},l=2,\mathrm{},[N]/2.`$ (64)
In the spatially homogeneous case, the system is translationally invariant; the solution obeys the relation $`c_i(t)=c(t)`$ and the correlations $`f_{i,j}(t)=f_{|ij|}(t)`$ depend only on the relative distance between the evaluation sites. In the limit $`N\mathrm{}`$, Eqs. (59), (61) and (64) yield the following set of time-continuous equations

$`{\displaystyle \frac{dc(t)}{dt}}`$ $`=`$ $`c(t)^2f_1(t),`$ (66)
$`{\displaystyle \frac{df_1(t)}{dt}}`$ $`=`$ $`c(t)^2(c(t)1)f_1(t)c(t)f_2(t),`$ (67)
$`{\displaystyle \frac{df_l(t)}{dt}}`$ $`=`$ $`c(t)[f_{l1}(t)+2f_l(t)+f_{l+1}(t)],l=2,3,\mathrm{}`$ (68)
Eqs. (III) can be used as a starting point for a truncation based on the neglect of pair correlations $`f_l(t)`$ for all $`l`$ equal or larger than a certain cutoff integer $`l_c`$. For $`l_c=2`$, i.e., in the pair approximation, the system of two equations approaches the steady state $`(0,0)`$, although the asymptotic decay of $`c(t)`$ is much slower than the $`t^1`$ decay prescribed by the MF approach due to large transient effects in $`f_1(t)`$ (Fig. 3). A log-log plot of the numerical solution suggests an inverse power law behavior of $`c(t)`$ for long times with an exponent less than one (see inset in Fig. 3). In the pair approximation, the stability of the MF fixed point can be proven by geometric arguments <sup>*</sup><sup>*</sup>*This is illustrated by an analysis of the 2D velocity field. Numerical results suggest that this property holds for any arbitrary $`l_c`$, meaning that the system truncated to any order will always attain the MF steady state of zero concentration, in contradiction with the non-MF results reported above. This reflects the non-negligibility of the three-point fluctuation correlations $`f_{i,j,k}(t)`$ which, as we shall see presently, indeed become of the same order of magnitude as the pair correlations $`f_l(t)`$ already for small $`l`$.

One can compute exactly these correlation fluctuations by considering the evolution equation for the joint probabilities $`P_{j,k}^{(l)}(t)`$, which in our model correspond to the distribution functions

$$\underset{r=i}{\overset{i+j1}{}}n_r(t)\underset{s=i+j+l1}{\overset{i+j+l+k2}{}}n_s(t).$$
(69)
Taking Eq. (18) as a starting point, a tedious but straightforward calculation shows that $`P_{j,k}^{(l)}(t)`$ evolves according to

$$\frac{dP_{j,k}^{(l)}(t)}{dt}=(j1)P_{j,k}^{(l)}(t)(k1)P_{j,k}^{(l)}(t)P_{j+1,k}^{(l1)}(t)P_{j,k+1}^{(l)}(t),j,k,l=1,2,\mathrm{}$$
(70)
The first (second) term on the r.h.s. of (70) corresponds to an event in which a particle inside the cluster of $`j(k)`$ occupied sites desorbs by interaction with a neighbour inside the cluster, while the third (fourth) term stands for the desorption of the rightmost particle inside the cluster by reaction with an occupied neighbour site at its right. Eq. (70) is solved using the ansatz

$$P_{j,k}^{(l)}(t)=p^{j+k2}\mathrm{exp}[(j+k2)t]P_{1,1}^{(l)}(t),j,k=1,2,\mathrm{}$$
(71)
This leads to the (infinite) closed coupled set of equations

$$\frac{dP_{1,1}^{(l)}(t)}{dt}=p\mathrm{exp}(t)\left[P_{1,1}^{(l)}(t)+P_{1,1}^{(l1)}(t)\right],l=2,3,\mathrm{}$$
(72)
with the boundary condition $`P_{1,1}^{(1)}(t)=P_2(t)`$. An explicit expression for $`P_{1,1}^{(l)}(t)`$ can be obtained from Eq. (72) by means of a generating function . The final result reads:

$$P_{1,1}^{(l)}(t)=P_1(t)\left[p\underset{k=0}{\overset{l1}{}}\left[\mathrm{ln}\left(\frac{P_1(t)}{p}\right)\right]^k/k!+\left[\mathrm{ln}\left(\frac{P_1(t)}{p}\right)\right]^l/l!\right]$$
(73)
This allows to compute the fluctuation correlation $`f_l(t)`$, which is given by

$$f_l(t)=P_{1,1}^{(l)}(t)[P_1(t)]^2,l=1,2,\mathrm{}$$
(74)
This function decreases superexponentially with increasing distance $`l`$, approaching zero for $`l\mathrm{}`$. The three-point NN fluctuation correlation $`h(t)=f_{1,2}(t)=\delta n_i\delta n_{i+1}\delta n_{i+2}`$ can be expressed as

$$h(t)=P_3(t)\left[P_1(t)\right]^3(2f_1(t)f_2(t))P_1(t).$$
(75)
Formulae (74) and (75) are confirmed by numerical simulations (Fig. 4). These also show that $`h(t)`$ may already get larger than $`f_l(t)`$ for $`l=2`$. In fact, the asymptotic values $`h(\mathrm{})`$ and $`f_2(\mathrm{})`$ are of the same order of magnitude in the whole range of the initial coverage $`p`$ (Fig. 5). Higher order fluctuations become comparatively large in the dilute limit $`p1`$.

In the light of the above, the failure of the truncation scheme seems thus to be due to the fact that it includes pair correlations of arbitrary long range whithout taking relevant higher order fluctuations into account from the very beginning. Although we have only shown the nonnegligibility of correlations up to the third order, some numerical computations suggest that, regardless of the initial conditions chosen, it is necessary to take into account the whole set of fluctuation correlations to obtain a deviation from the MF steady state.

A more restrictive truncation scheme consists in neglecting the effect of large clusters in Eqs. (28) by setting $`P_k(t)0`$ beyond a given size . This truncation procedure yields a smooth expansion of the exact results (29) and (35) in powers of $`p`$.

To conclude this paragraph, let us note that the explicit knowledge of the joint probabilities $`P_{j,k}^{(l)}(t)`$ can be used to integrate Eqs. (40)-(41). The solutions of Eqs. (36) read

$`S_1(t)`$ $`=`$ $`1P_1(t),`$ (77)
$`S_2(t)`$ $`=`$ $`12P_1(t)+P_2(t),`$ (78)
$`S_3(t)`$ $`=`$ $`1+(3+p{\displaystyle \frac{1}{2}}p^2)P_1(t)+2P_2(t){\displaystyle \frac{1}{2}}P_3(t),`$ (79)
$`S_4(t)`$ $`=`$ $`1+(4+3p2p^2+{\displaystyle \frac{1}{3}}p^3)P_1(t)+(3p+{\displaystyle \frac{1}{2}}p^2)P_2(t)P_3(t)+{\displaystyle \frac{1}{6}}P_4(t).`$ (80)
They are shown in Fig. 6 for the case of an initially full lattice.

## IV Dynamics of the CTD

The starting point is again a 1D lattice with empty ($`S`$) and occupied sites ($`A`$). The reaction now proceeds according to the scheme depicted in Fig. 7. At each time step, one site is randomly chosen. If the chosen site and its neighbour are occupied, both particles will desorb with probability $`k_R`$. The classical rate equation reads

$$\frac{dc(t)}{dt}=2k_Rc(t)^2,$$
(81)
which yields a faster decay than (4) to a zero concentration steady state, but again proportional to $`t^1`$ for long times. It is easily seen that the actual 1D system has the same steady states that the CPD system, i.e. all configurations with isolated particles. Once more, a deviation from the MF behavior is found.

To set up the corresponding microscopic evolution law, we must take into account that this time a particle at a given site $`i`$ will also desorb if its left neighbour site $`i1`$ is chosen and it is occupied. One has therefore an additional contribution in the r.h.s. of the dynamical rule:

$$n_i(t+\mathrm{\Delta }t)=n_i(t)\xi _N^{(i)}(t)\xi _R(t)n_i(t)n_{i+1}(t)\xi _N^{(i1)}(t)\xi _R(t)n_{i1}(t)n_i(t),i=1,\mathrm{},N.$$
(82)
Like in the CPD case, we can take Eq. (82) as a starting point to derive evolution equations for the first- and the second-order moments:

$`{\displaystyle \frac{d}{dt}}\overline{n_i(t)}`$ $`=`$ $`\overline{n_{i1}(t)n_i(t)}\overline{n_i(t)n_{i+1}(t)}`$ (84)
$`{\displaystyle \frac{d}{dt}}\overline{n_i(t)n_{i+1}(t)}`$ $`=`$ $`\overline{n_{i1}(t)n_i(t)}\overline{n_{i1}(t)n_i(t)n_{i+1}(t)}\overline{n_i(t)n_{i+1}(t)n_{i+2}(t)}`$ (85)
$`{\displaystyle \frac{d}{dt}}\overline{n_i(t)n_{i+l}(t)}`$ $`=`$ $`\overline{n_i(t)n_{i+1}(t)n_{i+l}(t)}\overline{n_i(t)n_{i+l1}(t)n_{i+l}(t)}`$ (87)
$`\overline{n_i(t)n_{i+l}(t)n_{i+l+1}(t)}\overline{n_{i1}(t)n_i(t)n_{i+l}(t)},l=2,3,\mathrm{}.`$
A generalization of Eqs. (84) and (85) for strings of $`k`$ consecutive sites leads again to a hierarchy for the global probabilities $`\overline{P}_k(t)`$:

$$\frac{d\overline{P}_k(t)}{dt}=(k1)\overline{P}_k(t)2\overline{P}_{k+1}(t),k=1,2,\mathrm{},k_{max}.$$
(88)
Note that the prefactor of the second term is now $`2`$ due to the additional reactive event between the leftmost particle inside the cluster and a particle at its left neighbour site. An equation of the form (88) has been obtained in the context of reactant isolation  and random sequential adsorption (RSA) models . In these models, the deposition of a dimer on the lattice is equivalent to the desorption of a pair of reactants and empty pairs of sites available for deposition correspond to unreacted pairs of reactants (see ref. ).

The solutions of the hierarchy (88) for a given initial configuration read

$$\overline{P}_k(t)=\mathrm{exp}((k1)t)\underset{j=0}{\overset{k_{max}k}{}}\frac{(2\mathrm{exp}(t)2)^j}{j!}\overline{P}_{k+j}(0),k=1,\mathrm{},k_{max}.$$
(89)
(c.f. ref. ) from which the mean asymptotic coverage follows straightforwardly:

$$c(\mathrm{})=\overline{P}_1(\mathrm{})=\underset{N\mathrm{}}{lim}\frac{\overline{N_A(\mathrm{})}}{N}=\underset{j=0}{\overset{k_{max}1}{}}\frac{(2)^j}{j!}\overline{P}_{j+1}(0).$$
(90)
This result is again in excellent agreement with MC simulations (Fig. 8(a) ). The coarse-grained solution of Eqs. (88) is formally obtained by setting $`k_{max}=\mathrm{}`$ and $`\overline{P}_j(0)=p^j`$. This yields

$`P_1(t)`$ $`=`$ $`p\mathrm{exp}[2p(\mathrm{exp}(t)1)],`$ (92)
$`P_k(t)`$ $`=`$ $`p^{k1}\mathrm{exp}\left[(k1)t\right]P_1(t),k=2,3,\mathrm{}`$ (93)
Thus, the corresponding stationary mean coverage takes the form

$$c(\mathrm{})=P_1(\mathrm{})=p\mathrm{exp}(2p)$$
(94)
Note that, contrary to the CPD case, the $`p`$-dependence of the asymptotic coverage is no longer monotonic. Thus, as long as $`p>0.5`$, $`c(\mathrm{})`$ increases when $`p`$ is decreased (Fig. 8(b) ). The initial situation of a fully occupied lattice ($`p=1`$) corresponds in random dimer deposition to an initially empty lattice. In this particular case, a famous combinatorial argument by Flory  predicts the value $`e^2`$ for the asymptotic mean fraction of empty sites (in our picture, occupied sites) at jamming, in accordance with the formula (94).

For the CTD system, it is also possible to derive a truncation hierarchy by introducing fluctuation correlations in Eqs. (82). Like in the CPD case, the second order hierarchy yields a MF steady state, in contradiction with the exact solution of (88). Once more, the reason for the failure is the nonnegligibility of the three-point correlations, some of which can be computed by solving the equation

$`{\displaystyle \frac{dP_{j,k}^{(l)}(t)}{dt}}`$ $`=`$ $`(j1)P_{j,k}^{(l)}(t)(k1)P_{j,k}^{(l)}(t)P_{j+1,k}^{(l1)}(t)`$ (96)
$`P_{j+1,k}^{(l)}(t)P_{j,k+1}^{(l)}(t)P_{j,k+1}^{(l1)}(t),j,k,l=1,2,\mathrm{}`$
which is also found in models for random dimer deposition . As shown in II D, the correlation functions $`P_{j,k}^{(l)}`$ can be used to set up explicit equations for the dynamics of vacant sites.

Finally, let us mention that it is possible to rederive the moment equations (82) and the hierarchy (88) from a ME analogous to Eq. (43).

## V Summary and outlook

We have developed a one-dimensional CA model which mimics the mesoscopic dynamics of two cooperative desorption reactions. An important advantage of this approach is that one directly sees the effect of a small modification of the MC algorithm on the underlying moment equations. The model allows us to derive a hierarchy of linear equations from which the mean particle coverage can be computed for both microscopic and coarse-grained initial conditions. We have seen that a truncation scheme retaining only pair fluctuation correlations fails to provide the correct behavior of these systems, due to the importance of higher order fluctuations. However, an alternative truncation based on neglecting the effect of large clusters in the dilute limit yields a smooth expansion of the cluster dynamics in powers of the initial coverage. In the case of the CTD, we have pointed out some analogies with models for dimer deposition.

The CDs studied here are relevant both from a theoretical and from an experimental point of view. Despite their simplicity, they exhibit a complex non-MF behavior characterized by nontrivial memory effects and spontaneous ordering. On the other hand, a wide number of physical processes on surfaces involve cooperative desorption of the products . In particular, several problems in the context of exciton dynamics in molecular cristals , recombination of condensed-gas radicals  and bond formation in polymers  can be mapped into the CDs. A classical example consists of a long polymer chain (methyl vynil ketone) formed by immobile radical groups which react with nearest neighbors so as to form rings when the chain is heated . Clearly, some groups will be isolated by the reaction dynamics and will remain unreacted. In the CTD model, the unreacted groups can be identified with the A particles and the rings correspond to pairs of vacancies left upon reaction. The quantity of interest, i.e., the fraction of unreacted groups, plays then the role of the lattice coverage $`\theta `$.

The effect of incorporating the backward reaction step $`S+AA+A`$ to the CPD has been studied in refs. . In this case, the mixing properties of the system are restored and one attains a MF steady state with equal number of empty and occupied sites. It would be desirable to extend the present study to the reversible CTD and also study the influence of an additional random particle input $`SA`$ on the CDs.

Another possible extension of our work consists of increasing the range of the local interactions by allowing, for instance, interactions with next to nearest neighbours. One expects that the system approaches the MF dynamics as the number of interacting neighbours increases. It is certainly worth to characterize this approach in a more quantitative way.

The dynamics of the one-dimensional CDs changes significantly in the diffusion limited case . One can account for the mobility of the particles by introducing additional diffusion terms in the dynamical rule. For the CPD, this has been done in ref.  for initial conditions of the form (29). As expected, diffusion yields an (anomalous) decay into a zero concentration steady state. The results in ref.  have been compared to an off-lattice solution by ben-Avraham et al. . Interestingly, the on-lattice solution displays a slower decay of the coverage for early times due to the finite propagation velocity of a local concentration perturbation on the lattice. A CA approach for the diffusion-limited CDs has been developed by Privman . In the Privman model, all lattice sites are synchronously updated at each time step. An extension of this model for the diffusionless CDs studied above is also worth carrying out.

A natural generalization of our calculations is to study the dynamics of the CDs on Bethe lattices of arbitrary dimension, for which results for the cluster dynamics derived heuristically by Majumdar and Privman (see ) are available. For the CPD, we expect to obtain results valid for physical lattices as well by extending some expansion methods developed in the framework of dimer deposition .

Finally, one would like to extend the boolean CA approach to three-state models accounting for the presence of more than one species and, more generally, to models displaying complex MF behavior like oscillations  and phase transitions .

## VI Acknowledgments

We are indebted to F. Baras, J.P. Boon, H.L. Frisch, A. Provata and F. Vikas for helpful discussions. This work was supported, in part, by the Training and Mobility of Researchers program of the European Commission and by the Interuniversity Attractions Poles program of the Belgian Federal Government.

## A The symmetric CPD

In this symmetric version of the CPD model, a particle at the chosen site looks either at the left or at the right neighbor site with equal probability and desorbs if the chosen neighbor is occupied. In this case, the dynamical rule reads:

$$n_i(t+\mathrm{\Delta }t)=n_i(t)\xi _N^{(i)}(t)\xi _R(t)n_i(t)\left\{\xi _L(t)n_{i1}(t)+(1\xi _L(t))n_{i+1}(t)\right\},i=1,\mathrm{},N.$$
(A1)
The additional decision variable $`\xi _L(t)`$ is equal to one if the left neighbour is chosen and zero otherwise. Clearly, the additional choice between left and right may change the global coverage in a realization characterized by a given path $`\{\stackrel{}{\xi }_N(0),\mathrm{},\stackrel{}{\xi }_N(t)\}`$. In contrast, one easily checks that averaging Eq. (A1) leads to the balance equations (22) and (28) valid for the asymmetric system. Clearly, the contributions to the destruction of a cluster by reactive events between two particles inside the cluster are the same in both models. In the asymmetric model, a cluster may also be destroyed by the choice of its rightmost particle, which will react with its right occupied neighbour with probability one. In contrast, this event will only take place with probability $`\frac{1}{2}`$ in the symmetric model, but there is an additional such contribution due to the reaction of the leftmost particle in the cluster with its left occupied neighbor. Therefore, both models will lead to the same balance equations for the cluster probabilities $`\overline{P}_k(t)`$ and $`P_k(t)`$. This conclusion is supported by comparison of MC simulations performed according to the rules (7) and (A1). A similar argument can be applied to the symmetric CTD.

## B Dynamics of particle islands

The definition of a particle cluster introduced in II C was nonexclusive, meaning that a cluster of a given size could contain smaller clusters. In the following, we will consider a more restrictive definition in which only isolated strings of particles are regarded as distinct clusters. These “particle islands” are characterized by the nonvanishing product

$$(1n_{i1}(t))\left[\underset{j=i}{\overset{i+k1}{}}n_j(t)\right](1n_{i+k}(t)),$$
(B1)
where $`k`$ is the size of the island. In a $`N`$-site periodic lattice, the total number of islands of size $`k`$ is given by

$$N_{I,k}(t)=\underset{i=1}{\overset{N}{}}(1n_{i1}(t))\left[\underset{j=i}{\overset{i+k1}{}}n_j(t)\right](1n_{i+k}(t)),$$
(B2)
and the total number of islands is $`N_I(t)=_{k=1}^{N1}N_{I,k}(t)`$ (the largest island can at most have $`N1`$ sites in the ring). With this definition, islands can only be created, never destroyed, even though its size may decrease in time. In order to create a new island at time $`t`$, an existing one must be split up by removal of an internal particle (not at the edge of an island). Therefore, the time evolution of $`N_I(t)`$ will be given by

$$N_I(t+\mathrm{\Delta }t)=N_I(t)+\underset{i=1}{\overset{N}{}}\xi _N^{(i)}(t)n_{i1}(t)n_i(t)n_{i+1}(t).$$
(B3)
In the limit $`t\mathrm{}`$, the iteration of this formula yields the total number of particles $`N_A(\mathrm{})`$ in the steady state:

$$N_A(\mathrm{})=N_I(\mathrm{})=N_I(0)+\underset{t=0}{\overset{\mathrm{}}{}}\underset{i=1}{\overset{N}{}}\xi _N^{(i)}(t)n_{i1}(t)n_i(t)n_{i+1}(t).$$
(B4)
The validity of this formula for the asymptotic coverage induced by a single realization can be easily checked numerically.

Following paragraph II D, we now consider an ensemble of realizations starting from the same initial condition. The probability to find an island of $`k`$ consecutive sites can be defined in a similar way to $`\overline{P}_k(t)`$:

$$\overline{I}_k^{(N)}(t)=\frac{\overline{N}_{I,k}(t)}{N}=\frac{1}{N}\underset{i=1}{\overset{N}{}}L_k^{(i)}(t),k=1,\mathrm{},N1.$$
(B5)
with

$$L_k^{(i)}(t)=\overline{(1n_{i1}(t))\underset{j=i}{\overset{i+k1}{}}n_j(t)(1n_{i+k}(t))}.$$
(B6)
After some algebra, one obtains

$$\overline{I}_k(t)=\overline{P}_k(t)2\overline{P}_{k+1}(t)+\overline{P}_{k+2}(t).$$
(B7)
Thus, once the solution for the set of $`\overline{P}_k(t)`$ is known, it is easy to determine the time evolution for the islands. A similar relation is found for coarse-grained initial conditions. In the continuous-time limit, one has:

$`I_k(t)`$ $`=(1n_{i1}(t)){\displaystyle \underset{j=i}{\overset{i+k1}{}}}n_j(t)(1n_{i+k}(t))`$ (B9)
$`=P_k(t)2P_{k+1}(t)+P_{k+2}(t)=[12p\mathrm{exp}(t)+p^2\mathrm{exp}(2t)]P_k(t).`$
Note that $`I_1(t)`$ increases monotonically in time, since the number of isolated particles always increases. The situation is less obvious for multiparticle islands (Fig. 9). If the initial coverage is high enough, their number will first be increased due to the breaking of larger islands, however they will sooner or later be themselves reduced to single-particle islands by the ongoing reactions.

The situation is slightly different in the CTD, since two-particle islands can indeed be destroyed. The evolution of $`N_I(t)`$ in a single realization is given by:

$`N_I(t+\mathrm{\Delta }t)`$ $`=N_I(t)+{\displaystyle \underset{i=1}{\overset{N}{}}}\xi _N^{(i)}(t)n_{i1}(t)n_i(t)n_{i+1}(t)n_{i+2}(t)`$ (B11)
$`{\displaystyle \underset{i=1}{\overset{N}{}}}\xi _N^{(i)}(t)(1n_{i1}(t))n_i(t)n_{i+1}(t)(1n_{i+2}(t)).`$
The first term describes the creation of a new island by reaction of two internal particles, while the second term stands for the destruction of a two-particle island. The total number of particles in the steady state can be written as

$$N_A(\mathrm{})=N_I(0)+\underset{t=0}{\overset{\mathrm{}}{}}\underset{i=1}{\overset{N}{}}\xi _N^{(i)}(t)n_i(t)n_{i+1}(t)(n_{i1}(t)+n_{i+2}(t)1).$$
(B12)
The dynamics of the islands can be easily determined by using the relations (B7) and (B9), which also hold in this case.