Take the tour ×

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|improve this question
In the question: "the stochastic procecess IS ergodic" –  Lorenzo Sep 26 '12 at 8:23
in the title, "a probabilistic cellular AutomatON" –  Igor Rivin Sep 26 '12 at 14:39
add comment

2 Answers

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer


