The behaviour of cellular automata on a random input, as most models of computation, can be highly complex and the possible type of behaviours (limit measures, etc.) is only limited by computability restrictions. The behaviour of surjective cellular automata on a random input, on the other hand, is much more controlled and governed by its dynamics and combinatorics. A simple example is the well-known fact that the uniform probability measure is invariant under any surjective cellular automata.

A question that remains open is whether, given a simple initial probability measure where every pattern appears with positive probability (e.g. each cell picks a color independently), it is possible that the probability for some pattern tends to zero when iterating a surjective cellular automata.

We provide some partial results and failures that resulted from a collaboration with Ilkka Tôrma and Ville Salo aiming to tackle this question, giving positive answers when relaxing some of the hypotheses.