# An Improved Lower Bound for the Critical Parameter of the Stavskaya's Process via a Generalized Recurrent Method

Olivier Couronné

► To cite this version:

Olivier Couronné. An Improved Lower Bound for the Critical Parameter of the Stavskaya's Process via a Generalized Recurrent Method. 2025. hal-05138055

HAL Id: hal-05138055

https://hal.science/hal-05138055v1

Preprint submitted on 1 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# AN IMPROVED LOWER BOUND FOR THE CRITICAL PARAMETER OF THE STAVSKAYA'S PROCESS VIA A GENERALIZED RECURRENT METHOD

OLIVIER COURONNÉ

**Abstract.** Stavskaya's process, a discrete-time version of the contact process on $\mathbb{Z}$, is known to exhibit a phase transition at a critical parameter $\alpha^*$ whose exact value remains an open problem. Recent work by Ramos et al. established a lower bound by linking the process's survival to the non-percolation of a dual contour. The probability of this contour was estimated using a recurrent method on a state space of weighted random walks with short-term memory. In this paper, we generalize and extend this method by systematically increasing the walk's memory and enriching the set of forbidden path sequences. By increasing the memory up to a length of 20 steps (corresponding to our parameter $n = 7$), we formulate the problem with a one-step transition matrix and numerically optimize its spectral radius. We thus establish the new lower bound $\alpha^* > 0.1370721$.

## 1. INTRODUCTION

The Stavskaya's process is a one-dimensional probabilistic cellular automaton, often considered the discrete-time analogue of the well-known contact process. The system evolves on the integer lattice $\mathbb{Z}$, with each site being in state 0 (vacant) or 1 (occupied). The dynamics are governed by a parameter $\alpha \in [0, 1]$, which represents the probability for an occupied site to become vacant.

The process exhibits a well-established phase transition at a critical parameter $\alpha^* \in (0, 1)$. For $\alpha > \alpha^*$, the process is ergodic and converges to the "all-0" configuration. For $\alpha < \alpha^*$, a non-trivial stationary measure exists, and the process started from the "all-1" configuration survives with positive probability. While the existence of $\alpha^*$ is known, its exact value remains an open problem. Rigorous bounds were first established by Toom [2].

Ramos et al. [1] recently revisited this problem using a powerful duality argument. They mapped the survival of the process to the absence of an open contour in a dual graph. The probability of such a contour was bounded by summing the weights of all "nice paths" on this dual lattice. In their work, paths were deemed "nice" if they avoided a small set of short forbidden sequences. This approach, based on a recurrence relation for paths with a two-step memory, yielded a lower bound of $\alpha^* > 0.11$.

In this work, we build upon and generalize this recurrent method. The precision of the bound is fundamentally limited by the "memory" of the random walk used to model the contours. By increasing this memory and introducing more sophisticated forbidden patterns, we can capture the process's correlations more accurately, leading to a tighter bound. Our main contribution is to generalize the method as a function of an integer $n \ge 1$, where the walk's memory has length $3n - 1$ and where we systematically forbid all primitive loops of length up to $3n$. This generalization unifies the approach and makes it adaptable to the available computational power.

Our main result, obtained through numerical optimization for the case $n = 7$, is the following theorem.

**Theorem 1.1.** *The critical parameter $\alpha^*$ of the one-dimensional Stavskaya's process satisfies*

$$ \alpha^* > 0.1370721. $$

The remainder of this paper details the methodology. In Section 2, we define the generalized recurrent method, including the state space and the construction of the transition matrix as a function of the parameter $n$. Section 3 describes the numerical procedure used to find the optimal bound and presents the results for different values of $n$. We conclude in Section 4.

*Date:* July 1, 2025.

2020 Mathematics Subject Classification. 60K35.

*Key words and phrases.* Particle Random Process; Stavskaya's Process.

The author is supported by the Labex MME-DII funded by ANR, reference ANR-11-LBX-0023-01, and this research has been conducted within the FP2M federation (CNRS FR 2036).
## 2. THE GENERALIZED RECURRENT METHOD

We follow the framework of [1], which itself builds on the method of Toom [2], where the probability of the process dying out is bounded by the probability of forming a specific type of contour on a dual lattice. This probability is bounded by the sum of weights of all valid contour paths.

In the original method, this sum of path weights is analyzed using a system of generating functions. They defined quantities $S_r(k)$ representing the total weight of all valid paths of length $k$ that terminate with a specific move $r$. The weights are functions of the process parameter $\alpha$ and two auxiliary real parameters, $p, q \ge 1$. The analysis then relies on deriving a system of linear recurrence relations that connect these sums at different lengths (e.g., expressing sums at length $k+2$ in terms of sums at length $k$). The convergence of the total sum is then determined by the properties of this system of recurrences.

