User vaughn climenhaga - MathOverflow

Hilbert metric and cross-ratio of points on simplices

2013-05-17T16:46:30Z

Background and motivation:

Consider the cone $C\subset \mathbb{R}^d$ of vectors with non-negative components, and let $\Delta\subset C$ be the simplex of probability vectors (those for which $\sum v_i = 1$). The cone (and hence the simplex) can be equipped with the Hilbert metric, which has applications to Perron-Frobenius theory, among other things.

In these applications, the following step is important: given a $d\times d$ stochastic matrix $A$ with strictly positive entries, one has $A\Delta\subset \Delta$, and one wishes to estimate the diameter of $A\Delta$ in the Hilbert metric. Using some explicit formulas for the Hilbert metric, it can be shown that $$ (1)\qquad\qquad \mathrm{diam}(A\Delta) = \sup_{v,w\in\Delta} d(Av,Aw) = \max_{i,j} d(Ae_i,Ae_j), $$ where $e_i$ are the standard basis vectors. Geometrically, this can be stated as follows: the diameter of $A\Delta$ is achieved by considering only its extreme points.

The proof of (1) that I know relies on some matrix computations and doesn't feel particularly geometrically informative. It uses the characterisation of the Hilbert metric in terms of a partial order -- there is also a characterisation of the Hilbert metric in terms of a cross-ratio. In the present case it boils down to fixing two points $x,y\in C$, letting $w,z$ be the points at which the line through $x,y$ intersects $\partial C$, and setting $d(x,y)$ to be the log of the cross-ratio of $w,x,y,z$.

I wonder if there is a more geometric proof of (1) using this description of $d$. This motivates the following question, which can be stated without reference to the Hilbert metric but would (1).

Question: (can be read independently of the above)

Let $\Delta,\Delta'$ be simplices of the same dimension and suppose that $\Delta'\subset \Delta$. Let $\ell$ be a line that intersects $\Delta'$ in an interval. Let $x,y\in \Delta'$ be the endpoints of this interval, and let $w,z$ be the points where $\ell$ intersects $\partial \Delta$. Let $\Theta(\ell)$ be the cross-ratio of the points $w,x,y,z$.

Compactness of $\Delta'$ implies that there exists $\ell$ maximising $\Theta$. (We assume that $\Delta'\cap\partial\Delta=0$ so that $\Theta<\infty$.) It can be shown that the supremum is attained when $\ell$ is one of the edges of $\Delta'$, but the proof I know is non-geometric. Is there a geometric proof of this fact?

Answer by Vaughn Climenhaga for Variational Principle for the Entropy

2013-05-10T20:58:48Z

The theorem is true not only for homeomorphisms but also for continuous maps that are not necessarily invertible.

For discontinuous maps $f$, I'm not sure if there's any problem beyond the fact that the definition of topological entropy is generally made under the assumption that $f$ is continuous, and so one needs to check that the definition still makes sense. I believe it does, but one should be careful that there are several definitions (spanning sets, separated sets, open covers are the three most common) which are proved to be equivalent, and it needs to be checked whether or not this proof of equivalence uses continuity. I saw a paper where if I recall correctly, it was claimed that the definitions work and the whole theorem goes through without any assumptions on continuity of $f$ -- Michaela Ciklova, ``Dynamical systems generated by functions with connected $G_\delta$ graphs'', Real Analysis Exchange 30(2), 2004/2005, pp. 617-638 -- I haven't looked closely through the argument though.

As for your second question, about uniqueness, here you need some stronger hypotheses. One easy way to get non-uniqueness is to let $(X,f)$ and $(Y,g)$ be two expansive systems with equal topological entropy, then consider their disjoint union. The mme for $(X,f)$ and the mme for $(Y,g)$ are both mmes for this new system, so you get non-uniqueness.

A more interesting question is how you get non-uniqueness in the presence of topological transitivity or other ``connectedness'' properties. This was addressed in a couple other MO questions:

http://mathoverflow.net/questions/26094/a-topologically-mixing-subshift-with-multiple-measures-of-maximal-entropy

http://mathoverflow.net/questions/43564/transitive-shifts-with-multiple-fully-supported-mmes

There are various criteria under which you get uniqueness, and that's a broad theory that I could say more about if you want, but I think this answers the question you asked so I'll leave it here for now.

Answer by Vaughn Climenhaga for Entropy of edit distance

2013-04-24T20:38:47Z

This is not a complete answer and may not tell you anything you don't already know, but it's too long for a comment.

You can get an estimate on the number of words at an edit distance of $k$ from a given word of length $n$ by using the arguments in the proof of Lemma 2.6 in this paper. (The lemma is on page 10 and its proof is on page 28.)

The idea is that if a word $w$ is at an edit distance of $k$ from a word $v$, then one can get from $v$ to $w$ via the following steps:

insert $k$ copies of the symbol 'e' (for 'edit') into the word $v$;
one by one, go through the symbols 'e' and either change the symbol immediately before it, delete the symbol immediately before it, or insert a symbol immediately before it, and then delete the 'e'.

Step 1 gives a word of length $n+k$ with $k$ occurrences of the symbol 'e', so there are ${n+k\choose k}$ possibilities after this step. Then step 2 gives at most $3^k$ possible words for each of those possibilities, so for a fixed word $v$ of length $n$ one obtains the bound $$ \#\{w \mid \text{edit distance from $v$ to $w$ is $k$}\} \leq 3^k {n+k \choose k}. $$ For small $k$ this is a reasonable bound; in particular when $k\ll n$ this is not much larger than ${n\choose k}$, the number of words a Hamming distance of $k$ away. The problem is that for larger values of $k$ the procedure described above succumbs to a lot of overcounting, so it's not clear what the actual bound should be.

Answer by Vaughn Climenhaga for On the affine property of entropy map

2013-02-17T22:08:34Z

The result on affinity of the entropy map holds for arbitrary finite convex combinations of invariant measures: if $\mu_1,\dots,\mu_n\in M(X,T)$ are any invariant measures and $a_1,\dots, a_n\in [0,1]$ sum to 1, then $h(\sum a_i \mu_i) = \sum a_i h(\mu_i)$, where I write $h(\mu)$ in place of $h_\mu(T)$.

This can be proved by induction in a pretty standard way. The case $n=2$ is proved already. Now if it holds for some $n$, we prove it for $n+1$: first note that $\sum_{i=1}^n a_i \mu_i = (1-a_{n+1}) \nu$, where $\nu\in M(X,T)$ is a probability measure, and we have $$ h(\sum_{i=1}^{n+1} a_i \mu_i) = h((1-a_{n+1})\nu + a_{n+1}\mu_{n+1}) = (1-a_{n+1})h(\nu) + a_{n+1} h(\mu_{n+1}), $$ and then expanding $h(\nu)$ using the induction hypothesis gives the result we want.

The remark after Theorem 8.1 in Walters' book doesn't say quite what you suggested it does. Quoting the remark: "The first part of the proof shows that if $\mu,m\in M(X)$, $p\in [0,1]$, and $\xi$ is a finite partition then $H_{p\mu + (1-p)m}(\xi) \geq p H_\mu(\xi) + (1-p)H_m(\xi)$." Indeed this only gives an inequality in one direction, but two points must be made:

The measures $\mu,m$ are not assumed to be invariant.
The quantity here is $H_\mu(\xi)$, the entropy of a partition, rather than $h_\mu(T)$, the (Kolmogorov-Sinai) entropy of an invariant measure, which is defined as the (linear) growth rate of the quantities $H_\mu(\xi_n)$ for a particular sequence of partitions $\xi_n$. So the remark is not about the KS entropy $h_\mu(T)$, which is affine over all finite convex combinations, but rather about a specific intermediary quantity which is not generally affine, although it does satisfy a super-affinity inequality. In particular there is no contradiction between the remark and the fact that affinity of $h_\mu$ holds for arbitrary finite combinations.

Answer by Vaughn Climenhaga for Ergodicity with respect to the shift

2013-02-12T21:10:38Z

