pith. sign in

arxiv: 2605.16904 · v1 · pith:LDBPFBV3new · submitted 2026-05-16 · 🧮 math.PR · cond-mat.stat-mech· math-ph· math.MP· nlin.CG

Positive-rate PCA and IPS with stationary Bernoulli measures are rapidly forgetful

Ir\`ene Marcovici , Siamak Taati This is my paper

Pith reviewed 2026-05-19 19:17 UTC · model grok-4.3

classification 🧮 math.PR cond-mat.stat-mechmath-phmath.MPnlin.CG
keywords probabilistic cellular automataexponential ergodicitymixing timesBernoulli measuresinteracting particle systemsentropy methods
0
0 comments X p. Extension
pith:LDBPFBV3 Add to your LaTeX paper What is a Pith Number? 
\usepackage{pith}
\pithnumber{LDBPFBV3}

Prints a linked pith:LDBPFBV3 badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more

The pith

Probabilistic cellular automata with strictly positive rates and a stationary Bernoulli measure are exponentially ergodic.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that any probabilistic cellular automaton with strictly positive transition probabilities that admits a stationary Bernoulli measure forgets its initial configuration at an exponential rate. This exponential ergodicity means correlations with the past decay exponentially in time. The mixing time needed for any finite region to become independent of its initial state grows only logarithmically with the diameter of that region. The same rapid forgetting holds for positive-rate finite-range interacting particle systems in continuous time. The argument treats the dynamics as a small perturbation of a fully noisy system and uses entropy to show that added randomness outruns the spread of local dependencies.

Core claim

Every probabilistic cellular automaton with strictly positive transition probabilities that admits a stationary Bernoulli measure is exponentially ergodic. Moreover, the mixing time of any finite region in such a system is logarithmic in the diameter of the region. A similar result holds in continuous time for positive-rate, finite-range interacting particle systems. The proofs use entropy, and rely on a representation of the system as a perturbation of another system with noise. The ergodic behaviour results from a competition between the accumulation of randomness due to noise and the diffusion of randomness due to local information exchange.

What carries the argument

Representation of the positive-rate PCA as a perturbation of an independent-noise system, tracked via entropy to quantify the competition between noise accumulation and local-information diffusion.

If this is right

  • Mixing time of any finite region scales logarithmically with its diameter.
  • The system is exponentially ergodic in every dimension.
  • In dimensions two and higher, positive-rate PCAs that admit stationary Bernoulli measures are algorithmically indistinguishable from those that do not.
  • Positive-rate finite-range interacting particle systems exhibit the same exponential ergodicity in continuous time.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Rapid mixing may make long-time statistics of these systems easier to sample by simulation.
  • The Bernoulli-measure condition could be close to necessary for exponential forgetting under strictly positive rates.
  • The entropy competition argument might extend to measures that are only approximately Bernoulli.

Load-bearing premise

The probabilistic cellular automaton admits a stationary Bernoulli measure.

What would settle it

A concrete positive-rate PCA that admits a stationary Bernoulli measure yet exhibits correlations decaying slower than any exponential rate, for example by direct computation of the two-point correlation function at large times.

read the original abstract

We prove that every probabilistic cellular automaton with strictly positive transition probabilities that admits a stationary Bernoulli measure is exponentially ergodic. Moreover, the mixing time of any finite region in such a system is logarithmic in the diameter of the region. A similar result holds in continuous time for positive-rate, finite-range interacting particle systems. The proofs use entropy, and rely on a representation of the system as a perturbation of another system with noise. The ergodic behaviour results from a competition between the accumulation of randomness due to noise and the diffusion of randomness due to local information exchange. We show that, in two and higher dimensions, the positive-rate probabilistic cellular automata that admit stationary Bernoulli measures are algorithmically indistinguishable from those that do not.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript proves that every probabilistic cellular automaton with strictly positive transition probabilities admitting a stationary Bernoulli measure is exponentially ergodic, with the mixing time of any finite region being logarithmic in the diameter of the region. Analogous results are established for positive-rate, finite-range interacting particle systems in continuous time. The proofs rely on entropy methods and a representation of the dynamics as a perturbation of a noisy system, quantifying the competition between randomness accumulation due to noise and diffusion due to local updates. In dimensions two and higher, positive-rate PCAs admitting stationary Bernoulli measures are shown to be algorithmically indistinguishable from those that do not.

Significance. If the central claims hold, the work advances the theory of ergodicity and rapid mixing for stochastic processes on lattices under positive rates. The entropy-perturbation framework provides a quantitative handle on the competition between noise and local information exchange, yielding the logarithmic mixing-time bound. The algorithmic indistinguishability result in higher dimensions is a natural and potentially useful consequence. The conditional nature of the result on the existence of a stationary Bernoulli measure is clearly stated and appropriate.

minor comments (3)
  1. The definition of the perturbation representation in the main proof could include an explicit statement of the noise strength parameter to make the entropy accumulation rate easier to track.
  2. Notation for the finite-region projections and their diameters is introduced in the mixing-time section but would benefit from a short forward reference in the statement of the main theorem.
  3. The discussion of algorithmic indistinguishability would be strengthened by a brief remark on the precise class of algorithms (e.g., local or finite-time) to which the result applies.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, assessment of significance, and recommendation of minor revision. No specific major comments were provided in the report, so we have no points to address individually at this stage. We will incorporate any minor editorial or presentational improvements in the revised manuscript.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper establishes exponential ergodicity and logarithmic mixing times for positive-rate probabilistic cellular automata and interacting particle systems that admit stationary Bernoulli measures. The central argument proceeds via an entropy-based analysis that represents the dynamics as a perturbation of a noisy reference system, quantifying the competition between noise-driven randomness accumulation and local-update diffusion. These steps rely on standard probabilistic estimates and coupling techniques rather than any self-definitional reduction, fitted-parameter renaming, or load-bearing self-citation. The result is conditional on the existence of the stationary Bernoulli measure and does not derive that measure from the ergodicity claim itself. Consequently the proof chain remains independent of its target conclusions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Review based on abstract only; the proof is said to use entropy and a perturbation representation of the system as a noisy process. No free parameters or invented entities are mentioned.

axioms (2)
  • standard math Standard properties of entropy and information theory for stochastic processes
    The proofs use entropy.
  • domain assumption The system admits a stationary Bernoulli measure
    The result applies to systems that admit such a measure.

pith-pipeline@v0.9.0 · 5660 in / 1150 out tokens · 54867 ms · 2026-05-19T19:17:12.895517+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

50 extracted references · 50 canonical work pages

  1. [1]

    Yu. K. Belyaev, Yu. I. Gromak, and V. A. Malyshev. Invariant random Boolean fields.Mathemati- cal Notes of the Academy of Sciences of the USSR, 6(5):792–799, 1969.doi:10.1007/bf01101406

    work page doi:10.1007/bf01101406 1969

  2. [2]

    C. H. Bennett. The thermodynamics of computation—a review.International Journal of Theo- retical Physics, 21(12):905–940, 1982.doi:10.1007/BF02084158

    work page doi:10.1007/bf02084158 1982

  3. [3]

    P. Caputo. Lecture notes on entropy and Markov chains, 2022. URL:http://www.mat.uniroma3. it/users/caputo/

    work page 2022

  4. [4]

    Caputo, Z

    P. Caputo, Z. Chen, Y. Gu, and Y. Polyanskiy. Entropy contractions in Markov chains: Half- step, full-step and continuous-time.Electronic Journal of Probability, 30, 2025.doi:10.1214/ 25-ejp1372

    work page 2025

  5. [5]

    Caputo, F

    P. Caputo, F. M¨ unch, and J. Salez. Entropy and curvature: Beyond the Peres-Tetali conjecture. Transactions of the American Mathematical Society, 378(5):3551–3571, 2025.doi:10.1090/tran/ 9395

    work page doi:10.1090/tran/ 2025

  6. [6]

    C ¸ apuni and P

    I. C ¸ apuni and P. G´ acs. A reliable Turing machine. Preprint, 2021.doi:10.48550/ARXIV.2112. 02152

    work page doi:10.48550/arxiv.2112 2021

  7. [7]

    T. M. Cover and J. A. Thomas.Elements of Information Theory. Wiley, 2nd edition, 2006. doi:10.1002/047174882X

    work page doi:10.1002/047174882x 2006

  8. [8]

    D. A. Dawson. Information flow in discrete Markov systems.Journal of Applied Probability, 10(1):63–83, 1973.doi:10.2307/3212496

    work page doi:10.2307/3212496 1973

  9. [9]

    D. A. Dawson. Information flow in one-dimensional Markov systems.Proceedings of the American Mathematical Society, 43(2):383–392, 1974.doi:10.1090/s0002-9939-1974-0336818-8

    work page doi:10.1090/s0002-9939-1974-0336818-8 1974

  10. [10]

    Information flow in graphs.Stochastic Processes and their Applications, 3(2):137– 151, 1975.doi:10.1016/0304-4149(75)90012-5

    D.A Dawson. Information flow in graphs.Stochastic Processes and their Applications, 3(2):137– 151, 1975.doi:10.1016/0304-4149(75)90012-5

    work page doi:10.1016/0304-4149(75)90012-5 1975

  11. [11]

    Fredes and J.-F

    L. Fredes and J.-F. Marckert. Invariant measures of interacting particle systems: Algebraic as- pects.ESAIM: Probability and Statistics, 24:526–580, 2020.doi:10.1051/ps/2020008

    work page doi:10.1051/ps/2020008 2020

  12. [12]

    G´ acs and J

    P. G´ acs and J. Reif. A simple three-dimensional real-time reliable cellular array.Journal of Computer and System Sciences, 36(2):125–147, 1988.doi:10.1016/0022-0000(88)90024-4

    work page doi:10.1016/0022-0000(88)90024-4 1988

  13. [13]

    Reliable computation with cellular automata.Journal of Computer and System Sciences, 32(1):15–78, 1986.doi:10.1016/0022-0000(86)90002-4

    Peter G´ acs. Reliable computation with cellular automata.Journal of Computer and System Sciences, 32(1):15–78, 1986.doi:10.1016/0022-0000(86)90002-4

    work page doi:10.1016/0022-0000(86)90002-4 1986

  14. [14]

    Reliable cellular automata with self-organization.Journal of Statistical Physics, 103(1–2):45–267, 2001.doi:10.1023/A:1004823720305

    Peter G´ acs. Reliable cellular automata with self-organization.Journal of Statistical Physics, 103(1–2):45–267, 2001.doi:10.1023/A:1004823720305

    work page doi:10.1023/a:1004823720305 2001

  15. [15]

    Guionnet and B

    A. Guionnet and B. Zegarlinksi.Lectures on Logarithmic Sobolev Inequalities, pages 1–134. Springer, 2003.doi:10.1007/978-3-540-36107-7_1. 22

    work page doi:10.1007/978-3-540-36107-7_1 2003

  16. [16]

    URLhttps://projecteuclid

    Y. Higuchi and T. Shiga. Some results on Markov processes of infinite lattice spin systems.Kyoto Journal of Mathematics, 15(1), 1975.doi:10.1215/kjm/1250523126

    work page doi:10.1215/kjm/1250523126 1975

  17. [17]

    R. Holley. Free energy in a Markovian model of a lattice spin system.Communications in Mathematical Physics, 23(2):87–99, 1971.doi:10.1007/bf01877751

    work page doi:10.1007/bf01877751 1971

  18. [18]

    R. A. Holley and D. W. Stroock. In one and two dimensions, every stationary measure for a stochastic Ising model is a Gibbs state.Communications in Mathematical Physics, 55(1):37–45, 1977.doi:10.1007/bf01613147

    work page doi:10.1007/bf01613147 1977

  19. [19]

    Jahnel and J

    B. Jahnel and J. K¨ oppl. On the long-time behaviour of reversible interacting particle systems in one and two dimensions.Probability and Mathematical Physics, 6(2):479–503, 2025.doi: 10.2140/pmp.2025.6.479

    work page doi:10.2140/pmp.2025.6.479 2025

  20. [20]

    Jahnel and C

    B. Jahnel and C. K¨ ulske. Attractor properties for irreversible and reversible interacting parti- cle systems.Communications in Mathematical Physics, 366(1):139–172, 2019.doi:10.1007/ s00220-019-03352-4

    work page 2019

  21. [21]

    J. Kari. Reversibility and surjectivity problems of cellular automata.Journal of Computer and System Sciences, 48(1):149–182, 1994.doi:10.1016/S0022-0000(05)80025-X

    work page doi:10.1016/s0022-0000(05)80025-x 1994

  22. [22]

    J. Kari. Reversible cellular automata: From fundamental classical results to recent developments. New Generation Computing, 36:145–172, 2018.doi:10.1007/s00354-018-0034-6

    work page doi:10.1007/s00354-018-0034-6 2018

  23. [23]

    J. Kari. Lecture notes on cellular automata, 2026. URL:https://users.utu.fi/jkari/

    work page 2026

  24. [24]

    Kari and S

    J. Kari and S. Taati. Conservation laws and invariant measures in surjective cellular automata. Discrete Mathematics & Theoretical Computer Science, DMTCS Proceedings vol. AP, Automata 2011 - 17th International Workshop on Cellular Automata and Discrete Complex Systems, 2011. doi:10.46298/dmtcs.2968

    work page doi:10.46298/dmtcs.2968 2011

  25. [25]

    Kari and S

    J. Kari and S. Taati. Statistical mechanics of surjective cellular automata.Journal of Statistical Physics, 160(5):1198–1243, 2015.doi:10.1007/s10955-015-1281-2

    work page doi:10.1007/s10955-015-1281-2 2015

  26. [26]

    J. F. C. Kingman.Poisson Processes. Oxford University Press, 1993

    work page 1993

  27. [27]

    Kozlov and N

    O. Kozlov and N. Vasilyev. Reversible Markov chains with local interaction. In R. L. Dobrushin and Ya. G. Sinai, editors,Multicomponent Random Systems, pages 451–469. Marcel Dekker, 1980

    work page 1980

  28. [28]

    K¨ unsch

    H. K¨ unsch. Non reversible stationary measures for infinite interacting particle systems.Zeitschrift f¨ ur Wahrscheinlichkeitstheorie und Verwandte Gebiete, 66(3):407–424, 1984.doi:10.1007/ bf00533706

    work page 1984

  29. [29]

    K˚ urka.Topological and Symbolic Dynamics, volume 11 ofCours Sp´ ecialis´ es

    P. K˚ urka.Topological and Symbolic Dynamics, volume 11 ofCours Sp´ ecialis´ es. Soci´ et´ e Math´ ematique de France, 2003

    work page 2003

  30. [30]

    Landauer, Irreversibility and heat generation in the computing process

    R. Landauer. Irreversibility and heat generation in the computing process.IBM Journal of Research and Development, 5(3):183–191, 1961.doi:10.1147/rd.53.0183

    work page doi:10.1147/rd.53.0183 1961

  31. [31]

    T. M. Liggett.Interacting Particle Systems. Springer, 1985.doi:10.1007/978-1-4613-8542-4

    work page doi:10.1007/978-1-4613-8542-4 1985

  32. [32]

    Mairesse and I

    J. Mairesse and I. Marcovici. Around probabilistic cellular automata.Theoretical Computer Science, 559:42–72, 2014.doi:10.1016/j.tcs.2014.09.009

    work page doi:10.1016/j.tcs.2014.09.009 2014

  33. [33]

    Mairesse and I

    J. Mairesse and I. Marcovici. Probabilistic cellular automata and random fields with i.i.d. di- rections.Annales de l’Institut Henri Poincar´ e, Probabilit´ es et Statistiques, 50(2), May 2014. doi:10.1214/12-aihp530

    work page doi:10.1214/12-aihp530 2014

  34. [34]

    Marcovici, M

    I. Marcovici, M. Sablik, and S. Taati. Ergodicity of some classes of cellular automata subject to noise.Electronic Journal of Probability, 24(41), 2019.doi:10.1214/19-EJP297

    work page doi:10.1214/19-ejp297 2019

  35. [35]

    Martinelli

    F. Martinelli. Lectures on Glauber dynamics for discrete spin models. In P. Bernard, editor, Lectures on Probability Theory and Statistics: Ecole d’Ete de Probabilites de Saint-Flour XXVII, pages 93–191. Springer, 1999.doi:10.1007/978-3-540-48115-7_2. 23

    work page doi:10.1007/978-3-540-48115-7_2 1999

  36. [36]

    K. Morita. Reversible computing and cellular automata—a survey.Theoretical Computer Science, 395(1):101–131, 2008.doi:10.1016/j.tcs.2008.01.041

    work page doi:10.1016/j.tcs.2008.01.041 2008

  37. [37]

    Morita and M

    K. Morita and M. Harao. Computation universality of one-dimensional reversible (injective) cellular automata.The Transactions of the IEICE, E72(6):758–762, 1989

    work page 1989

  38. [38]

    Moulin Ollagnier and D

    J. Moulin Ollagnier and D. Pinchon. Free energy in spin-flip processes is non-increasing.Com- munications in Mathematical Physics, 55(1):29–35, 1977.doi:10.1007/bf01613146

    work page doi:10.1007/bf01613146 1977

  39. [39]

    Dai Pra, P.-Y

    P. Dai Pra, P.-Y. Louis, and S. Rœlly. Stationary measures and phase transition for a class of probabilistic cellular automata.ESAIM: Probability and Statistics, 6:89–104, 2002.doi:10.1051/ ps:2002004

    work page 2002

  40. [40]

    Raginsky

    M. Raginsky. Strong data processing inequalities and Φ-Sobolev inequalities for discrete channels. IEEE Transactions on Information Theory, 62(6):3355–3389, 2016.doi:10.1109/tit.2016. 2549542

    work page doi:10.1109/tit.2016 2016

  41. [41]

    A. R´ enyi. On measures of entropy and information. InProceedings of the 4th Berkeley Symposium on Mathematical Statististics and Probability, pages 547–561. University of California Press, 1961

    work page 1961

  42. [42]

    W. G. Sullivan. Specific information gain for interacting Markov processes.Zeitschrift f¨ ur Wahrscheinlichkeitstheorie und Verwandte Gebiete, 37(1):77–90, 1976.doi:10.1007/bf00536299

    work page doi:10.1007/bf00536299 1976

  43. [43]

    J. M. Swart.A Course in Interacting Particle Systems. Cambridge University Press, To appear. doi:10.48550/ARXIV.1703.10007

    work page doi:10.48550/arxiv.1703.10007

  44. [44]

    S. Taati. Reversible cellular automata in presence of noise rapidly forget everything. InProceedings of AUTOMATA 2021, volume 90 ofOASIcs, pages 3:1–3:15. Schloss Dagstuhl, 2021.doi:10. 4230/OASICS.AUTOMATA.2021.3

    work page 2021

  45. [45]

    T. Toffoli. Computation and construction universality of reversible cellular automata.Journal of Computer and System Sciences, 15(2):213–231, 1977.doi:10.1016/S0022-0000(77)80007-X

    work page doi:10.1016/s0022-0000(77)80007-x 1977

  46. [46]

    Invertible cellular automata: A review.Physica D: Nonlinear Phenomena, 45(1–3):229–253, 1990.doi:10.1016/0167-2789(90)90185-R

    Tommaso Toffoli and Norman Margolus. Invertible cellular automata: A review.Physica D: Nonlinear Phenomena, 45(1–3):229–253, 1990.doi:10.1016/0167-2789(90)90185-R

    work page doi:10.1016/0167-2789(90)90185-r 1990

  47. [47]

    A. L. Toom, N. B. Vasilyev, O. N. Stavskaya, L. G. Mityushin, G. L. Kuryumov, and S. A. Pirogov. Discrete local Markov systems. In R. L. Dobrushin, V. I. Kryukov, and A. L. Toom, editors,Stochastic cellular systems: ergodicity, memory, morphogenesis. Manchester University Press, 1990

    work page 1990

  48. [48]

    L. N. Vaserstein. Markov processes over denumerable products of spaces, describing large systems of automata.Problems Informormation Transmission, 5(3):47–52, 1969

    work page 1969

  49. [49]

    N. B. Vasilyev. Bernoulli and Markov stationary measures in discrete local interactions. In R. L. Dobrushin, V. I. Kryukov, and A. L. Toom, editors,Locally Interacting Systems and Their Application in Biology, pages 99–112. Springer, 1978.doi:10.1007/BFb0070087

    work page doi:10.1007/bfb0070087 1978

  50. [50]

    von Neumann

    J. von Neumann. Probabilistic logics and the synthesis of reliable organisms from unreliable com- ponents. In C. E. Shannon and J. McCarthy, editors,Automata Studies, pages 43–98. Princeton University Press, 1956.doi:10.1515/9781400882618. I. Marcovici Universit´e de Rouen Normandie, LMRS, 76801 Saint- ´Etienne-du-Rouvray, France. E-mail address:irene.mar...

    work page doi:10.1515/9781400882618 1956