Our approach generalizes this concept. Instead of tracking the sums based on the last step, we define a comprehensive state space where each state represents a much longer path history. This allows us to reframe the problem: the complex, multi-step recurrence relations of the original method become a simple one-step linear transformation governed by a large transition matrix $M_n$. The condition for convergence then translates to the spectral radius of this matrix being less than one. The core of our new approach is to systematically generalize and refine the definition of a "valid" path history to construct this matrix.

### 2.1. Paths, Weights, and Primitive Loops.
On the dual graph, a path is a sequence of steps. The three possible step types have a weight that depends on the parameters $p, q \ge 1$ and $\alpha$:

* Step 1 (displacement $(-1, -1)$): weight $p^{-1}q^{-1}$

* Step 2 (displacement $(+2, 0)$): weight $\alpha p^2$

* Step 3 (displacement $(-1, +1)$): weight $qp^{-1}$

A key insight of the contour method is that not all sequences of steps form valid contours. Following Toom [2] and Ramos et al. [1], we identify two types of forbidden patterns.

First, the sequences $(1, 3)$ and $(3, 1)$ are forbidden.

Second, we exclude all closed loops. Given the vector displacements of the three step types, a path returns to its origin—thereby forming a closed loop—if and only if it is "balanced," meaning it contains an equal number of steps of type 1, 2, and 3.

**Definition 2.1.** A loop of order $k$ is a path of length $3k$ containing exactly $k$ instances of each step type $\{1, 2, 3\}$. A loop of order $k$ is said to be primitive if it does not contain a primitive loop of order $j < k$ as a contiguous subpath.

The set of forbidden patterns $\mathcal{F}_n$ for a level $n$ consists of:

(1) The patterns $(1, 3)$ and $(3, 1)$.

(2) All primitive balanced loops of order $k$, for $1 \le k \le n$.

For example, for $n = 1$, $\mathcal{F}_1$ contains the degenerate loops $(1, 3)$ and $(3, 1)$, as well as the primitive loops of order 1: $(1, 2, 3)$ and $(3, 2, 1)$. This set of patterns corresponds exactly to the forbidden sequences used in the analysis by Ramos et al. [1].

For $n = 2$, we add the 2 primitive loops of order 2, that is $(1, 1, 2, 2, 3, 3)$ and $(3, 3, 2, 2, 1, 1)$.

### 2.2. State Space and Transition Matrix.
For a level $n$, we define a state space based on a memory of the last $L = 3n - 1$ steps.

**Definition 2.2 (State Space).** For a level $n$, the state space $S_n$ is the set of all paths of length $L = 3n - 1$ that do not contain any primitive loop from $\mathcal{F}_{n-1}$ as a subpath.

Let $S(k)$ be a column vector where each entry $S_w(k)$ is the sum of weights of all valid paths of length $k$ ending in the state $w \in S_n$. A path of length $k+1$ is formed by appending a new move $j \in \{1, 2, 3\}$ to a valid path of length $k$. This transition is allowed only if the resulting sequence at the tail of the path does not create any forbidden pattern.

The evolution of the weighted path counts is described by a one-step linear transformation:

$$ (1) \qquad S(k+1) = M_n(p, q, \alpha)S(k), $$

where $M_n(p, q, \alpha)$ is the transition matrix of size $|S_n| \times |S_n|$. To make the dependence on the parameters explicit, we can decompose $M_n$ into three base matrices. Each base matrix, $M^{(j)}$, exclusively represents the
valid transitions ending with the specific move $j \in \{1, 2, 3\}$:

$$ (2) \qquad \mathbf{M}_n(p, q, \alpha) = \frac{1}{pq} \mathbf{M}^{(1)} + (\alpha p^2) \mathbf{M}^{(2)} + \frac{q}{p} \mathbf{M}^{(3)}. $$

Here, $\mathbf{M}^{(j)}$ for $j \in \{1, 2, 3\}$ are sparse matrices with entries of 0 or 1.

An entry $M_{w',w}$ is non-zero if and only if state $w'$ can be obtained from state $w$ by appending a valid move $j$. More formally, if $w = (w_1, \dots, w_L)$, a transition to $w' = (w_2, \dots, w_L, j)$ is valid if the extended path $(w_1, \dots, w_L, j)$ of length $3n$ does not contain any pattern from $\mathcal{F}_n$ as a suffix. If the transition is valid, $M_{w',w}$ takes the value of the weight of the new move $j$.

### 3. NUMERICAL OPTIMIZATION AND RESULTS

The total probability of a contour existing converges if the spectral radius of the transition matrix, $\rho(\mathbf{M}_n)$, is less than 1. Our goal is to find the largest value of $\alpha$ for which we can find parameters $p, q \ge 1$ that satisfy this condition.

$$ (3) \qquad \alpha^* \ge \sup_{n \ge 1} \sup_{\substack{p \ge 1 \\ q \ge 1}} \sup \{\alpha \in [0, 1] \mid \rho(\mathbf{M}_n(p, q, \alpha)) < 1\}. $$

Our numerical explorations indicated that the maximum is achieved along the line $q = 1$. The optimization was therefore reduced to a one-dimensional search over $p$.

For a fixed $p$ (and $q = 1$), our goal is to find the supremum of the set of all $\alpha$ values for which the condition $\rho(\mathbf{M}_n(p, 1, \alpha)) < 1$ is satisfied. We denote this supremum as $\alpha_c(p)$.

Numerically, we approximate $\alpha_c(p)$ using a bisection search. The search iteratively narrows down an interval $[\text{low}, \text{high}]$ for $\alpha$. At each step, a midpoint mid is tested. If $\rho(\mathbf{M}_n(p, 1, \text{mid})) < 1$, we know that mid is a valid lower bound, so we set low = mid. Otherwise, we set high = mid. This process converges to a highly accurate estimate of $\alpha_c(p)$ while ensuring that the final low value always corresponds to a spectral radius less than 1.

The best lower bound for $\alpha^*$ is then the maximum value found over our search space for $p$:

$$ \alpha^* > \sup_{p \ge 1} \alpha_c(p). $$

The numerical procedure for a fixed $n$ is as follows:

(1) Generate the set of primitive loops $\mathcal{F}_n$.

(2) Construct the state space $S_n$ and the base transition matrices.

(3) For each value of $p$ in a search grid (with $q = 1$):

(a) Approximate the supremum $\alpha_c(p)$ of the set $\{\alpha \mid \rho(\mathbf{M}_n(p, 1, \alpha)) < 1\}$ using a bisection search with a tolerance of $10^{-10}$.

(4) The best lower bound for $\alpha^*$ at level $n$ is the maximum value found over the grid, $\max_p \alpha_c(p)$.

The results of this procedure for increasing values of $n$ are presented in Table 1. We observe of course an improvement in the lower bound, at the cost of an exponential growth in the size of the state space.

<table><caption>TABLE 1. Lower bounds for $\alpha^*$ as a function of the level $n$.</caption><thead><tr><th>n</th><th>Primitive Loops</th><th>State Space Size</th><th>$p_{opt}$</th><th>Lower Bound for $\alpha^*$</th></tr></thead><tbody><tr><td>1</td><td>4</td><td>7</td><td>1.464</td><td>0.125</td></tr><tr><td>2</td><td>6</td><td>73</td><td>1.44</td><td>0.131 019 66</td></tr><tr><td>3</td><td>12</td><td>759</td><td>1.43</td><td>0.133 586 60</td></tr><tr><td>4</td><td>36</td><td>7,859</td><td>1.424</td><td>0.135 028 55</td></tr><tr><td>5</td><td>146</td><td>81,231</td><td>1.42</td><td>0.135 953 42</td></tr><tr><td>6</td><td>694</td><td>839,009</td><td>1.417</td><td>0.136 597 47</td></tr><tr><td>7</td><td>3584</td><td>8,663,071</td><td>1.415</td><td>0.137 072 11</td></tr></tbody></table>

Note: The "State Space Size" column corresponds to $|S_n|$. $p_{opt}$ is the value of $p$ that maximizes the bound for $q = 1$.

The search for $n = 7$ yields our main result. The optimal value was found for parameters $p = 1.415$ and $q = 1.0$.
4. CONCLUSION

By generalizing the recurrent method of Ramos et al., we have developed a systematic framework for improving the lower bound of the critical parameter of the Stavskaya's process. By increasing the memory of the random walk and refining the set of forbidden paths through the algorithmic exclusion of primitive loops, we have established a new lower bound of $\alpha^* > 0.1370721$.

This work demonstrates the power of the dual contour method when combined with a more detailed state representation and numerical optimization. The framework is general and can be applied with even larger memory lengths ($n > 7$), which would yield further improvements. However, the exponential growth in the size of the state space, visible in Table 1, constitutes a major computational bottleneck, suggesting that future gains from this approach alone will be increasingly costly to obtain.

REFERENCES

[1] A. D. Ramos, C. S. Sousa, P. M. Rodríguez, and P. Cadavid. *An improved lower bound for the critical parameter of Stavskaya's process*. Bulletin of the Australian Mathematical Society, 102(3):517-524, 2020.

[2] A. Toom, N. Vasilyev, O. Stavskaya, L. Mityushin, G. Kurdyumov, and S. Pirogov. *Stochastic Cellular Systems: ergodicity, memory, morphogenesis*. Edited by R. Dobrushin, V. Kryukov, and A. Toom. Series in Nonlinear Science: Theory and Applications. Manchester University Press, 1990.

UNIVERSITÉ PARIS NANTERRE, 200 AVENUE DE LA RÉPUBLIQUE 92000 NANTERRE, FRANCE, MODAL'X, FP2M, CNRS FR 2036.

Email address: olivier.couronne@parisnanterre.fr