No, there are many fully-supported non-ergodic measures. Just take a convex combination of a fully-supported measure and anything else. (Recall that an invariant measure is ergodic if and only if it cannot be writen as a non-trivial convex combination of two distinct invariant measures.)

Also there are many ergodic measures that are not fully supported. For example, given any periodic sequence consider the atomic measure that gives equal weight to each of the shifts of this sequence. This measure is ergodic but its support is a finite set.

Answer by Vaughn Climenhaga for Trichotomies in mathematics

2013-02-02T21:41:38Z

In thermodynamic formalism for dynamical systems, a Hölder continuous potential function $\phi$ on a countable state topological Markov chain $(X,\sigma)$ is either positive recurrent, null recurrent, or transient. These correspond to the three possibilities for equilibrium states (shift-invariant measures maximising the quantity $h(\mu) + \int_X \phi\,d\mu$): existence of a finite equilibrium state is equivalent to positive recurrence; null recurrence is the boundary case where the equilibrium state becomes $\sigma$-finite but not finite, and transience is the case where there is no equilibrium state (all the weight has gone to infinity).

These can be characterised in terms of a particular sequence $a_n>0$: positive recurrence is equivalent to $\limsup a_n > 0$, null recurrence is equivalent to $a_n\to 0$ and $\sum a_n=\infty$, and transience is equivalent to $\sum a_n<\infty$. I imagine this trichotomy for sequences appears in other places as well.

Edit: It's worth mentioning that this trichotomy is also true for random walks on directed graphs (weighted or unweighted) -- historically I believe this is where it was first studied and where the terminology came from, but as a dynamicist I more immediately think of the interpretation above. In this setting the interpretations are as follows:

Positive recurrent -- with probability 1, a random walk returns to where it started, and the expected return time is finite.
Null recurrent -- the walk returns to the starting position with probability 1, but the expected return time is infinite.
Transient -- with probability 1, the walk never returns to its starting position.

Answer by Vaughn Climenhaga for Particles chasing one another around a circle

2012-12-03T07:01:07Z

To answer your questions about median and mode, one can take Alexandre's answer a little further and compute the exact distribution function for the overtake-times.

Note that the overtake-time doesn't depend on $v_1,v_2$ directly, but only on their difference. Call the difference $v$. Now $v$ is the difference of two uniformly distributed random variables on $[0,1]$, so it is supported on $[-1,1]$ with probability density function $1-|v|$. Moreover, since $\theta$ is uniformly distributed we can without loss of generality identify the cases $(v,\theta)$ and $(-v,1-\theta)$ and reduce everything to the following set-up:

$v$ is distributed on $[0,1]$ with density function $2(1-v)$.
$\theta$ is uniformly distributed on $[0,1]$.
The overtake-time is $t=\theta/v$.

Now we can compute the cumulative density function for the overtake-time. Indeed, we have $P(t<T) = P(\theta/v<T) = P(\theta < Tv)$ , which we can get by the following integral: $$ P(t<T) = \int_0^1 2(1-v) P(\theta < Tv | v) \,dv. $$ The probability $P(\theta < Tv | v)$ is given by the function $f(\theta,v) = \max(Tv,1)$. Thus for $T\leq 1$, we have $f(\theta,v)=Tv$ for all $v\in[0,1]$, so integrating gives $P(t<T) = T/3$ , while for $T\geq 1$, we integrate and find $$ P(t<T) = \int_0^{1/T} 2(1-v)Tv\,dv + \int_{1/T}^1 2(1-v)\,dv = 1-\frac 1T + \frac 1{3T^2}. $$ So in the end the cumulative density function for the overtake-time is $$ P(t<T) = \begin{cases} \frac T3 & T\leq 1, \\ 1 - \frac 1T + \frac 1{3T^2} & T \geq 1. \end{cases} $$ The term $1/T$ in the last expression will give you the infinite mean, since upon differentiating the CDF you'll get a term $1/T^2$, which upon multiplying by $T$ and integrating to get the mean you end up integrating $1/T$ from $1$ to $\infty$.

As for the median, it looks as though any proximity to $\pi/2$ is just a red herring, because solving for $P(t<T) = 1/2$ yields $T=1 + \frac 1{\sqrt{3}} \approx 1.57735\dots$.

Answer by Vaughn Climenhaga for Connection between properties of Dynamical and Ergodic Systems

2012-11-24T22:33:29Z

Edit: I've updated this answer to reflect the helpful comments made by Andres Koropecki and Ian Morris.

As the other answers mentioned, the first crucial distinction you must make is that some properties refer to a topological dynamical system $(X,T)$, while others refer to a measure-preserving dynamical system $(X,T,\mu)$. Thus there are two different sets of definitions. Let me attempt a sketch at some of the relationships within each set.

First suppose you have a topological dynamical system $(X,T)$. Then four of the key properties are topological transitivity, topological mixing, minimality, and unique ergodicity. The first three are related by

topologically mixing $\Rightarrow$ topologically transitive;
minimal $\Rightarrow$ topologically transitive.

Unique ergodicity is independent of those three properties. The picture is the following.

Counterexamples 1-9 illustrating the strict containments are as follows. (These may not be the simplest or the earliest counterexamples in each case, and I welcome corrections or improvements. This is based on some quick googling for things not already in my memory, plus the helpful additions offered by commenters.)

1. $X = \Sigma_2 \times \{a,b\}$, the direct product of a full two-shift with a period-two orbit, where the dynamics is $\sigma\times S$, with $\sigma$ the shift map and $S$ the map interchanging $a$ and $b$.

2. $X=\Sigma_2$.

3. Constructed by Bassam Fayad, Topologically mixing and minimal but not ergodic, analytic transformation on $\mathbb{T}^5$, 2000.

4. Constructed by Furstenberg, Strict ergodicity and transformation of the torus, 1961.

5. An irrational flow on the torus, slowed down near a single point: see the comment below by Andres Koropecki.

6. As Ian Morris points out in the comments, the identity map on a singleton set works here. A less trivial example was given by Karl Petersen, A topologically strongly mixing symbolic minimal set, 1970.

7. Rotation of the circle by an irrational angle.

8. Direct product of the example from 5 with a periodic orbit. (Again as suggested by Andres in the comments.)

9. North-south map: a map $T\colon [0,1]\to [0,1]$ with fixed points at $0,1$ and such that $T(x) < x$ for all $x\in (0,1)$. Identify the endpoints $0$ and $1$ so that this is a uniquely ergodic circle map.

A couple things are probably worth pointing out.

