MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let's consider a Probabilistic Cellular Automaton on a one dimensional lattice $S$. Each site of the lattice can have two states, $0$ and $1$. The transition probability acting on each site is: $P(x_i=1 | x_{i-1}, x_i, x_{i+1}) = 1$ when $x_{i-1}= x_i = x_{i+1} = 1$ and it is $P(x_i=1 | x_{i-1}, x_i, x_{i+1}) = \epsilon$ otherwise.

How can I proove that if $S$ is finite (in particular in my case it is the one dimensional chain from site $-N$ to $N$ with periodic boundary condition) then the stochastic process is ergodic for any value of $\epsilon$?

For ergodic I mean that "from any initial probability distribution, the system always converge on the same invariant measure".

The invariant measure, in this case, is obviously the one which gives weight "$1$" to the configuration $1, 1, 1, \ldots 1$. Then one should just proove that the probability to get in any site $i$ the state $1$ at time $T$, $P_T(x_i=1)$, converges to $1$ for $T \rightarrow \infty$. But I cannot formalize how to see this.

share|cite|improve this question
In the question: "the stochastic procecess IS ergodic" – QuantumLogarithm Sep 26 '12 at 8:23
in the title, "a probabilistic cellular AutomatON" – Igor Rivin Sep 26 '12 at 14:39
up vote 5 down vote accepted

Define a random variable $Y\in \{0,1\}^N$ by $P(y_i^{(n)}=1) = \epsilon$ for all $1\leq i\leq N$ and $n\in\mathbb{N}$ and observe that $x_i^{(n)} \geq y_i^{(n)}$ for all $i,n$ (as long as $X,Y$ are being driven by the same random process). With probability 1 there exists a time $n$ such that $y_i^{(n)}=1$ for all $i$ (since all the events are independent and the lattice is finite), and then from this time on $X$ is in the state where every $x_i=1$.

share|cite|improve this answer

The point $x=(1,1,\dots,1)$ is an absorbing state, and $p(y,x)$ is bounded away from 0 for any other state $y$. The only stationary measure of any countable Markov chain with this property is $\delta_x$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.