Consider probability measures $\mu$ on the space $\{0,1\}^\mathbb{N}$ that are shift-invariant with respect to the left-shift map.
Is there a nice characterization of the ergodic shift-invariant measures?
I know that the ergodic measures are the extremal points in the set of shift-invariant measures. However, I wouldn't call this a nice characterization.
As an example of a nice characterization, we know by de Finetti's theorem that the ergodic measures that are invariant under permutations (which switch bits around by permuting their positions) is exactly the set of Bernoulli measures.
I think all the examples of shift-invariant ergodic measures I know of are Markov chains. Hence this leads to the following sub-question?
Are there shift-invariant ergodic measures which are not Markov chains?
I am sure all this is standard and well-known, however I could not find an answer by Googling. Therefore, I am asking on Math.StackExchange (as opposed to MathOverflow).
Best Answer
Characterization?
If you want a characterization that is of hard analysis flavor, you could characterize ergodic measures as those measures where distribution of subwords in a larger word (say of length $N$) does not depend much on the choice of the word of length $N$ if you ignore some exceptional words of length $N$ (where the probability of the exception goes to zero). The precise statement of this characterization appears for example in the paper with the title: Entropy is the Only Finitely Observable Invariant.
I wonder if there is a theorem that gives you some class of measures parametrized by finite descriptions of them and then says that there is no algorithm to determine ergodicity for this class.
As for intuition, if you have a measure that is easily described and easy to reason about, then if you cannot come up with any way to extract some information from a $\mu$ typical sample binary sequence in a shift-invariant way, then the measure is going to be ergodic.
Examples
A simple (maybe too simple) example is the invariant measure you would obtain by concatenating 00 or 11 infinitely many times randomly and independently (each with probability 1/2), and then apply the shift map one or zero times, each with probability 1/2. This example is not very interesting and may feel like an easy way out. The reason this is not Markov (of any step) is because the support of this measure is not an SFT (subshift of finite type).
A more interesting example would be a measure in which distances between occurrences of 1 are independent. It's like a renewal process except discrete and invariant under the shift map. Let $(p_i)_{i = 1}^{\infty}$ be a sequence of nonnegative numbers whose sum is 1 and also such that $\sum_i i p_i < \infty$, then you can build such an invariant measure $\mu$ where $\mu([10^{i-1}1] | [1]) = p_i$ for all $i$ and $\mu([1]) = \sum_i i p_i > 0$. To construct this measure, you first build the conditional one $\mu_{[1]}$ (a measure defined on the cylinder $[1] \subset \{0, 1\}^{\mathbb N}$) which corresponds to the discrete-time renewal process which has $(p_i)_{i = 1}^{\infty}$ as its distribution of holding times. This $\mu_{[1]}$ is not invariant under the shift map, but it is invariant under its first return map, so you can use Kakutani skyscraper construction to construct $\mu$ defined on $\{0,1\}^{\mathbb N}$. This measure is ergodic because its restriction to $[1]$ is ergodic with respect to the first return map. You can then choose $(p_i)_{i = 1}^{\infty}$ in a way that it guarantees $\mu$ not being Markov. For example, you can make its support be the even shift (i.e. $p_i > 0$ if and only if $i$ is even).
Another interesting class of measures: measures corresponding to hidden Markov chains. These are measures that are factors of Markov measures.
More general class: measures from thermodynamic formalism, but things get very technical there.