Terminology is not always uniform. For example one of the papers I referenced (I think Petersen's) uses "ergodic" in place of "topologically transitive", to highlight the analogy with the measure-preserving case. So people may sometimes use different words for the same thing.
Conversely the same word may mean different things. There are two definitions of topological transitivity, one involving open sets ($f^n(U) \cap V \neq \emptyset$ for some large $n$) and the other involving existence of a dense orbit. The definition involving open sets more closely mirrors the definition of topological mixing (non-empty intersection for every large $n$), while the definition with a dense orbit more closely mirrors minimality (denseness of every orbit). The definitions are equivalent if $X$ is separable, second category, and has no isolated points.

All of the above is for topological dynamical systems, where no invariant measure is specified. Then there are the ergodic properties: those that depend on a system preserving an measure $\mu$. For these one has the ergodic hierarchy.

It is very often the case that one wishes to study a topological dynamical system as a measure-preserving system by equipping it with an invariant measure, and in this case it is quite reasonable to ask about the relationships between the two different classes of properties. But this depends on which invariant measure you choose, because in general there may be very many of them. One may ask what properties of $(X,T)$ let you pick invariant measures $\mu$ with certain nice properties, and this is a whole different story which would expand this answer far beyond the bounds of propriety.

Answer by Vaughn Climenhaga for Continuous pointwise ergodic theorem?

2012-11-22T01:59:35Z

The answer to both questions is 'no', both for maps and for flows.

For concreteness let $M=\{0,1\}^\mathbb{Z}$ be the set of bi-infinite sequences of $0$s and $1$s, and let $\Phi\colon M\to M$ be the shift map given by $\Phi(x)_j = x_{j+1}$ for $x=(x_j)_{j\in\mathbb{Z}}$ .

Q1. Topological transitivity of $\Phi$ only depends on $\Phi$ and $M$, not on the measure $\mu$. In particular the system $(M,\Phi)$ defined above is topologically transitive, but there are many (many!) regular Borel probability measures that are preserved by $\Phi$, and not all of them are ergodic. See this question for some discussion of how intricate this space is. In particular, let $p$ and $q$ be fixed points for $\Phi$, and let $\mu$ be the atomic measure that gives weight $\frac 12$ to each of $p$ and $q$. Then $\mu$ is $\Phi$-invariant but not ergodic.

Q2. The pointwise time averages do not need to exist for every $x$. In fact it is quite typical that they do not exist. Let me make this last statement a little more precise, again using the example of $(M,\Phi)$ from above.

Consider the continuous real valued function $f\colon M\to \mathbb{R}$ defined by $f(x) = x_0$. That is, $f$ is simply the value of the symbol in the $0$ position in the sequence $x$. Then $a_N(x) := \frac 1N \sum_{j=1}^N f(\Phi^j(x))$ is the frequency of the symbol $1$ in the string $x_1 x_2 \cdots x_N$.

The pointwise time averages of $f$ along the orbit of $x$ exist if and only if $a_N(x)$ converges as $N\to \infty$ -- in other words, if and only if the lower and upper asymptotic frequencies of the symbol $1$ are equal. It is straightforward to construct examples of sequences $x\in M$ such that the lower and upper asymptotic frequencies disagree and the limit does not exist.

In fact, one can say some more about how large the set of such points are. Given $x\in M$, let $\lambda(x) = \liminf a_N(x)$ and $\Lambda(x) = \limsup a_N(x)$ . Note that $0\leq \lambda(x)\leq \Lambda(x)\leq 1$ for all $x\in M$. Given $0\leq r\leq s\leq 1$, let $K_{r,s}$ be the set of $x\in M$ such that $\lambda(x) = r$ and $\Lambda(x) = s$. The study of the various sets $K_{r,s}$ is called multifractal analysis, and quite a lot is known. I'll state just a few results addressing your question.

Let $K^\neq = \bigcup_{r<s} K_{r,s}$ be the set of points for which $\lambda(x) \neq \Lambda(x)$, so that the limit doesn't exist. Then the following are true (at least for the system I described above -- determining for which general classes of systems these statements hold is a more subtle question):

$K^\neq$ has zero measure for every $\Phi$-invariant measure.
$K^\neq$ has Hausdorff dimension equal to the Hausdorff dimension of $M$. (The more honest way of saying this is that they have equal topological entropies, but Hausdorff dimension is a more familiar concept and the statement with dimension is true if you use an appropriate metric.)
$K^\neq$ is residual -- that is, it is a countable intersection of open and dense subsets of $M$.
In fact, one can show that $K_{0,1}$ is residual, but that it has Hausdorff dimension $0$. (The fact that $K^\neq$ has full Hausdorff dimension is due to the fact that the Hausdorff dimension of $K_{r,s}$ approaches the Hausdorff dimension of $M$ as $r,s\to \frac 12$.)

So there's an assortment of facts for you illustrating how large the set of points is where convergence fails. In particular the last fact can be interpreted as saying that from a topological point of view, for a generic point $x$ the limit fails to exist as strongly as it can possibly fail. This highlights the fact that ergodic theory is really about measures, not topology. (I will note that the limit exists everywhere if your map is uniquely ergodic, that is, if there is only one invariant probability measure. Such systems are quite different from the systems I was describing, which should be thought of as hyperbolic, or informally, chaotic.)

Answer by Vaughn Climenhaga for Stationary, ergodic measures from the structuralist point of view

2012-10-10T19:54:50Z

I'm not familiar enough with the notion of localisable measurable space in Pavlov's sense to say anything too authoritative, but I can make the following comments which apply to at least the case $d=1$ (as a dynamicist working mostly with group actions generated by a single continuous map $f\colon X\to X$ this is the natural setting for me):

An ergodic measure is uniquely defined by its collection of null sets, in the following sense: if $\mu$ is an ergodic stationary measure and $\nu\ll \mu$ is also ergodic and stationary, then $\nu=\mu$. This is just because the Radon-Nikodym derivative $d\nu/d\mu$ is an invariant function and hence a.e.-constant.
As discussed in this other question, there are many examples of dynamical systems (including in particular full shift spaces, which is the dynamicist's way of talking about the set of spin fields when $d=1$) for which the space of stationary ergodic measures is the set of extreme points of a Poulsen simplex. In particular it is path-connected and dense in its convex closure.

Answer by Vaughn Climenhaga for Ergodicity for a Probabilistic Cellular Automaton on a finite space

2012-09-26T13:39:04Z

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$.

Answer by Vaughn Climenhaga for Proofs without words

2010-05-15T16:40:20Z

This should really be a comment on Marco Radeschi's answer from Feb 22 involving the area formula for spherical triangles, but since I'm new here I don't have the reputation to leave comments yet.

In reply to Igor's comment (on Marco's answer) wondering about an analogous proof for the area formula of hyperbolic triangles: there is one along similar lines, and you're rescued from non-compactness by the fact that asymptotic triangles have finite area. In particular, the proof in the spherical case relies on the fact that the area of a double wedge with angle $\alpha$ is proportional to $\alpha$; in the hyperbolic case, you need to replace the double wedge with a doubly asymptotic triangle (one vertex in the hyperbolic plane and two vertices on the ideal boundary) and show that if the angle at the finite vertex is $\alpha$, then the area is proportional to $\pi - \alpha$. That follows from similar arguments to those in the spherical case (show that the area function depends affinely on $\alpha$ and use what you know about the cases $\alpha=0,\pi$).

Once you have that, then everything follows from the picture below, since you know the area of the triply asymptotic triangle and of the three (yellow, red, blue) doubly asymptotic triangles.

(That picture is slightly modified from p. 221 of this book, which has the whole proof in more detail.)

Answer by Vaughn Climenhaga for Proofs without words

2010-05-20T01:27:35Z

It's a long list of wonderful answers already, but I can't resist...

Question: Is it possible to find six points on a square lattice that form the vertices of a regular hexagon?

Proof without words:

Hint: A square lattice is invariant under rotation by π/2 around any lattice point. Use reductio ad absurdum.

Credit: I learned that proof from György Elekes during the Conjecture and Proof course in the Budapest Semesters in Mathematics, after constructing a proof of my own that used entirely too many words and made very laboured use of the fact that $\sqrt{3}$ is irrational. The picture here is my own creation (using Asymptote).

Follow-up: Can you find four points on a hexagonal lattice that form the vertices of a square? The proof is similar but not immediate.

Answer by Vaughn Climenhaga for Aproximating dynamical systems by intrinsically ergodic systems

2012-07-09T15:36:04Z

Every topologically transitive shift space, whether intrinsically ergodic or not, can be approximated from above by intrinsically ergodic systems.

Indeed, given a finite alphabet $A=\{1,2,\dots,p\}$ and a closed $\sigma$-invariant set $X\subset A^\mathbb{Z}$ (everything works just the same for one-sided shifts), let $\mathcal{L}=\mathcal{L}(X) \subset A^* = \bigcup_{n\geq 1} A^n$ be the collection of all finite words that appear in some sequence $x\in X$. Thus $X$ determines $\mathcal{L}$ and vice versa. Let $\mathcal{F} = A^* \setminus \mathcal{L}$ be the set of forbidden words. Now let $Y_n\subset A^\mathbb{Z}$ be the set of all sequences that do not contain any words in $\mathcal{F}$ of length $\leq n$. Then $Y_n$ is a shift of finite type and $X= \bigcap_{n\geq 1} Y_n$.

Furthermore, $Y_n$ is topologically transitive and hence intrinsically ergodic by virtue of being an SFT. To see this, choose any $v,w\in \mathcal{L}(Y_n)$ and write $v=v_1 v_2$, $w=w_1 w_2$ where $v_2$ and $w_1$ both have length exactly $n$. Then by transitivity of $X$ there exists a word $u$ such that $v_2 u w_1 \in \mathcal{L}(X)$, and by the definition of $Y_n$ we have $v u w\in \mathcal{L}(Y_n)$, which shows that $Y_n$ is transitive.

Thus the counterexample given in the answer to your earlier question works here as well. Actually, I'll point out that there are quite a broad class of such counterexamples, which can be constructed by looking at coded systems: these are shift spaces defined either in terms of a countable collection of generating words that are allowed to be freely concatenated, or equivalently in terms of a directed graph on countably many vertices with edges labeled from a finite alphabet. There are plenty of examples of coded systems that are transitive but not intrinsically ergodic (see this question or this answer, for example), and you can approximate coded systems from within by SFTs (or at least sofic shifts) in a very natural way: just truncate the collection of generators to a finite set, or truncate the graph to a finite subgraph.

In another direction, I believe there is a paper of Gurevich in which certain quantitative conditions are given on the rate of approximation from outside by intrinsically ergodic systems that turn out to be sufficient to guarantee intrinsic ergodicity of $X$. But I don't have the reference handy at the moment, and I'll have to wait until I'm in my office next week to dig up the paper and see if it's in fact relevant.

Edit: I found the Gurevich paper I was thinking of (actually 2 papers). References are as follows:

B.M. Gurevic, "Uniqueness of the measure with maximal entropy for symbolic almost-Markov dynamic systems", Soviet Math. Dokl. 13 (1972), No. 3, 569-571.
B.M. Gurevic, "Stationary random sequences of maximal entropy", Chapter 10 (pp. 327-380) of Multicomponent Random Systems, edited by R.L. Dobrushin and Ya.G. Sinai, Advances in Probability and Related Topics, Volume 6, Marcel Dekker Inc (1980).

As you see from the page count, (1) is quite short and just has the statement of the result, no proofs, while (2) is more comprehensive. Roughly speaking, the main result can be summarised as follows (the result in the paper is more precise because it doesn't assume that various limits exist).

Given a shift space $X$ on a finite alphabet, let $\mathcal{L}_n$ be the set of words of length $n$ that appear in some $x\in X$, and let $Y_n$ be the SFT defined by the condition that $x\in Y_n$ if and only if $x_k \cdots x_{k+n-1} \in \mathcal{L}_n$ for every $k$. Then $X = \bigcap_n Y_n$, and in particular, $h(Y_n) \to h(X)$, where $h$ is the topological entropy. Let $\rho_n = h(Y_n) - h(X)$ be the entropy gap; heuristically, $\rho_n$ is the amount of entropy that is destroyed by the restrictions in $X$ of length $>n$ .

Furthermore, define $\alpha_n$ by $$ \alpha_n = \inf \{\tau \mid \forall u,v\in \mathcal{L}_n\ \exists w\in \mathcal{L}_\tau\ s.t. uvw\in \mathcal{L}\}. $$ That is, in the shift $X$, any two words of length $n$ can be glued together using a word of length $\alpha_n$. The shift $X$ has specification if and only if $\lim \alpha_n < \infty$, and in this case $X$ is intrinsically ergodic. (This is due to Bowen.)

Let $R_\alpha = \lim \frac 1n \log \alpha_n$ be the growth rate of $\alpha_n$, and let $R_\rho = -\lim \frac 1n \log \rho_n$ be the decay rate of $\rho_n$. Thus $R_\alpha$ is the rate at which the gluing time increases (and can be thought of as quantifying how badly $X$ fails to have specification), and $R_\rho$ is the rate at which the entropy gap decays (and can be thought of as quantifying how closely $X$ is approximated by the SFTs $Y_n$ in terms of entropy).

Theorem (Gurevich): If $h(X)>0$ and $R_\alpha < \frac{R_\rho} {16 h(X)}$, then $X$ is intrinsically ergodic.

Heuristically, "if the failure of specification is slow relative to the approximation by SFTs, then $X$ is intrinsically ergodic".

Answer by Vaughn Climenhaga for Recurrence theorems

2012-05-29T00:00:30Z

If $\mu$ is a probability measure on $X$ and $T\colon X\to X$ is an ergodic measure-preserving transformation, then for every set $A$ with positive $\mu$-measure, the Poincare Recurrence Theorem tells you that $\mu$-a.e. point $x\in A$ has finite first return time $\tau_A(x)$. There are various results giving more detailed information about the first return time, but the most general is probably Kac's formula, which states that $\int_A \tau_A(x) \,d\mu(x) = 1/\mu(A)$, and more generally that if $\phi\in L^1(X)$, then $\int_A \sum_{k=1}^{\tau_A(x)} \phi(T^k x) \,d\mu(x) = \int_X \phi(x)\,d\mu(x)$. (The result on average return time follows by taking $\phi$ to be the characteristic function of $A$).

Answer by Vaughn Climenhaga for Separable sigma-algebra: equivalence of two definitions

2012-05-28T20:46:42Z

I'm late to the party, but here's my two cents. References in what follows are to

[Ha] P.R. Halmos, Measure Theory, Springer, 1950.
[Ro] V.A. Rokhlin, On the fundamental ideas of measure theory, Transl. AMS, Series 1, No. 10 (1962), 1-54. (The original Russian article is from 1949. A pdf of the English translation is presently available here.)
[JDH] will denote the answer already given to this question by Joel David Hamkins.

Consider a measured $\sigma$-algebra $(S,\mu)$. Assume that $\mu$ is normalised to have total weight 1, and that $S$ is complete (contains all subsets of null sets).

In [Ha], $(S,\mu)$ is said to be separable if it has a countable subset that is dense w.r.t. the metric $\rho(A,B) = \mu(A\bigtriangleup B)$. We denote this property by (S).

In [Ro], $(S,\mu)$ is said to be separable if it has a countable subset $\Gamma$ such that for every $A\in S$, there exists $B\in \sigma(\Gamma)$ such that $A\subset B$ and $\mu(B\setminus A) = 0$. Here $\sigma(\Gamma)$ is the $\sigma$-algebra generated by $\Gamma$. Since we're already using the word "separable" for (S), let's say that in this case $(S,\mu)$ is one-sided countably generated, and denote this property by (CG1). To keep terminology manageable, we won't explicitly say "mod zero", but this is understood, and thus we need to specify "one-sided" because of the restriction that $A\subset B$, which means that the "mod zero" only applies to the outer approximation, whereas the inner must be exact.

So that's two conditions. Let's round it out by saying that $(S,\mu)$ is one-sided separable if it has a countable subset $\Gamma$ that is not only dense w.r.t. $\rho$ but also has the property that for every $A\in S$ and $\epsilon>0$ there exists $B\in \Gamma$ such that $A\subset B$ and $\mu(B\setminus A) < \epsilon$; we denote this property by (S1). Similarly, say $(S,\mu)$ is countably generated if it has a countable subset $\Gamma$ such that for every $A\in S$ there exists $B\in \sigma(\Gamma)$ such that $\rho(A,B)=0$.

Now we have four conditions: two of them involve approximations from the outside, while the other two allow arbitrary approximations. Clearly (CG1) implies (CG), and similarly (S1) implies (S). It was shown in [JDH] that (CG) implies (S), but the converse is not true.

So far this is just a summary of what others have already said here. Here's the new bit.

Equivalence when non-atomic. Recall that an atom is a set $E\in S$ such that $\mu(E)>0$ and every subset $A\subset E$ has either $\mu(A)=0$ or $\mu(A)=\mu(E)$. If $(S,\mu)$ is non-atomic (has no atoms), then in fact all four definitions are equivalent. To see this, observe that any of the four imply (S), and that (S) in turn implies that there is a $\sigma$-algebra isomorphism from $(S,\mu)$ to the Lebesgue sets on the unit interval equipped with Lebesgue measure [Ha, Sec. 41, Theorem C]. Since all four properties hold for the Lebesgue space, we are done.

Atomic pieces. Intuitively, one expects that if $E$ is an atom in $(S,\mu)$, then there should be a $\sigma$-algebra map $(S|_E, \mu|_E) \to (T,\nu)$ that is a mod zero isomorphism, where $T$ is a $\sigma$-algebra with only two elements ($\emptyset$ and a single point) and $\nu$ is a point mass with total weight $\mu(E)$. In particular, this requires that there exists a set $F\subset E$ such that $\mu(F) = \mu(E)$ and every null set $A\subset E$ has $A\cap F = \emptyset$. The example in [JDH] shows that this need not always be the case, and that an atomic space need not be (mod zero) isomorphic to a point mass even if (S) holds.

The one-sided conditions (S1) and (CG1) serve to fill this gap and let us deal appropriately with the atomic pieces. Indeed, if either of these properties hold, then one can show the following:

(A) There exist atoms $E_n \in S$ such that $S|_{E_n}$ is the trivial $\sigma$-algebra for every $n$, and $S|_{(\bigcup_n E_n)^c}$ is isomorphic to the Lebesgue sets on an interval of length $1 - \sum_n \mu(E_n)$.

So at the end of the day, we see that (CG1) and (S1) are equivalent, and imply both (CG) and (S). Furthermore, (CG) implies (S), and the converse is true if $(S,\mu)$ is non-atomic, but may fail if it has atoms.

I don't know if (CG) is equivalent to (CG1) and (S1). I suspect it is not, because otherwise I doubt that [Ro] would introduce the extra condition that $A\subset B$. However, I do not know a counterexample.

Comments on the proof of (A). For the proof of (A), one must use (CG1) or (S1) to take an atom $E\in S$ and produce a subset $F\subset E$, $F\in S$ such that $F\cap A = \emptyset$ for all $A\in S$ with $\mu(A)=0$. The key to this is that both conditions allow you to produce a countable family $S'\subset S$ such that for every $\epsilon>0$ and every null set $A$, we have $A\subset \bigcup_n B_n$ for some $B_n \in S'$ with $\mu(\bigcup_n B_n) < \epsilon$. (For (S1) one takes $S' = \Gamma$, while for (CG1) one takes $S'$ to be the set of all finite intersections of sets in $\Gamma$ and their complements.) Then because $E$ is an atom, we can conclude that $\mu(B_n \cap E) = 0$ for all $n$, and so the collection of all null sets in $E$ can be covered by a countable collection of null sets, whose union therefore has measure zero.

Answer by Vaughn Climenhaga for Understanding a proof that the simplex of shift invariant probability measures on $\{0,1\}^\mathbb{Z}$ is Poulsen?

2012-05-13T04:54:29Z

The language of the proof given in the book you refer to is a little different from the language I'm accustomed to, but I'll give what I believe is the exact same argument using a slightly different language, and hopefully do it in such a manner that the issue you point out doesn't arise. (Since I'm not quite sure how to explain it away using a language that's less familiar to me.)

Let $X = \{0,1\}^\mathbb{Z}$ with $\sigma\colon X\to X$ the shift map, and let $\mu$ be any $\sigma$-invariant probability measure on $X$. Given $n\in \mathbb{N}$, let $\nu_n$ be the Bernoulli measure for $\sigma^n$ that best approximates $\mu$, and let $\mu_n$ be the invariant measure generated by $\nu_n$.

More precisely, $\nu_n$ is defined as follows. Let $Y = \{0,1,\dots,2^n-1\}^\mathbb{Z}$, with $\tau\colon Y\to Y$ the shift map, and define a homeomorphism $\pi\colon Y \to X$ by identifying symbols in the alphabet of $Y$ with $n$-words in $X$: if $\phi\colon \{0,1,\dots,2^n-1\}\to \{0,1\}^n$ is a bijection, then we put $\pi(y) = \dots \phi(y_{-1}).\phi(y_0)\phi(y_1)\dots$, where juxtaposition denotes concatenation. Note that $\pi$ conjugates $\tau$ to $\sigma^n$ via $\pi\circ \tau = \sigma^n\circ \pi$.

Define a measure $\mu^*$ on $Y$ by $\mu^*(E) = \mu(\pi E)$. Now define a $\tau$-invariant measure $\nu$ on $Y$ by putting $\nu([y_1\dots y_k]) = \prod_{j=1}^k \mu^*([y_j])$. This is the Bernoulli measure that best approximates $\mu^*$. Define $\nu_n$ on $X$ by $\nu_n(E) = \nu(\pi^{-1}E)$. Then $\nu_n$ is a Bernoulli measure for $\sigma^n$ with the property that $\nu_n([x_1\dots x_n]) = \mu([x_1\dots x_n])$ for every $n$-cylinder, but $\nu_n$ is not $\sigma$-invariant.

To rectify this, let $\mu_n = \frac 1n \sum_{k=0}^{n-1} \sigma_*^k \nu_n$. Then $\mu_n$ is $\sigma$-invariant, and moreover, since for every $n$-cylinder $C$ the $\sigma$-invariance of $\mu$ gives $(\sigma_*^k \nu_n)(C) = (\sigma_*^k \mu)(C) = \mu(C)$, we have $\mu_n(C) = \mu(C)$.

I believe that this last set of equalities (the fact that $\nu_n$, $\mu_n$, and $\mu$ agree on $n$-cylinders) is the statement you wanted explained. It seems to me that agreement on $C_{\Lambda_n}$ (in the language of the book) corresponds to agreement on $n$-cylinders (in the language here). In any case, the measure $\mu_n$ is ergodic and $\sigma$-invariant, and approaches $\mu$ as $n\to\infty$, which shows that the space of $\sigma$-invariant measures is the Poulsen simplex.

Answer by Vaughn Climenhaga for A Fractional Linear Transformation Class Property

2012-04-21T05:19:29Z

You're asking for a one-parameter family $\mathcal{C}$ of maps on a closed interval $I$ such that

the endpoints of $I$ are fixed by every map in $\mathcal{C}$;
the maps in $\mathcal{C}$ are strictly increasing;
$\mathcal{C}$ is closed under composition;
every positive real number appears exactly once as the ratio of the derivatives of $\mathcal{C}$ at the right and left endpoints of $I$.

The fourth condition means that $\mathcal{C}$ should be parametrised by $\mathbb{R}^+$, so let's write $\mathcal{C} = \{ \psi_c \mid c>0 \}$, where $c$ represents the square root of the ratio between the derivates at the endpoints, as in your question. The chain rule together with the third condition means that we should require $$\psi_{c_1 c_2} = \psi_{c_1} \circ \psi_{c_2}$$ for all $c_1,c_2>0$. We can reparametrise $\mathcal{C}$ by putting $t=\log c$ (or $t=-\log c$) and writing $\phi_t = \psi_c$, this becomes $$ \phi_{t_1+t_2} = \phi_{t_1} \circ \phi_{t_2}.$$ In other words, the family $\mathcal{C}$ defines an action of $\mathbb{R}$ on $I$, or in the language of dynamical systems/ODEs, a flow on $I$. This flow comes from integrating a vector field $V(x)$, or if you prefer, solving the ODE $$(*) \qquad \qquad \frac d{dt} \phi_t(x) = V(\phi_t(x)).\qquad\qquad\qquad$$ Conditions 1 and 2 mean that $V$ should vanish at the endpoints of $I$ and should be positive everywhere else. But modulo some regularity concerns, that's all you need. If you let $V\colon I\to [0,\infty)$ be any Lipschitz continuous function that vanishes at the endpoints of $I$ and is positive on its interior, then solving $(*)$ will give you a family of smooth maps (the time-$t$ maps of the flow) that satisfy your conditions.

Incidentally, you can use $(*)$ to see how both the family $\mathcal{S}$ of FLTs and the family in Robert Israel's (second) answer fit into this scheme. If you write $$ \phi_t(x) = \frac{e^{-t} x}{1+(1-e^{-t})x}$$ for the FLT satisfying your conditions (with $c=e^{-t}$ and $t\in\mathbb{R}$ arbitrary), then an easy calculation shows that $\phi_{s+t} = \phi_s \circ \phi_t$, so this defines a flow, and we can compute $$ V(x) = \frac{d\phi_t(x)}{dt}|_{t=0} = -x(1+x). $$ In other words, these FLTs are just the time-$t$ maps of the logistic flow on the interval $[-1,0]$. You can play a similar game with the arctan maps, but I haven't worked it out to see if the formula comes out cleanly.

Actually, the family of arctan maps in Robert Israel's answer illustrates a (superficially) different way of approaching the question, which is to fix a homeomorphism $h$ between the interior of $I$ and the real line (or the half-line) and then define the family of maps $\mathcal{C}$ to be those that are conjugated to translations (or homotheties) by $h$. So in his example, you conjugate to the negative half-line by $h(x) = \tan(\pi x/2)$ and then let $g_c = h^{-1} \circ (y\mapsto cy) \circ h$.

Of course, logs turn the half-line into the line and multiplication into addition, so this turns into translation on the line under another change of coordinates. And finding a change of coordinates that turns a map into translation on the line is just another way of saying that you find that map as a solution of an ODE, so it boils down to what I described above. Your choice... you can choose the vector field $V$, or you can choose the homeomorphism $h$. Either will give you quite a large number of examples.

Answer by Vaughn Climenhaga for The Manneville-Pomeau map is topologically conjugate to a full one-sides shift on two symbols. Can you give the corresponding homeomorphism?

2012-04-18T14:46:54Z

Pengfei's answer gives you the general form of the semi-conjugacy $\pi_s$ (basically, the answer is the proof that there is a semi-conjugacy that is 1-1 except at preimages of the endpoints). If you're looking for more detailed information about the structure of $\pi_s$, then it depends on exactly what your goal is, but the most useful thing to have is usually an estimate on the points $\beta_n := \pi_s(0^n 1^\infty)$ -- that is, the points which lie in the first branch of $f$ for $n$ iterates and then are mapped into the endpoint $1$. (This is usually the hard part of the estimates because the map is uniformly expanding everywhere else, which makes life easier.)

Many useful estimates on these points can be found in Section 6.2 of Lai-Sang Young, Recurrence times and rates of mixing, Isr. J. Math. 110 (1999), 153-188. In particular, one has $\beta_n \in [(n+1)^{-1/s}, n^{-1/s}]$.

You can also derive useful estimates by approximating the first branch of the Manneville-Pomeau map with the time-1 map of the ODE $x' = x^{1+s}$. (If you just want to study a map with an indifferent fixed point, then you can use this as your definition, so there's no approximation required.) This ODE can be explicitly solved by observing that $(x^{-s})' = -s$, and so $x(t) = (x_0^{-s} - st)^{-1/s}$.

I'm not sure how feasible it is to write down an explicit expression for the semi-conjugacy, even armed with these estimates, but these give you most of the quantitative tools you need when you're working with the Manneville-Pomeau map.

Transitive shifts with multiple fully supported MMEs

2010-10-25T19:46:04Z

This is a sequel to my earlier question, where I asked for an example of a shift space that is mixing but not intrinsically ergodic -- that is, it has multiple measures of maximal entropy (MMEs). Steve Huntsman's answer referred me to a paper by Haydn that gives such an example: however, in that example the two MMEs are supported on disjoint compact subsets of the shift space, and so in some sense the shift can be viewed as two intrinsically ergodic shifts that have been "glued together".

Is there an example of a transitive shift with multiple MMEs that are all fully supported? More precisely, does anybody know of a transitive shift space $X\subset \{0,1,\dots,p-1\}^\mathbb{Z}$ for which there are two distinct ergodic measures $\mu_1, \mu_2$ such that

$h_{\mu_1}(\sigma) = h_{\mu_2}(\sigma) = h_\mathrm{top}(X,\sigma)$;
$\mu_i(U)>0$ for every open set $U\subset X$ and $i=1,2$?

Answer by Vaughn Climenhaga for Transitive shifts with multiple fully supported MMEs

2012-04-14T04:50:52Z

Poking through the DGS book mentioned in Ian's answer I came along a reference to a paper that turns out to be exactly what I wanted when I asked this question originally, so I'll post it here for the sake of closure and because it's a nice example.

The paper is by Wolfgang Krieger: On the uniqueness of the equilibrium state, Mathematical Systems Theory 8 (2), 1974, p. 97-104.

The example is the Dyck shift, which is easiest to understand in terms of brackets. The alphabet of the shift is a collection of $2n$ symbols that come in $n$ pairs; each pair has a left element and a right element. So with $n=2$ we can write the four symbols as ( ) [ ]. The shift space $X$ comprises all sequences on these symbols in which the brackets are "opened and closed in the right order". So for example, ( ) [ ] is a legal word, as is ( ( ( ) [ ] [, but ( [ [ ) is illegal because the ( bracket cannot be closed before the [ brackets are.

Sticking with $n=2$, let $B_-\subset X$ be the set of all sequences in which every left bracket has a corresponding right bracket, and $B_+$ be the set of all sequences in which every right bracket has a corresponding left bracket. One can show that every shift-invariant measure has $\mu(B_- \cup B_+) = 1$ by partitioning the complement into a countable collection of disjoint sets indexed by the location of the first/last left/right bracket with no partner.

Define a map $\pi_+\colon B_+ \to \{0,1,2\}^\mathbb{Z}$ by sending ( to 0, [ to 1, and both ) and ] to 2. Then $\pi_+$ is an isomorphism between the two shift spaces because every right bracket has a corresponding left bracket, and hence its identity as ) or ] is uniquely determined by the rules of the shift. Similarly, the analogous map $\pi_- \colon B_- \to \{0,1,2\}^\mathbb{Z}$ is an isomorphism.

Because every ergodic invariant measure on $X$ is supported on either $B_-$ or $B_+$, we conclude that $h(X) = \log 3$ and that there are exactly two ergodic measures of maximal entropy $\mu_{\pm} = \nu \circ \pi_{\pm}$, where $\nu$ is the $(\frac 13, \frac 13, \frac 13)$-Bernoulli measure on the full 3-shift. Each of these measures gives positive measure to every open set in $X$, and each is of positive entropy -- indeed, each is Bernoulli, which is part of what makes this answer so satisfying to me.

Note that for larger values of $n$ the same argument shows that $h(X) = \log(n+1)$.

Answer by Vaughn Climenhaga for Hausdorff dimension of a subset of Cantor set

2012-02-16T00:24:35Z

The comments by Andreas and Anton give you the answer already to your specific question. Let me give a more general answer, since your question is very representative of a whole class of examples.

The condition that $x_n = 1 \Rightarrow x_{n+1} = 0$ is a Markov condition: the value of $x_{n+1}$ is restricted by the value of $x_n$. In your case you are considering all sequences in $\{0,1\}^\mathbb{N}$ such that the symbol $1$ cannot follow itself; one could also consider more symbols and more complicated restrictions, such as "every occurrence of $2$ can only be followed by $0$ or $2$, but not $1$". See http://en.wikipedia.org/wiki/Subshift_of_finite_type for more details.

Subshifts of finite type (abbreviated SFTs) are also called topological Markov chains, and can be presented in terms of a transition matrix, as described in that Wikipedia article. The logarithm of the largest eigenvalue of the transition matrix is an important quantity called the topological entropy of the SFT.

When you construct a subset of the Cantor set as in your question, the topological entropy turns out to be directly related to the Hausdorff dimension: namely Hausdorff dimension is topological entropy divided by $\log \lambda$, where $\lambda$ is the contraction ratio at each step of the construction of the Cantor set.

We wrote a more detailed description of this in Pesin & Climenhaga, "Lectures on fractal geometry and dynamical systems", or you can find many parts of it in most standard textbooks on dynamical systems.

Answer by Vaughn Climenhaga for Coded Systems and dense subsets

2012-02-16T00:09:03Z

In case the book referred to in Doug Lind's comment didn't have what you're looking for, a proof of this statement can be found in Section 2 of this paper:

Doris Fiebig and Ulf-Rainer Fiebig, Invariants for subshifts via nested sequences of shifts of finite type, Ergodic Theory and Dynamical Systems 21 (2001), pp 1731-1758.

There are also some other references there, including an article by Krieger with the proof, and another paper by Fiebig and Fiebig with lots more information on coded systems.

Answer by Vaughn Climenhaga for partition into the orbits of a dynamical system

2012-02-13T04:45:52Z

Although it appears you've already settled matters with the information in Jon's answer, I'll offer a quick summary and elaboration.

Let $(X,\mathcal{B},\mu)$ be a Lebesgue space (set + $\sigma$-algebra + probability measure) and $P$ the partition into orbits $\mathcal{O}(x) = \{T^n x \mid n\in \mathbb{Z}\}$ for an invertible measure-preserving transformation $T$.

For (3), it's exactly as you say: $\mathcal{B}$ contains each orbit $\mathcal{O}(x)$, and since a set $A$ is $T$-invariant if and only if it is a union of complete $T$-orbits, we get that the $\sigma$-algebra generated by $P$ is precisely the collection of $T$-invariant sets. The completed $\sigma$-algebra generated by $P$ is the collection of sets that are $T$-invariant mod $0$.

Consequently the answer to (1) is yes unless a single orbit carries full measure: ergodicity implies that every element of the $\sigma$-algebra generated by $P$ has measure $0$ or $1$, and consequently this $\sigma$-algebra is equivalent mod $0$ to the trivial $\sigma$-algebra. Thus for an ergodic transformation, $P$ is measurable if and only if a single partition element has full measure, which happens exactly when $\mu$ is supported on a single periodic orbit.

Finally, for (2), you observe correctly that non-measurability of $P$ follows as soon as $\mu$ has an ergodic component that is not a periodic orbit. For a concrete example, one may consider the map $T\colon [0,1]\to[0,1]$ that takes $x$ to $2x \pmod 1$, and the measure $\mu = \frac 12(\delta_0 + \lambda)$, where $\delta_0$ is the point mass on the fixed point at $0$, and $\lambda$ is Lebesgue measure. In this case $\mu$ is non-ergodic but $P$ is non-measurable. Or, if you prefer a completely non-atomic example, you can let $\nu_p$ denote the $T$-invariant measure on $[0,1]$ that comes from the $(p,1-p)$-Bernoulli measure on the full two-shift (where $p\in (0,1)$) and let $\mu$ be any convex combination of $\nu_p$ and $\nu_q$ for $p\neq q$.

Answer by Vaughn Climenhaga for Is there any expression for the Feigenbaum constants ?

2012-02-07T04:25:29Z

The Feigenbaum constant is the largest eigenvalue of the derivative of the renormalisation operator at its unique fixed point. There is a beautiful article of Lyubich in the October 2000 Notices of the AMS, entitled "The Quadratic Family as a Qualitatively Solvable Model of Chaos", in which he summarises the connection between universality and renormalisation (pages 1046, 1049-1051).

That doesn't directly answer your question, but hopefully that interpretation of the Feigenbaum constant, together with Lyubich's article and/or the references therein, may be of interest.

Answer by Vaughn Climenhaga for absolute continuity on $R^{n}$

2012-02-01T03:15:52Z

I guess it may depend on exactly which property of absolutely continuous functions you think is most important to keep, or to put it another way, exactly which definition you prefer in one dimension. For me the most commonly useful property of absolutely continuous functions is that they map sets of Lebesgue measure zero to sets of Lebesgue measure zero.

Pulling in roughly equal parts from my memory of real analysis and what Wikipedia and EoM tell me, the story seems to be that a function $f\colon [a,b] \to \mathbb{R}$ is absolutely continuous if and only if all three of the following hold (Banach–Zaretskii theorem):

$f$ is continuous;
$f$ is of bounded variation;
the Luzin N property holds: if $E$ has Lebesgue measure $0$, then so does $f(E)$.

Each of these 3 properties generalises to higher dimensions. The first and third are immediate; the second requires a slightly different definition of variation than in one dimension, but is a completely standard thing.

Thus one could say that a function $f\colon \mathbb{R}^m \to \mathbb{R}^n$ is "absolutely continuous" if those three properties hold, and to me this seems a very reasonable generalisation of the usual definition. (Of course one could extend this to maps between smooth manifolds, where you also have a notion of zero volume.)

This seems to be different from the definition that Malý uses in the paper Tapio Rajala referred to in his answer. From a quick glance at that paper, there seem to be a number of different generalisations out there, and this seems to be another example of the phenomenon wherein various notions that are distinct in higher dimensions happen to all coincide in the lowest-dimensional case, so that you can generalise some aspects of the familiar setting, but not all. Which generalisation is useful depends on what your purpose is.

Connectedness of space of ergodic measures

2011-12-21T00:34:27Z

Let $X = \Sigma_p^+ = \{1,\dots,p\}^\mathbb{N}$ and let $f=\sigma\colon X\to X$ be the shift map. Let $\mathcal{M}$ be the space of Borel $f$-invariant probability measures on $X$ endowed with the weak* topology.

Now $\mathcal{M}$ is a Choquet simplex, and hence connected. The geometry of its extreme points is a little more subtle. These extreme points are precisely the ergodic measures. Let $\mathcal{M}^e$ denote the collection of ergodic measures in $\mathcal{M}$. Note that $\mathcal{M}^e$ has some nice properties; for instance, there is a natural embedding from the space of Hölder continuous functions into $\mathcal{M}^e$ that takes $\phi$ to its unique equilibrium state $\mu_\phi$. The image of the embedding is the collection of Gibbs measures (for Hölder potentials).

Of course, there are many ergodic measures that do not arise as equilibrium states of Hölder continuous functions, and so I wonder which nice properties of the collection of Gibbs measures extend to $\mathcal{M}^e$. In particular: Is $\mathcal{M}^e$ connected? Path connected? I expect that it is, and that moreover this should happen whenever $X$ is a compact metric space and $f\colon X\to X$ is a continuous map satisfying the specification property, but I don't know a reference and don't yet see how to approach a proof.

Answer by Vaughn Climenhaga for Connectedness of space of ergodic measures

2011-12-22T17:20:04Z

I'll flesh out the consequences of Gerald's comment in a (CW-ed) answer. Lindenstrauss, Olsen, and Sternfeld showed in 1978 that if $S_1$ and $S_2$ are compact metrisable simplices such that the extremal points of $S_i$ are dense in $S_i$ for $i=1,2$, then there is an affine homeomorphism from $S_1$ to $S_2$; the unique (up to affine homeomorphism) compact metrisable simplex with the property that its extremal points are dense is called the Poulsen simplex.

In that same paper, it was shown that the Poulsen simplex has the property that its set of extremal points is arc-connected. Since $\mathcal{M}$ is a compact metrisable simplex whenever $X$ is a compact metric space and $f\colon X\to X$ is continuous, and the extremal points of $\mathcal{M}$ are precisely the ergodic measures $\mathcal{M}^e$, it follows that $\mathcal{M}^e$ is arc-connected whenever it is dense in $\mathcal{M}^e$. In particular, the strong specification property introduced by Bowen implies that periodic orbit measures are dense in $\mathcal{M}^e$ (Sigmund 1974), and since such measures are ergodic, this implies that $\mathcal{M}$ is the Poulsen simplex, and hence $\mathcal{M}^e$ is arc-connected, whenever $(X,f)$ has strong specification.

So that's not quite as constructive a proof as the approach following (Sigmund 1977) as suggested in Andrey's answer and the comment following, but it's certainly simpler to write down based on existing results.

Answer by Vaughn Climenhaga for Measure of large cylinder sets

2011-12-15T21:18:17Z

So far as I know the best result you can hope for in full generality is the Shannon-McMillan-Breiman Theorem that you quote: If $(X,\sigma)$ is a shift space and $\mu$ is an ergodic shift-invariant measure on $X$, then for every $\epsilon>0$ and $\delta>0$ there exists $N$ such that for every $n\geq N$ one has $$ \mu \left\{ x \mid \mu(C_n(x)) \in [e^{-n(h(\mu) + \epsilon)}, e^{-n(h(\mu) - \epsilon)}] \right\} \geq 1-\delta. $$

Any tighter bounds essentially amount to having a Gibbs property of some sort for the measure, which usually comes from knowing that the measure is an equilibrium state for a reasonably behaved potential function, ie., $h(\mu) + \int \phi\,d\mu = P(\phi) = \sup_\nu (h(\nu) + \int \phi\,d\nu)$, where the supremum is taken over all invariant probability measures. The classical Gibbs property says that if $X$ is an irreducible shift of finite type and $\phi$ is Hölder continuous, then the equilibrium state $\mu$ is unique and has the property that there is a constant $K$ such that $$ \frac 1K \leq \frac{\mu(C_n(x))}{e^{-nP(\phi) + S_n\phi(x)}} \leq K, $$ where $S_n\phi(x) = \phi(x) + \phi(\sigma x) + \cdots + \phi(\sigma^{n-1} x)$ is the $n$th ergodic sum. Note that $\frac 1n S_n\phi(x) \to \int \phi\,d\mu = P(\phi) - h(\mu)$ for $\mu$-a.e. $x$, so the denominator grows like $e^{-nh(\mu)}$, and the fluctuations in $\mu(C_n(x))$ are directly tied to fluctuations in the ergodic sums $S_n\phi$. (In particular, if $X$ is an irreducible SFT and $\mu$ is the unique measure of maximal entropy, then you get $\mu(C_n(x))/e^{-nh(\mu)} \in [K^{-1},K]$ for all $n$ and $x$, which is a very tight set of bounds.)

There are also weak Gibbs properties available in some settings where $X$ is not an SFT or $\phi$ is not Hölder, but to get into those I'd need a better idea of the particular setting you're interested in.

Margulis-Ruelle inequality for piecewise continuous interval maps

2011-11-02T04:27:32Z

The Margulis-Ruelle inequality states that measure-theoretic entropy is controlled by Lyapunov exponents; more precisely, if $f$ is a $C^{1+\alpha}$ diffeomorphism on a $d$-dimensional manifold $M$ and $\mu$ is a Borel $f$-invariant ergodic probability measure with Lyapunov exponents $\lambda_1, \dots, \lambda_d$, then $h_\mu(f) \leq \sum_{\lambda_i>0} \lambda_i$.

This also holds for non-invertible $C^1$ interval maps: we have $h_\mu(f) \leq \max(0,\lambda(\mu))$, where $\lambda(\mu) = \int \log|f'(x)|\,d\mu(x)$. (See, for example, Proposition 4.1 of [Ledrappier, Some properties of absolutely continuous invariant measures on an interval, Ergodic Theory Dynam. Systems 1 (1981), 77-93].)

Question: Has this result been proved for piecewise $C^1$ interval maps? I would be surprised if it is not true in this setting, but neither I nor anyone I've asked has been able to produce a reference to a proof in the case where $f$ is a piecewise monotonic interval map without any assumption of Markov structure.

Comment by Vaughn Climenhaga

2013-05-11T04:56:45Z

I assume that the extra requirement in Brin-Stuck and Katok-Hasselblatt is purely in order to simplify certain aspects of the exposition elsewhere, because as you say, the proof of this result is the same. One simplification they may obtain (caveat - I'm writing this without either of the books at hand) is that when you define expansivity, you use a different definition for homeomorphisms than for non-invertible maps. So if you are writing an account of the whole theory, you can either do everything twice, or decide to deal strictly with homeomorphisms and not worry about optimal results.

Comment by Vaughn Climenhaga

2013-05-10T21:38:31Z

Thanks Ian, I thought it was in there this way also.

Comment by Vaughn Climenhaga

2013-05-10T21:15:23Z

It's stated this way (actually in a more general form, for pressure as well) in Peter Walters, "A variational principle for the pressure of continuous transformations", American Journal of Mathematics **97**(4), 1975, pp. 937-971. I don't have Walters' book handy to see if he states it his way there as well.

Comment by Vaughn Climenhaga

2013-04-29T16:54:52Z

In the formula for $L_{n,P}$, what is $|g|$?

Comment by Vaughn Climenhaga

2013-04-24T13:17:05Z

Can you clarify exactly what you mean by "entropy of the edit distance"?

Comment by Vaughn Climenhaga

2013-02-23T05:14:55Z

One answer is that this is a special case of the Birkhoff ergodic theorem since Markov measures are ergodic. This doesn't require aperiodicity, just irreducibility and positive recurrence. (I guess you consider a Markov chain with countable state space?) For a stronger result, that uses irreducibility, you can look at the Perron-Frobenius theorem, which shows that in fact if $\mu_n$ is any sequence of probability distributions on the state space that evolves according to the Markov law, then $\mu_n$ converges to the stationary distribution, without the need for Cèsaro averages.

Comment by Vaughn Climenhaga

2013-02-11T16:31:37Z

As a mathematician and not a biologist, I'm not the most qualified to speak to the biological relevance of the model. The fact that it was a biologist and not a mathematician who wrote the paper popularising the model suggests to me that it is of more than just mathematical interest. I think his paper itself may have a better discussion of this issue.

Comment by Vaughn Climenhaga

2013-02-11T15:00:11Z

The logistic map $x\mapsto \lambda x(1-x)$ was popularised by a biologist, Robert May, in a 1976 paper in Nature, where it is indeed motivated by considering the dynamics of a population with non-overlapping generations. Presence or absence of "chaotic" behaviour depends in a quite subtle manner on the parameter $\lambda$, but for a positive measure set of parameter values, there is an absolutely continuous invariant measure and positive Lyapunov exponent, which is interpreted as chaos. (The logistic equation $\dot{x} = \lambda x(1-x)$ also models population growth, but without chaos.)

Comment by Vaughn Climenhaga

2013-02-08T14:41:59Z

Hmm. Yes, there are some subtleties I seem to have skimmed over. I'll try to flesh this answer out and be sure it's actually correct.

Comment by Vaughn Climenhaga

2013-01-12T20:05:14Z

As it stands this is a very broad question and I'm not sure it's possible to give a good answer. You'll probably get more helpful responses if you ask about specific examples/counterexamples that you'd like to see or understand better.

Comment by Vaughn Climenhaga

2012-12-05T19:01:36Z

As the 3 simultaneous answers below point out, existence follows from continuity. I've deleted my answer as Pietro gives a better explanation.

Comment by Vaughn Climenhaga

2012-12-03T14:45:22Z

It does raise the further point that transitivity depends on whether you consider $n\in \mathbb{N}$ or $n\in \mathbb{Z}$. Your examples are transitive in the latter sense but not in the former. So I suppose really one should add another element to the diagram, distinguishing between these two possibilities (I think I implicitly used forward transitivity without clearly specifying that). Now we have (at least) 4 definitions of transitivity (dense orbit/open sets, $\mathbb{N}$/$\mathbb{Z}$). I think the examples in the answer all satisfy either all or none of those definitions.

Comment by Vaughn Climenhaga

2012-12-03T14:42:30Z

@Ian: Ah yes, I see that indeed I did manage to misunderstand your examples. When you said "homoclinic orbit" I pictured a continuous loop based at the fixed point (likely because I'm teaching ODEs this term so I pictured a homoclinic trajectory for an ODE). Of course that's not what you meant, and now that I understand your examples as being one or more fixed points together with a discrete orbit, I agree there is a dense orbit.

Comment by Vaughn Climenhaga

2012-12-03T01:32:06Z

@Ian: I'm not sure about your homo/heteroclinic orbit examples for 8, 1 - I don't see where transitivity should come from, unless I'm misunderstanding the example. Your suggestion for 9 amounts to gluing together two copies of the present example, but one copy seems to do the trick. Certainly you're correct on 6, though I find it marginally unsatisfying to cite the trivial example.

Comment by Vaughn Climenhaga

2012-12-03T01:29:29Z

@Andres: As you say, the north-south map should have endpoints identified, I've edited.