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

An easy question that I have never been able to answer. Suppose we have the CA on $\{ 0,1,2 \}^{\mathbb{N}}$ with local rule given by $f(x,y)=A_{x,y}$ and $A$ the $3\times 3$ matrix $A=(0,1,2,0,1,2,1,2,0).$ For example $(0,1,2,0,0,0,1,2,0,\ldots)\mapsto (1,2,1,0,0,1,2,1,\ldots),$ It is like a shift if the coordinate before is $0$ or $1$ and $x+1$ mod 3 if not. My question is, are there any invariant probability measures full supported other that the Haar measure? I have never seen an idea to solve this problem, so any reference is welcome.

share|cite|improve this question
What about a measure with all weight given to $(0,0,0,\ldots)$? – Yoav Kallus Feb 8 '13 at 19:02
A nice geometric interpretation of the problem could be great. – Umberto Feb 8 '13 at 20:08
If I understand you correctly then the action of this system on the closed subset $\{0,1\}^{\mathbb{N}}$ is simply the shift, so this system admits a host of shift-invariant ergodic measures supported on $\{0,1\}^{\mathbb{N}}$. Or do you want the measure to be fully supported? – Ian Morris Feb 8 '13 at 22:14
Could you explain in more detail how the local rules are defined in terms of the matrix $A$? – R W Feb 8 '13 at 23:46
@R W: I think that if you have x followed by y, then you must take the x+1-st row of the matrix and the y+1-st column of it to get the new value of x. – domotorp Feb 9 '13 at 19:13
up vote 1 down vote accepted

This problem is easy, but there is a related problem that is not, this is to find a fully supported invariant measure for our CA that is at the same time invariant for the action of the shift different from the Haar measure. Is this possible?

To solve the problem here we can do the following. Call our CA by $F.$ $F$ is clearly surjective, then by a result by Hedlund every cylinder set has 3 preimages.

We will find an invariant measure for $F$ by defining recursively in $k$ the measure on the cylinder sets with coordinates fixed $0,1,\ldots,k,$ then we will extend the measure using Komogorov as usual. Define for $i\in \{0,1,2\}$ define $[i]_0=\{ i\}\times \{0,1,2\}^{\mathbb{N}}.$

For $k=1,2,\ldots$ suppose $F^{-k}[i]_0=\{a_i^{1}(k),a_i^{2}(k),\ldots,a_i^{3^{k}}(k)\},$ for example ordered by the lexicographic order. We will define inductively in $k$ the values $\mu(a_i^{j}(k))\doteq p_{i}^{j}(k)\in (0,1).$

Choose $p_0^{1}(0),p_1^{1}(0),p_2^{1}(0)>0$ such that $p_0^{1}(0)+p_1^{1}(0)+p_2^{1}(0)=1.$ Define $\mu([i]_0)=p_i^{1}(0).$

Suppose we have defined $\mu$ in $F^{-k}[i]_0.$ Given $j=1,2,\ldots,3^{k}$ we find $j_1,j_2,j_3$ such that $F(a_i^{j_1}(k+1))=F(a_i^{j_2}(k+1))=F(a_i^{j_3}(k+1))=a_i^{j}(k)$ (the evaluation of $F$ on cylinder sets has the obvious meaning) choose $p_i^{j_1}(k+1),p_i^{j_2}(k+1),p_i^{j_3}(k+1)>0$ such that $p_i^{j_1}(k+1)+p_i^{j_2}(k+1)+p_i^{j_3}(k+1)=p_i^{j}(k).$

Clearly we have defined in such a way an $F$-invariant probability measure, however not necessarily shift invariant.

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.