Convergence Time and Phase Transition in a Non-monotonic Family of Probabilistic Cellular Automata

In dynamical systems, some of the most important questions are related to phase transitions and convergence time. We consider a one-dimensional probabilistic cellular automaton where their components assume two possible states, zero and one, and interact with their two nearest neighbors at each time step. Under the local interaction, if the component is in the same state as its two neighbors, it does not change its state. In the other cases, a component in state zero turns into a one with probability \(\alpha ,\) and a component in state one turns into a zero with probability \(1-\beta \). For certain values of \(\alpha \) and \(\beta \), we show that the process will always converge weakly to \(\delta _{0},\) the measure concentrated on the configuration where all the components are zeros. Moreover, the mean time of this convergence is finite, and we describe an upper bound in this case, which is a linear function of the initial distribution. We also demonstrate an application of our results to the percolation PCA. Finally, we use mean-field approximation and Monte Carlo simulations to show coexistence of three distinct behaviours for some values of parameters \(\alpha \) and \(\beta \).     

Large Deviations for Probabilistic Cellular Automata

We consider a generalized model of a probabilistic cellular automata described by a Markov chain on an infinite dimensional space and derive certain large deviations bounds for corresponding occupational measures.     

Large Deviations for Probabilistic Cellular Automata II

We obtain an upper large deviations bound which shows that for some models of probabilistic cellular automata (which are far away from the product case) the lower large deviation bound derived in Eizenberg and Kifer J. Stat. Phys. 108: 1255–1280 (2002) is sharp, and so the corresponding large deviations phenomena cannot be described via the traditional Donsker–Varadhan form of the action functional. For models which are close to the product case we derive approximate large deviations bounds using the Donsker–Varadhan functional for the product case.     

Critical Percolation Probabilities for the Next-Nearest-Neighbouring Site Problems on Sierpinski Carpets

In this paper, we compute the next-nearest-neighbouring site percolation (Connections exist not only between nearest-neighbouring sites, but also between next-nearest-neigh bouring sites.) probabilities PC on the two-dimensional Sierpinski carpets, using the translationaldilation method and Monte Carlo technique. We obtain a relation among PC, fractal dimensionality D and connectivity Q. For the family of carpets with central cutouts,(1 - P_c)/(1 - P_c^s) = (D - 1)^1.60, where P_c^s = 0.41, the critical percolation probability for the next-nearest-neighbouring site problem on square lattice. As D reaches 2, P_c = P_c^s = 0.41, which is in agreement with the critical percolation probability on 2-d square lattices with . next-nearest-neigh bouring interactions.     

Self-Duality for Multi-State Probabilistic Cellular Automata with Finite Range Interactions

In this paper we study a criterion of self-duality for multi-state probabilistic cellular automata with finite range interactions and give some models which satisfy this criterion.     

Exponential Decay of Correlations for Strongly Coupled Toom Probabilistic Cellular Automata

We investigate the low-noise regime of a large class of probabilistic cellular automata, including the North-East-Center model of Toom. They are defined as stochastic perturbations of cellular automata belonging to the category of monotonic binary tessellations and possessing a property of erosion. We prove, for a set of initial conditions, exponential convergence of the induced processes toward an extremal invariant measure with a highly predominant spin value. We also show that this invariant measure presents exponential decay of correlations in space and in time and is therefore strongly mixing.     

Invariant Measures and Decay of Correlations for a Class of Ergodic Probabilistic Cellular Automata

We give new sufficient ergodicity conditions for two-state probabilistic cellular automata (PCA) of any dimension and any radius. The proof of this result is based on an extended version of the duality concept. Under these assumptions, in the one dimensional case, we study some properties of the unique invariant measure and show that it is shift-mixing. Also, the decay of correlation is studied in detail. In this sense, the extended concept of duality gives exponential decay of correlation and allows to compute explicitly all the constants involved.     

Dualities for a Class of Finite Range Probabilistic Cellular Automata in One Dimension

In this paper we study dualities for a class of one-dimensional probabilistic cellular automata with finite range interactions by using a sequence of extended cellular automata.     

Renormalization of Cellular Automata and Self-Similarity

We study self-similarity in one-dimensional probabilistic cellular automata (PCA) using the renormalization technique. We introduce a general framework for algebraic construction of renormalization groups (RG) on cellular automata and apply it to exhaustively search the rule space for automata displaying dynamic criticality.     

Probabilistic Deterministic Finite Automata and Recurrent Networks,Revisited

Reservoir computers (RCs) and recurrent neural networks (RNNs) can mimic any finite-state automaton in theory, and some workers demonstrated that this can hold in practice. We test the capability of generalized linear models, RCs, and Long Short-Term Memory (LSTM) RNN architectures to predict the stochastic processes generated by a large suite of probabilistic deterministic finite-state automata (PDFA) in the small-data limit according to two metrics: predictive accuracy and distance to a predictive rate-distortion curve. The latter provides a sense of whether or not the RNN is a lossy predictive feature extractor in the information-theoretic sense. PDFAs provide an excellent performance benchmark in that they can be systematically enumerated, the randomness and correlation structure of their generated processes are exactly known, and their optimal memory-limited predictors are easily computed. With less data than is needed to make a good prediction, LSTMs surprisingly lose at predictive accuracy, but win at lossy predictive feature extraction. These results highlight the utility of causal states in understanding the capabilities of RNNs to predict.     

Reversibility Problem of Multidimensional Finite Cellular Automata

While the reversibility of multidimensional cellular automata is undecidable and there exists a criterion for determining if a multidimensional linear cellular automaton is reversible, there are only a few results about the reversibility problem of multidimensional linear cellular automata under boundary conditions. This work proposes a criterion for testing the reversibility of a multidimensional linear cellular automaton under null boundary condition and an algorithm for the computation of its reverse, if it exists. The investigation of the dynamical behavior of a multidimensional linear cellular automaton under null boundary condition is equivalent to elucidating the properties of the block Toeplitz matrix. The proposed criterion significantly reduces the computational cost whenever the number of cells or the dimension is large; the discussion can also apply to cellular automata under periodic boundary conditions with a minor modification.     

Continuum Nonsimple Loops and 2D Critical Percolation

Substantial progress has been made in recent years on the 2D critical percolation scaling limit and its conformal invariance properties. In particular, chordal SLE ₆(the Stochastic Loewner Evolution with parameter κ=6) was, in the work of Schramm and of Smirnov, identified as the scaling limit of the critical percolation “exploration process.” In this paper we use that and other results to construct what we argue is the fullscaling limit of the collection of allclosed contours surrounding the critical percolation clusters on the 2D triangular lattice. This random process or gas of continuum nonsimple loops in Bbb R²is constructed inductively by repeated use of chordal SLE ₆. These loops do not cross but do touch each other—indeed, any two loops are connected by a finite “path” of touching loops.     

Factorization of Combinatorial R Matrices and Associated Cellular Automata

Solvable vertex models in statistical mechanics give rise to soliton cellular automata at q=0 in a ferromagnetic regime. By means of the crystal base theory we study a class of such automata associated with non-exceptional quantum affine algebras U′ $_q$ ( $\widehat {\mathfrak{g}}$ $_n$ ). Let B $_l$ be the crystal of the U′ $_q$ ( $\widehat {\mathfrak{g}}$ $_n$ )-module corresponding to the l-fold symmetric fusion of the vector representation. For any crystal of the form B = $B_{l_1 }$ ? ...? $B_{l_N }$ , we prove that the combinatorial R matrix B $_M$ ?B $\widetilde \to$ B?B $_M$ is factorized into a product of Weyl group operators in a certain domain if M is sufficiently large. It implies the factorization of certain transfer matrix at q=0, hence the time evolution in the associated cellular automata. The result generalizes the ball-moving algorithm in the box-ball systems.     

Probabilistic Cloning of Three Real States with Optimal Success Probabilities

We investigate the probabilistic quantum cloning (PQC) of three real states with average probability distribution. To get the analytic forms of the optimal success probabilities we assume that the three states have only two pairwise inner products. Based on the optimal success probabilities, we derive the explicit form of 1 →2 PQC for cloning three real states. The unitary operation needed in the PQC process is worked out too. The optimal success probabilities are also generalized to the M→N PQC case.     

Continuity of Information Transport in Surjective Cellular Automata

We introduce a local version of the Shannon entropy in order to describe information transport in spatially extended dynamical systems, and to explore to what extent information can be viewed as a local quantity. Using an appropriately defined information current, this quantity is shown to obey a local conservation law in the case of one-dimensional reversible cellular automata with arbitrary initial measures. The result is also shown to apply to one-dimensional surjective cellular automata in the case of shift-invariant measures. Bounds on the information flow are also shown.     

Strict Inequalities of Critical Values in Continuum Percolation

We consider the supercritical finite-range random connection model where the points x,y of a homogeneous planar Poisson process are connected with probability f(|y−x|) for a given f. Performing percolation on the resulting graph, we show that the critical probabilities for site and bond percolation satisfy the strict inequality $p_{c}^{\mathrm{site}} > p_{c}^{\mathrm{bond}}$p_{c}^{\mathrm{site}} > p_{c}^{\mathrm{bond}}. We also show that reducing the connection function f strictly increases the critical Poisson intensity.