COMPUTING INVARIANT

DENSITIES AND METRIC ENTROPY

Mark Pollicott and Oliver Jenkinson

University of Manchester and Institut de Mathématiques de Luminy

Abstract. We present a method for accurately computing the metric entropy (or, equivalently, the Lyapunov exponent) of the absolutely continuous invariant measure μ for a piecewise analytic expanding Markov map T of the interval. We construct atomic signed measures μ_{M} supported on periodic orbits up to period M, and prove that ∫ log |T′| dμ_{M} → h(μ) super-exponentially fast. We illustrate our method with several examples.

0. The problem

Let T : I → I be a piecewise C^{2} expanding map of the interval. By the Lasota-Yorke theorem [L-Y] we know there exists a T -invariant probability measure μ which is absolutely continuous with respect to Lebesgue measure. If T is topologically mixing then this absolutely continuous invariant measure (abbreviated to a.c.i.m.) is unique and ergodic, with strictly positive C^{1} density function ρ : I → ℝ.

In the special case of the continued fraction transformation T x = 1/x (mod 1) the density is ρ(x) = ((1+x) log 2)^{−1}. For the Ulam-von Neumann map T x = 4x(1−x), which is topologically conjugate to the expanding tent map τ(x) = 1 − |2x − 1|, the density is known to be ρ(x) = π^{−1}(x(1 − x))^{−1/2}. Finally, Parry [Pa] and Renyi [Renyi] studied the problem for certain piecewise linear examples, including the β-transformation defined by T x = βx (mod 1), for any β > 1. However, in general there is no explicit formula for the density function, and much recent interest has focused on approximating the density [HuntB], [Froy1], [Froy2], [HuntF], [K-M-Y], [M], with particular emphasis on Ulam’s method [Ulam]. In this note we will present an alternative approach.

We shall only consider the case where T is a real analytic Markov map. In this case a well-known approach to finding the a.c.i.m. μ is given by the weighted distribution of periodic orbits. More precisely, the sequence of atomic T -invariant probability measures

m_{M} = \frac{∑_{x∈Fix(M)} δ_{x}/|(T^{M})′(x)|}{∑_{x∈Fix(M)} 1/|(T^{M})′(x)|}, M ≥ 1  (0.1)

(where the summations are over the set Fix(M) = {x ∈ I : T^{M}x = x} of period-M points) converges to μ in the weak-star topology (see [K-H, p. 635]). That is, for each k ∈ ℤ,

∫_{0}^{1} e^{2πikx}dm_{M}(x) → μ̂(k) := ∫_{0}^{1} e^{2πikx}dμ(x).

Typeset by AMS-TEX

This convergence can be shown to be exponentially fast (see section 4), the rate being determined by the second eigenvalue of the Perron-Frobenius operator L_{T} (defined in section 1).

In this note we will present a rather more efficient method of computing these Fourier coefficients μ̂(k). We achieve this by a more elaborate regrouping of the periodic points to define new invariant signed probability measures μ_{M} by

μ_{M} = \frac{1}{N_{M}} ∑_{\begin{matrix}(n_{1},... ,n_{m}) \\ n_{1}+...+n_{m}≤M \end{matrix}} \frac{(−1)^{m}}{m!} ∑_{i=1}^{m} ∑_{x∈Fix(n_{i})} (∏_{{j=1 \atop j≠i}}^{m} ∑_{z∈Fix(n_{j})} r(z, n_{j})) \frac{δ_{x}}{|(T^{n_{i}})′(x) − 1|}.

where we denote

r(x, n) = \frac{1}{n|(T^{n})′(x) − 1|},

and the normalisation constant N_{M} is simply

N_{M} = ∑_{\begin{matrix}(n_{1},... ,n_{m}) \\ n_{1}+...+n_{m}≤M \end{matrix}} \frac{(−1)^{m}}{m!} ∑_{i=1}^{m} ∑_{x∈Fix(n_{i})} (∏_{{j=1 \atop j≠i}}^{m} ∑_{z∈Fix(n_{j})} r(z, n_{j})) \frac{1}{|(T^{n_{i}})′(x) − 1|}.

Note in particular that the measures μ_{M} are supported on those periodic points of period at most M.

The advantage of these more involved definitions is that in the case when T is C^{ω} we have the following superexponential convergence of the Fourier coefficients.

Theorem 1. Suppose that T : I → I is a piecewise C^{ω} expanding Markov map of the interval, with absolutely continuous invariant probability measure μ. There is a sequence of T -invariant signed probability measures μ_{M}, supported on the points of period at most M, and 0 < θ < 1, such that for each k ∈ ℤ, there exists C > 0 with

|∫_{0}^{1} e^{2πkix}dμ_{M}(x) − μ̂(k)| ≤ Cθ^{M^{2}}.

More generally, for any real analytic function g : I → ℝ, we can similarly see that | ∫_{0}^{1} g(x)dμ_{M}(x) − ∫_{0}^{1} g(x)dμ(x)| ≤ Cθ^{M^{2}}. Of particular interest is the choice g(x) = log |T′(x)|, since by the Rohlin-Pesin equality [Ro], [Pe] we can identify the metric entropy h_{μ}(T) with such an integral,

h_{μ}(T) = ∫ log |T′(x)|dμ(x).  (0.2)

The ergodic theorem means that h_{μ}(T) equals the Lyapunov exponent

lim_{n→+∞} \frac{1}{n} log |(T^{n})′(x)|

for Lebesgue almost all x.

Combining identity (0.2) with the method of proof of Theorem 1, we also prove Theorem 2. Suppose that T : I → I is a piecewise C^{ω} expanding Markov map of the interval, with absolutely continuous invariant probability measure μ. There is a sequence of T -invariant signed probability measures μ_{M}, supported on the points of period at most M, and constants 0 < θ < 1, C > 0, such that |h_{μ}(T) − ∫ log |T′| dμ_{M}| ≤ Cθ^{M^{2}}.

We organise the article as follows. In section 1 we collect together a few easy results on expanding piecewise-analytic Markov interval maps, and consider analytically parametrised families of such maps. In section 2 we show that the measures μ_{M} converge to the a.c.i.m. μ. In section 3 we consider the speed of convergence, and prove our theorems. In section 4 we use our methods to estimate the entropy of the a.c.i.m. for two families of examples.

Acknowledgments. We are grateful to an anonymous referee for a number of helpful suggestions.

1. Some simple properties of the density and metric entropy

Consider a piecewise C^{ω} expanding Markov interval map T : I → I. By this we mean

(a) there exists a partition 0 = a_{0} < a_{1} < … < a_{p} = 1 such that T is realanalytic on each [a_{i}, a_{i+1}] (i.e. extends to a holomorphic map on some complex neighbourhood of [a_{i}, a_{i+1}]),

(b) there exists κ > 1 such that |T′(x)| ≥ κ for all x ∈ I,

We shall also assume for convenience that T [a_{i}, a_{i+1}] = I for all i. This condition is not essential, but eases the exposition in the sequel. In particular it implies T is topologically mixing. A more general definition of a Markov map would allow each image T [a_{i}, a_{i+1}] to be some union ∪_{j∈J}[a_{j}, a_{j+1}] of pieces in the partition. Under this hypothesis, the invariant density ρ in Lemma 1 would only be C^{ω} on each piece of the partition. Moreover, the various function spaces we consider would be defined relative to the partition, and would consist of functions with some prescribed regularity on each piece of the partition.

Let μ denote the unique ergodic a.c.i.m. [C-E] and let ρ ∈ L^{1}(I) denote the associated density (or Radon-Nikodym derivative) i.e., dμ(x) = ρ(x)dλ(x), where λ is Lebesgue measure. In general it is not possible to find an explicit expression for the density ρ.

We can define the Perron-Frobenius operator L_{T} : C^{0}(I) → C^{0}(I) by

L_{T} k(x) = ∑_{T y=x} \frac{k(y)}{|T′(y)|}, k ∈ C^{0}(I).

Recall that the space of real-analytic functions C^{ω}(I) is a Fréchet space. If we fix some open complex neighbourhood U of I, then the space of bounded holomorphic functions on U is a Banach space with respect to the uniform norm.

Lemma 1. The density ρ is a real-analytic function, and satisifies Lρ = ρ.

This is a standard result following from the change of variable formula (cf. [K-H, p. 186]), the latter observation following immediately from the fact that L preserves C^{ω}(I), i.e., LC^{ω}(I) ⊂ C^{ω}(I).

Lemma 2. Suppose the metric entropy h_{μ}(T) is equal to the topological entropy h(T). Then the map T is C^{ω} conjugate to a piecewise linear map whose slope on each partition piece is ±p, where p is the number of pieces in the Markov partition.

A simple calculation with Radon-Nikodym derivatives [K-H, p. 187] gives

\frac{dμT}{dμ} (x) = \frac{d(μT)}{d(λT)} \frac{d(λT)}{dλ} \frac{dλ}{dμ} = ρ(T x)|T′(x)|ρ(x)^{−1}.  (1.1)

By T -invariance of μ the jacobian dμT/dμ must satisfy

∑_{T y=x} (\frac{dμT}{dμ} (y))^{−1} = 1, a.e.  (1.2)

If h_{μ}(T) = h(T), then μ is the unique measure of maximal entropy, so (see [Wal1]) − log |T′| is an essential coboundary. Thus − log \frac{dμT}{dμ} is also an essential coboundary (i.e. − log \frac{dμT}{dμ} = vT − v + c for some real c and bounded measurable function v). But then (1.2) implies \frac{dμT}{dμ} must itself be constant, and that this constant is precisely p.

Therefore, if we assume that 0 is a fixed point, for convenience, then by (1.1) we deduce T is conjugate to the required piecewise linear map by the conjugacy h(x) = ∫_{0}^{x} ρ(x)dx.

Lemma 3. Let T_{ε} (−a < ε < a) be a family of C^{ω} expanding Markov maps, which vary analytically with the parameter ε, and with a.c.i.m. μ_{ε}. Then the associated metric entropies h(μ_{ε}) also vary analytically.

The invariant density ρ_{ε} for T_{ε} satisfies L_{T_{ε}}ρ_{ε} = ρ_{ε} (by Lemma 1). Moreover, the maximal eigenvalue 1 for L_{T_{ε}} is simple and isolated. It follows from standard analytic perturbation theory that the map ε ↦ ρ_{ε} ∈ C^{ω}(I) is C^{ω} [Kato]. By (0.2) we can write h(μ_{ε}) = ∫ log |T′_{ε}|ρ_{ε}(x)dx, from which Lemma 3 immediately follows.

Let us now consider the specific family of maps T_{ε} : [0, 1] → [0, 1] defined by

T_{ε}(x) = 2x + ε sin 2πx (mod 1), for − \frac{1}{2π} < ε < \frac{1}{2π} .

These maps are all analytic and expanding. They are also topologically conjugate to the standard doubling map T_{0} : I → I, from which we deduce that the topological entropy h(T_{ε}) is equal to log 2 (indeed the same is true for any degree-2 expanding map [K-H, Theorem 2.4.2]).

By the variational principle (see for example [Wal2]), the metric entropy of the a.c.i.m. μ_{ε} must necessarily satisfy h(μ_{ε}) ≤ log 2. The following lemma is an easy consequence of Lemma 2.

Lemma 4. For ε ≠ 0 the map T_{ε} has metric entropy h(μ_{ε}) < log 2

If we assume for a contradiction that h(μ_{ε}) = log 2 then Lemma 1 implies that T_{ε} is C^{ω} conjugate to the linear map with derivative 2. However, when we compute the derivative at the fixed point 0 we see (T′_{ε})(0) = 2(1 − ε), whereas it is required to take the value T′_{ε}(0) = 2, giving the required contradiction.

Indeed we can derive a second order approximation of h(μ_{ε}) as follows.

Proposition 1. h(μ_{ε}) = log 2 − \frac{π^{2}}{4} ε^{2} + O(ε^{3}) as ε → 0.

Proof. The Rohlin-Pesin identity gives

h(μ_{ε}) = ∫ log |T′_{ε}(x)|ρ_{ε}(x)dx,  (1.3)

where ρ_{ε} is the invariant density for T_{ε}. By Lemma 3, we know the entropy h(μ_{ε}) varies analytically, so let us write h(μ_{ε}) = log 2 + h_{1}ε + h_{2}ε^{2} + O(ε^{3}), where the coefficients h_{1}, h_{2} are to be determined.

We have the expansions

log |T′_{ε}(x)| = log 2 + επ cos(2πx) − \frac{ε^{2}π^{2}}{2} cos^{2}(2πx) + O(ε^{3})

and

ρ_{ε}(x) = 1 + ρ^{1}(x)ε + ρ^{2}(x)ε^{2} + O(ε^{3}).

The functions ρ^{1}, ρ^{2} satisfy ∫ ρ^{1}(x) dx = 0 = ∫ ρ^{2}(x) dx, since ∫ ρ_{ε}(x) dx = 1 for all ε. Substituting the expansions into (1.3), and comparing coefficients, we immediately deduce that h_{1} = 0. Comparing second order terms we have

h_{2} = log 2 ∫ ρ^{2}(x)dx + π ∫ cos(2πx)ρ^{1}(x)dx − \frac{π^{2}}{2} ∫ cos^{2}(2πx)dx.  (1.4)

The first term on the right-hand side of (1.4) is zero, by the previous comment.

We now claim that the function ρ^{1} is identically zero. Once we have established this, the second term on the right-hand side of (1.4) will vanish to leave h_{2} = −\frac{π^{2}}{2} ∫ cos^{2}(2πx)dx = −π^{2}/4, as required.

Let σ_{ε} be the inverse branch of T_{ε} which is close to x ↦ x/2. We can write σ_{ε}(x) = x/2 + εσ^{1}(x) + O(ε^{2}), and using the identity x = T_{ε}(σ_{ε}(x)), we derive σ^{1}(x) = −\frac{1}{2} sin(πx). If τ_{ε} is the inverse branch near x ↦ (x + 1)/2, then we can write τ_{ε}(x) = (x + 1)/2 + ετ^{1}(x) + O(ε^{2}), and a similar argument gives τ^{1}(x) = \frac{1}{2} sin(πx) = −σ^{1}(x).

Since ρ_{ε} is a fixed point of the Perron-Frobenius operator L_{T_{ε}} we have

ρ_{ε}(x) = L_{T_{ε}}ρ_{ε}(x) = ρ_{ε}(σ_{ε}x)σ′_{ε}(x) + ρ_{ε}(τ_{ε}x)τ′_{ε}(x).  (1.5)

Substituting the various series expansions into (1.5), and considering the linear term in ε, we obtain

\begin{aligned}ρ^{1}(x) & = \frac{1}{2} (ρ^{1} (\frac{x}{2}) + ρ^{1} (\frac{x + 1}{2})) + (σ^{1})′(x) + (τ^{1})′(x) \\ & = \frac{1}{2} (ρ^{1} (\frac{x}{2}) + ρ^{1} (\frac{x + 1}{2})) . \end{aligned}

We thus deduce that ρ^{1} = L_{T_{0}}ρ^{1}, so that ρ^{1} lies in the eigenspace spanned by the invariant density for the doubling map T_{0}. That is, ρ^{1} is a constant. Having already observed that ∫ ρ^{1}(x)dx = 0, we finally deduce that ρ^{1} is identically zero, as required.

Figure 1. Entropy h(μ_{ε}) and second order approximation log 2 − \frac{π^{2}}{4} ϵ^{2} (dashed)

In Figure 1 we compare h(μ_{ε}) to the second order approximation derived in Proposition 1.

2. Convergence of the measures μ_{M}

In this section we shall show that the measures μ_{M} converge to the a.c.i.m. μ. In section 3 we shall study the rate of convergence.

In section 1, we considered the Perron-Frobenius operator. In our proof of Theorem 1 we need to modify this definition slightly. More generally, for any Hölder continuous function f : I → ℝ we can define the transfer operator L_{f} : C^{0}(I) → C^{0}(I) by

L_{f}k(x) = ∑_{T y=x} k(y)e^{f(y)}.

This operator L_{f} has a simple isolated maximal eigenvalue at the point e^{P (f)}, where

P (f) = P (f, T) = lim_{n→∞} \frac{1}{n} log ∑_{x∈Fix(n)} e^{f^{n}(x)}

is the pressure of f, and we denote f^{n}(x) = f(x) + f(T x) + … + f(T^{n−1}x)[Bowen].

Given an analytic function g : I → ℝ and t ∈ ℝ we choose

f(x) = − log |T′(x)| + tg(x).

The maximal eigenvalue of the corresponding transfer operator L_{− log |T′|+tg} is therefore exp P (− log |T′| + tg). We define z(t) to be its reciprocal

z(t) := exp [−P (− log |T′| + tg)] .

Note that setting t = 0 gives z(0) = exp [−P (− log |T′|)] = 1, since 1 is the maximal eigenvalue of the Perron-Frobenius operator L_{T}. We want to relate this to the integral of the function g with respect to the a.c.i.m. μ via the following formula.

Lemma 5.

∫ g dμ = \frac{d}{dt}P (− log |T′| + tg)|_{t=0} .

(see [Ru2, p.133], [Pa-Pol, p.60]).

In particular, since z(0) = 1, Lemma 5 implies that

∫ g dμ = −\frac{d}{dt} log z(t)|_{t=0} = −\frac{z′(0)}{z(0)} = −z′(0).  (2.1)

We next want to relate the integral to the periodic points of T : I → I. For a point x ∈ Fix(n) we denote

r(x, n) = \frac{1}{n|(T^{n})′(x) − 1|}.

Summing over all such points we let

a_{n} = a_{n}(t) = ∑_{x∈Fix(n)} r(x, n)e^{tg^{n}(x)},

and then formally define the Fredholm determinant F (z, t) by

F (z, t) = exp (− ∑_{n=1}^{∞} a_{n}(t)z^{n}) = exp (− ∑_{n=1}^{∞} \frac{z^{n}}{n} ∑_{x∈Fix(n)} \frac{e^{tg^{n}(x)}}{|(T^{n})′(x) − 1|}) .

In section 3 we will show that in fact F (z, t) is an entire function of both z and t. For the moment let us assume this, and relate F to the expression (2.1) for ∫ g dμ. The first step is the following lemma.

Lemma 6. The function z(t) := exp [−P (− log |T′| + tg)] gives an implicit solution to F (z(t), t) = 0 satisfying z(0) = 1.

Proof. Note that z(t) = exp [−P (− log |T′| + tg)] = lim sup_{n→∞} |a_{n}(t)|^{1/n} is the radius of convergence of the power series ∑_{n=1}^{∞} a_{n}(t)z^{n}, and hence a zero of F (cf. [Ru2, p. 142], where similar statements hold for zeta functions). The fact that z(0) = 1 was noted above.

Now by the implicit function theorem we have that

z′(0) = −\frac{D_{2}F (z(0), 0)}{D_{1}F (z(0), 0)} = −\frac{D_{2}F (1, 0)}{D_{1}F (1, 0)}  (2.2)

where D_{i}F (z, t), i = 1, 2, denotes the partial derivative of F with respect to the i^{th} variable. Thus by (2.1) we can write

∫ g dμ = z′(0) = \frac{D_{2}F (1, 0)}{D_{1}F (1, 0)}.  (2.3)

We will now use the expression (2.3) to compute ∫ g dμ. Both numerator and denominator can be expressed as series of rapidly decreasing terms, as follows. Using the expansion e^{−x} = 1 + ∑_{m=1}^{∞}(−1)^{m} \frac{x^{m}}{m!} we can expand

F (z, t) = 1 + ∑_{N=1}^{∞} C_{N}(t)z^{N},

where

C_{N}(t) = ∑_{\begin{matrix}(n_{1},... ,n_{m}) \\ n_{1}+...+n_{m}=N \end{matrix}} \frac{(−1)^{m}}{m!} a_{n_{1}}(t) … a_{n_{m}}(t).  (2.4)

(Note the above summation is over all m-tuples of positive integers whose sum is equal to N). With this expansion for F (z, t) we can now calculate its partial derivatives, as follows.

\begin{aligned}D_{1}F (z, t) & = ∑_{N=1}^{∞} NC_{N}(t)z^{N−1} \\ D_{2}F (z, t) & = ∑_{N=1}^{∞} C′_{N}(t)z^{N} \end{aligned}

We can explicitly compute the derivative C′_{N}(t) as

\begin{aligned}C′_{N}(t) & = \frac{d}{dt} ( ∑_{\begin{matrix}(n_{1},... ,n_{m}) \\ n_{1}+...+n_{m}=N \end{matrix}} \frac{(−1)^{m}}{m!} a_{n_{1}}(t) … a_{n_{m}}(t)) \\ & = ∑_{\begin{matrix}(n_{1},... ,n_{m}) \\ n_{1}+...+n_{m}=N \end{matrix}} \frac{(−1)^{m}}{m!} ∑_{i=1}^{m} a′_{n_{i}}(t) ∏_{\begin{matrix}j=1 \\ j≠i \end{matrix}}^{m} a_{n_{j}}(t). \end{aligned}

Setting t = 0, and recalling the notation g^{n_{i}}(x) = g(x)+g(T x)+…+g(T^{n_{i}−1}x), we obtain the following expression:

C′_{N}(0) = ∑_{\begin{matrix}(n_{1},... ,n_{m}) \\ n_{1}+...+n_{m}=N \end{matrix}} \frac{(−1)^{m}}{m!} ∑_{i=1}^{m} ∑_{x∈Fix(n_{i})} r(x, n_{i})g^{n_{i}}(x) ∏_{\begin{matrix}j=1 \\ j≠i \end{matrix}}^{m} ∑_{z∈Fix(n_{j})} r(z, n_{j}).

Now

∑_{x∈Fix(n_{i})} r(x, n_{i})g^{n_{i}}(x) = ∑_{x∈Fix(n_{i})} \frac{1}{|(T^{n_{i}})′(x) − 1|} \frac{g^{n_{i}}(x)}{n_{i}} = ∑_{x∈Fix(n_{i})} \frac{g(x)}{|(T^{n_{i}})′(x) − 1|},

so that

\begin{aligned}C′_{N}(0) & = ∑_{\begin{matrix}(n_{1},... ,n_{m}) \\ n_{1}+...+n_{m}=N \end{matrix}} \frac{(−1)^{m}}{m!} ∑_{i=1}^{m} ∑_{x∈Fix(n_{i})} \frac{g(x)}{|(T^{n_{i}})′(x) − 1|} ∏_{{j=1 \atop j≠i}}^{m} ∑_{z∈Fix(n_{j})} r(z, n_{j}) \\ & = ∫ g dν_{N}, \end{aligned}

where we define

ν_{N} = ∑_{\begin{matrix}(n_{1},... ,n_{m}) \\ n_{1}+...+n_{m}=N \end{matrix}} \frac{(−1)^{m}}{m!} ∑_{i=1}^{m} ∑_{x∈Fix(n_{i})} (∏_{{j=1 \atop j≠i}}^{m} ∑_{z∈Fix(n_{j})} r(z, n_{j})) \frac{δ_{x}}{|(T^{n_{i}})′(x) − 1|}.

(2.5)

The sum ν_{1} + … + ν_{M} is a finite signed measure, whose support is a union of periodic orbits. Since all points in a given orbit carry equal mass then ν_{1}+…+ν_{M} is T -invariant. Suitably normalized it gives a signed T -invariant probability measure μ_{M}. This normalization is obtained by summing the first M coefficients in the power series expansion for D_{1}F (z, 0). Thus we define

μ_{M} = \frac{∑_{N=1}^{M} ν_{N}}{∑_{N=1}^{M} NC_{N}(0)}.  (2.6)

Proposition 2. The measures μ_{M} converge to the a.c.i.m. μ in the weak^{∗} topology.

Proof. Let g(x) = e^{2πikx}. Then by (2.3), (2.5), (2.6) we see ∫ e^{2πikx}dμ_{M} → μ̂(k) as M → ∞.

Remark. In general the signed measures μ_{M} need not be positive measures. To see this it suffices to find some M such that ν_{1} + … + ν_{M} gives mass of opposite sign to two of its atoms.

Suppose, for example, that T is symbolically the full shift on two symbols, with two fixed points x_{0} and x_{1}, and a single period-two orbit {x_{01}, x_{10}}. Let e_{i} = |T′(x_{i}) − 1|^{−1} for i = 1, 2.

Using (2.5) for N = 1 and N = 2 gives (ν_{1} + ν_{2})({x_{0}}) = e_{0} [(e_{0} + e_{1}) − 1] and (ν_{1} + ν_{2})({x_{1}}) = e_{1} [(e_{0} + e_{1}) − 1]. These weights are both of the same sign, but this sign might be either positive or negative depending on the derivative of T at x_{0} and x_{1}. In particular we can find T with T′(x_{0}) = \frac{3}{2} and T′(x_{1}) = 3, say, in which case e_{0} + e_{1} = \frac{5}{2} > 1 so that (ν_{1} + ν_{2})(\{x_{0}\}) > 0 and (ν_{1} + ν_{2})(\{x_{1}\}) > 0.

However the period-two point x_{01} is given zero weight by ν_{1}, and negative weight by ν_{2}, so that (ν_{1} + ν_{2})({x_{01}}) < 0 (the same is also true for x_{10}).

3. Speed of approximation

So far in deriving our formulae, we have assumed that F (z, t) is an entire function of both z and t. We now justify this. First recall (see [Gr]) that a bounded linear operator L : B → B of a Banach space B over ℂ is called nuclear if there exist normalised u_{i} ∈ B, normalised l_{i} ∈ B^{∗}, and λ_{i} ∈ ℂ with ∑_{i} |λ_{i}| < ∞ such that

Lw = ∑_{i=1}^{∞} λ_{i}l_{i}(w)u_{i}.

Lemma 7. F (z, t) is an entire function of both z and t.

Proof. For each piece [a_{i}, a_{i+1}] of the Markov partition we let T_{i} : I → [a_{i}, a_{i+1}] denote the corresponding inverse branch of T (i.e. T_{i} ∘ T = id on [a_{i}, a_{i+1}]), and z_{i} ∈ [a_{i}, a_{i+1}] the fixed point of T_{i}.

For \underline{i} = (i_{1}, …, i_{n}), let T\underline{i} denote the composition T_{i_{1}} ∘…∘T_{i_{n}}, and write |\underline{i}| = n. For each such \underline{i}, let z\underline{i} ∈ I denote the unique fixed point of T\underline{i}, and let I\underline{i} denote the image T\underline{i}I.

Let us choose n sufficiently large so that, for each \underline{i} with |\underline{i}| = n, there is an open complex disc D\underline{i} ⊃ I\underline{i} of radius d\underline{i}, centered at z\underline{i}, such that

(a) for each 1 ≤ j ≤ p, T_{j} extends holomorphically to the union D^{(n)} := ∪_{|\underline{i}|=n}D\underline{i}, with \overline{T_{j}(D^{(n)})} a proper subset of D_{j},

(b) e^{tg}/|T′| extends to a holomorphic function on each D\underline{i}, and hence to a holomorphic function (which we denote by ϕ) on the disjoint union D_{n} := ∐_{|\underline{i}|=n} D\underline{i}.

Let B denote the space of functions which are holomorphic on the disjoint union D_{n} and continuous on \overline{D}_{n}. Equipped with the uniform norm, B is a Banach space. The operator L_{− log |T′|+tg} is well-defined on B, and takes the form

L_{− log |T′|+tg}w(z) = ∑_{j=1}^{p} ϕ(T_{j}(z))w(T_{j}(z)).

This operator is then nuclear (see [Ru1, p. 236]), and in particular the trace trace(L_{− log |T′|+tg}^{m}) = ∑_{i=1}^{∞} e_{i}^{m} < ∞ is well-defined for each m, where the e_{i} are the eigenvalues of L_{− log |T′|+tg} counted with multiplicity. By Fredholm theory [Gr] we have the trace formulae

trace(L_{− log |T′|+tg}^{m}) = ( − ∑_{m=1}^{∞} \frac{z^{m}}{m} trace(L_{− log |T′|+tg}^{m})) and this is an entire function of both z and t [Ru1]. The above lemma immediately implies the superexponential decay of the power series coefficients C_{N}(t) of F (z, t). We now give a more precise bound on the rate of decay.

Lemma 8. There exists 0 < θ < 1 such that, for any t ∈ ℂ, C_{N}(t) = O(θ^{N^{2}}).

Proof. To ease the notation, let us write L = L_{− log |T′|+tg}, so that

Lw(z) = ∑_{j=1}^{p} ϕ(T_{j}z)w(T_{j}z) = ∑_{j=1}^{p} L_{j}w(z),

where L_{j}w(z) := ϕ(T_{j}z)w(T_{j}z). Suppose n is chosen sufficiently large as in Lemma 7, and that our Banach space B is as before. Let \underline{i} = i_{1} … i_{n}, and let \underline{i}′ = i_{1} … i_{n−1} be its length-(n − 1) prefix.

We write ϕ\underline{i} := ϕ|_{D\underline{i}}. Observe that, for each j, the function L_{j}w is defined by

(L_{j}w)\underline{i} = w\underline{j} ∘ T_{j}.ϕ\underline{j} ∘ T_{j},  (3.1)

where \underline{j} = j\underline{i}′.

Define D\underline{i}′ to be the disjoint union ∐_{k=1}^{p} D_{\underline{i}′k}, and note that

\overline{T_{j}(D\underline{i}′)} ⊂ D\underline{j}.

Let B\underline{j} be the smallest disc, centered at z\underline{j}, which contains \overline{T_{j}(D\underline{i}′)}. Let β\underline{j} = max_{x∈\overline{T_{j}(D_{\underline{i}}_{′})}} |z\underline{j} − x| denote the radius of B\underline{j}. Clearly we have β\underline{j} < d\underline{j}, so define the contraction ratio α\underline{j} = β\underline{j}/d\underline{j} < 1.

Let Γ\underline{j} be a circle of radius γ\underline{j} centred at z\underline{j}, and such that β\underline{j} < γ\underline{j} < d\underline{j}. Clearly for any given ϵ > 0 we may choose Γ\underline{j} such that β\underline{j}/γ\underline{j} < (1 + ϵ)α\underline{j}.

Cauchy’s formula means that, for z ∈ D\underline{i} ⊂ D\underline{i}′, we can express

(L_{j}w)\underline{i}(z) = w\underline{j}(T_{j}z)ϕ\underline{j}(T_{j}z) = \frac{1}{2πi} ∫_{Γ\underline{j}} \frac{w\underline{j}(ξ)ϕ\underline{j}(ξ)}{ξ − T_{j}z}dξ.

For z ∈ D\underline{i}, ξ ∈ Γ\underline{j} we write

\begin{aligned}(ξ − T_{j}z)^{−1} & = (ξ − z\underline{j})^{−1} (1 − \frac{T_{j}z − z\underline{j}}{ξ − z\underline{j}} )^{−1} \\ & = (ξ − z\underline{j})^{−1} ∑_{r=0}^{∞} (\frac{T_{j}z − z\underline{j}}{ξ − z\underline{j}} )^{r} . \end{aligned}

Note this expansion is valid because |T_{j}z − z\underline{j}| < |ξ − z\underline{j}|, since the circle Γ\underline{j} is outside the image T_{j}(D\underline{i}′). Therefore, for z ∈ D\underline{i} ⊂ D\underline{i}′ we have

(L_{j}w)\underline{i}(z) = ∑_{r=0}^{∞} (T_{j}z − z\underline{j})^{r} \frac{1}{2πi} ∫_{Γ\underline{j}} \frac{w\underline{j}(ξ)ϕ\underline{j}(ξ)}{(ξ − z\underline{j})^{r+1}} dξ,

so that

(Lw)\underline{i}(z) = ∑_{r=0}^{∞} ∑_{j=1}^{p} (T_{j}z − z\underline{j})^{r} \frac{1}{2πi} ∫_{Γ\underline{j}} \frac{w\underline{j}(ξ)ϕ\underline{j}(ξ)}{(ξ − z\underline{j})^{r+1}} dξ.  (3.2)

Now define v_{\underline{j},r} ∈ B and m_{\underline{j},r} ∈ B^{∗} by

v_{\underline{j},r}(z) := \{ \begin{matrix}(T\underline{j}z − z\underline{j})^{r} & if z ∈ D\underline{i}′ \\ 0 & if z ∉ D\underline{i}′. \end{matrix}

and

m_{\underline{j},r}(w) := \frac{1}{2πi} ∫_{Γ\underline{j}} \frac{w\underline{j}(ξ)ϕ\underline{j}(ξ)}{(ξ − z\underline{j})^{r+1}} dξ.

From (3.2) we then have

Lw = ∑_{r=0}^{∞} ∑_{|\underline{j}|=n} m_{\underline{j},r}(w)v_{\underline{j},r}.

Now we just normalise by setting

u_{\underline{j},r} = \frac{v_{\underline{j},r}}{||v_{\underline{j},r}||_{∞}} = \frac{v_{\underline{j},r}}{βr ; \underline{j}} and l_{\underline{j},r} = \frac{m_{\underline{j},r}}{||m_{\underline{j},r}||_{∞}} ,

so that

Lw = ∑_{r=0}^{∞} ∑_{|\underline{j}|=n} λ_{\underline{j},r}l_{\underline{j},r}(w)u_{\underline{j},r},  (3.3)

for coefficients λ_{\underline{j},r} = ||v_{\underline{j},r}||_{∞}||m_{\underline{j},r}||_{∞}. To estimate the decay of these coefficients as r → ∞, we have

λ_{\underline{j},r} = ||v_{\underline{j},r}||_{∞}||m_{\underline{j},r}||_{∞} ≤ βr ; \underline{j} \frac{||ϕ||_{∞}}{2πγr+1 ; \underline{j}} < \frac{||ϕ||_{∞}}{2πγ\underline{j}} (1 + ϵ)αr ; \underline{j}.

Taking ϵ > 0 sufficiently small, we may choose max_{|\underline{j}|=n} α\underline{j} < α < 1 such that

λ_{\underline{j},r} ≤ Kα^{r}  (3.4)

for all |\underline{j}| = n, where

K = ||ϕ||_{∞} (2π min_{|\underline{j}|=n} γ\underline{j})^{−1} = Q||e^{tg}||_{∞},  (3.5)

and Q is a constant depending only on T.

Re-labelling the various functions, functionals, and coefficients in (3.3) we write

Lw = ∑_{q=0}^{∞} λ_{q}l_{q}(w)u_{q},

where the λ_{q} are non-increasing.

���

COMPUTING INVARIANT DENSITIES AND METRIC ENTROPY 13

For any fixed r, there were p^{n} functions of the form u_{\underline{j},r}, and p^{n} functionals of the form l_{\underline{j},r}, so choosing θ_{0} = α^{1/p^{n}} < 1, the estimate (3.4) implies

λ_{q} ≤ Kθ_{0}^{q}.  (3.6)

We now estimate the coefficients C_{N}(t) in the power series expansion of the Fredholm determinant F (z, t). Formally

det(I − zL) = | \begin{matrix}1 − zλ_{1}l_{1}(u_{1}) & −zλ_{1}l_{1}(u_{2}) & −zλ_{1}l_{1}(u_{3}) & … \\ −zλ_{2}l_{2}(u_{1}) & 1 − zλ_{2}l_{2}(u_{2}) & −zλ_{2}l_{2}(u_{3}) & … \\ −zλ_{3}l_{3}(u_{1}) & −zλ_{3}l_{3}(u_{2}) & 1 − zλ_{3}l_{3}(u_{3}) & … \\ ⋮ & ⋮ & ⋮ & ... \end{matrix} |

so we can express

C_{N}(t) = ∑_{i_{1}<...<i_{N}} λ_{i_{1}} … λ_{i_{N}} Det [(l_{i_{α}}(u_{i_{β}}))_{1≤α,β≤N}]

(cf. [Gr, p. 17] for details). Now since the l_{i_{α}} and u_{i_{β}} are both normalised, we have |l_{i_{α}}(u_{i_{β}})| ≤ 1 for all 1 ≤ α, β ≤ N. Thus Det (l_{i_{α}}(u_{i_{β}}))_{1≤α,β≤N} ≤ N^{N/2}.

It remains to estimate the term ∑_{i_{1}<...<i_{N}} λ_{i_{1}} … λ_{i_{N}}, which we note is just the N^{th} term in the series expansion of the Euler product ∏_{q=1}^{∞}(1 + λ_{q}z). Following [Fried, p. 507], the identity

∑_{i_{1}<...<i_{N}} θ_{0}^{i_{1}+...+i_{N}} = \frac{θ_{0}^{N(N+1)/2}}{(1 − θ_{0}) … (1 − θ_{0}^{N})},

together with our estimate (3.6) on the decay rate of the λ_{q} gives

∑_{i_{1}<...<i_{N}} λ_{i_{1}} … λ_{i_{N}} ≤ \frac{K^{N}θ_{0}^{N(N+1)/2}}{(1 − θ_{0}) … (1 − θ_{0}^{N})},

so that

|C_{N}(t)| ≤ \frac{N^{N/2}K^{N}θ_{0}^{N(N+1)/2}}{(1 − θ_{0}) … (1 − θ_{0}^{N})} ≤ AN^{N/2}K^{N}θ_{0}^{N(N+1)/2},  (3.7)

where A = ∏_{j=1}^{∞}(1−θ_{0}^{j})^{−1} < ∞. Setting θ = θ_{0}^{1/2}, we have C_{N}(t) = O(θ^{N^{2}}), which concludes the lemma.

Remark. The rate θ is independent of t and g. The constant K does depend on t and g, but note that setting t = 0 removes the dependence on g (see (3.5)). Thus C_{N}(0) is O(θ^{N^{2}}), where the implicit constant is independent of the function g.

The next lemma extends our estimates on C_{N}(t) to the coefficients NC_{N}(0) and C′_{N}(0) of the power series expansions for the partial derivatives of F.

Lemma 9. We can bound |NC_{N}(0)| = O(θ^{N^{2}}) and |C′_{N}(0)| = O(θ^{N^{2}}).

Proof. Clearly the bound on NC_{N}(0) follows immediately from that on C_{N}(0). Moreover, by the above remark, the implicit constant is independent of the function g.

To estimate |C′_{N}(0)| we first combine (3.5) and (3.7) to obtain

|C_{N}(t)| ≤ AN^{N/2}Q^{N}θ^{N(N+1)}||e^{tg}||_{∞}^{N}.

Then by Cauchy’s theorem we integrate around the unit circle, say, to obtain

|C′_{N}(0)| = |\frac{1}{2πi} ∫_{|t|=1} \frac{C_{N}(t)}{t^{2}}dt| ≤ \frac{A}{2π} N^{N/2}Q^{N}θ^{N(N+1)}e^{N||g||_{∞}},  (3.8)

and the result follows. Note however that C′_{N}(0) does depend on g.

Now we can finally complete the proof of Theorems 1 and 2.

Setting g(x) = e^{2πikx}, we use Lemmas 8 and 9 to deduce that there exists 0 < θ < 1 such that

∫ g dμ = \frac{D_{2}F (1, 0)}{D_{1}F (1, 0)} = \frac{∑_{N=1}^{M} C′_{N}(0)}{∑_{N=1}^{M} NC_{N}(0)} + O(θ^{M^{2}}) = ∫ g dμ_{M} + O(θ^{M^{2}}).

The proof of Theorem 2 follows in the same way, though here we make the choice g(x) = log |T′(x)|.

4. Examples

4.1 A family of unimodal maps. Consider the family of maps T_{l} : [0, 1] → [0, 1] defined by

T_{l}(x) = 1 − |2x − 1|^{l}, for l > 1.

For l = 2 this is the familiar Ulam-von Neumann map T_{2}x = 4x(1 − x), which is well-known to be conjugate to the strictly expanding tent map S : I → I defined by

S(x) = \{ \begin{matrix}2x & if 0 ≤ x ≤ \frac{1}{2} \\ 1 − 2x & if \frac{1}{2} ≤ x ≤ 1. \end{matrix}

This unimodal family has been well-studied, and it is known that each T_{l} has an absolutely continuous invariant measure μ_{T_{l}} (see for example [No-vS]). Recently Murray [M, p. 98] (see also [K-M-Y]) has shown that each map in this family is conjugate to an expanding Markov map, via the conjugating homeomorphism

φ_{l}(x) = \frac{1 + x^{1/l} − (1 − x)^{1/l}}{2} .

This is a homeomorphism of I which fixes the three points 0, 1/2 and 1, is C^{ω} on (0, 1), and is non-differentiable at 0 and 1. We then define maps S_{l} : I → I by S_{l} := φ_{l} ∘ T_{l} ∘ φ_{l}^{−1}. Murray shows these maps are expanding, so there exist absolutely continuous invariant measures μ_{S_{l}}. The a.c.i.m.’s μ_{T_{l}} and μ_{S_{l}} are related by φ_{l}^{∗}μ_{S_{l}} = μ_{T_{l}}. In particular, the corresponding invariant densities ρ_{T_{l}}, ρ_{S_{l}} are simply related by ρ_{T_{l}}(x) = ρ_{S_{l}}(φ_{l}x)φ′_{l}(x).

The maps S_{l} : [0, 1] → [0, 1] are clearly analytic on the half-open intervals (0, 1/2] and [1/2, 1). (Of course, the individual analytic extension for each of these intervals need not, indeed will not, co-incide when they intersect).

The algebraic nature of the conjugacy means a little care is needed in proving analyticity of S_{l} at the points x = 0, 1. Let us write φ_{l}(x) = x^{1/l}/2 + A(x), where A is analytic at 0, and A(0) = 0. The implicit function theorem implies that φ_{l}^{−1} is analytic at zero, and can be written φ_{l}^{−1}(x) = 2^{l}x^{l}(1 + B(x)), where B is analytic at zero with B(0) = 0. Near zero we can also write T_{l}(x) = 2lx(1 + C(x)), where C is analytic at zero with C(0) = 0. Substituting into S_{l} = φ_{l} ∘ T_{l} ∘ φ_{l}^{−1} we see that

S_{l}(x) = φ_{l} (2l [2^{l}x^{l} (1 + B (x))] (1 + C (2^{l}x^{l} (1 + B(x))))) .

Letting

D(x) = 2l [2^{l}x^{l} (1 + B (x))] (1 + C (2^{l}x^{l} (1 + B(x))))

we have

S_{l}(x) = (2l)^{1/l} x (1 + B (x))^{1/l} (1 + C (2^{l}x^{l} (1 + B(x))))^{1/l} + A (D(x)) , (4.1)

which is indeed analytic at x = 0. A similar argument applies at the point x = 1.

The conjugacy φ_{l} effects an isomorphism of the two measure-theoretic dynamical systems (T_{l}, μ_{T_{l}}) and (S_{l}, μ_{S_{l}}). In particular the metric entropies h(μ_{T_{l}}) and h(μ_{S_{l}}) are the same, so we will work with the expanding map S_{l} (to which our theory applies). In fact the conjugacy φ_{l} is differentiable except at the two endpoints of I. Therefore, with the exception of the fixed point at zero, the Lyapunov exponents of all periodic orbits of S_{l} agree with those of T_{l} (which are easier to compute). The Lyapunov exponent at the fixed point 0 of S_{l} is simply log(2l)^{1/l} (see (4.1)).

Murray [M, p. 101] estimates the metric entropy of the a.c.i.m. for T_{4} using Ulam’s method. He obtains h(μ_{T_{4}}) = 0·684494±0·004475 using an approximation involving estimates on 20,480 subintervals.

Our calculations corroborate this, as shown in Table 1, which illustrates the rate at which our approximations converge.

\begin{matrix}M & ∫ log |T′_{4}|dμ_{M} \\ 10 & 0.68449357504752271773574313505618766157945930 \\ 11 & 0.68449357504752260251509177842177235719158843 \\ 12 & 0.68449357504752260256820776598083056164855874 \\ 13 & 0.68449357504752260256819472702814929076462601 \\ 14 & 0.68449357504752260256819472868164339401607398 \\ 15 & 0.68449357504752260256819472868154757763010379 \\ 16 & 0.68449357504752260256819472868154757953058421 \end{matrix}

Table 1. Successive approximations to the entropy of the a.c.i.m. for T_{4}(x) = 1 − |2x − 1|^{4}

In Table 2 we list approximations to the entropy of the a.c.i.m. for T_{l}, l = 3, 4, …, 10. All these approximations were derived using the first sixteen terms

\begin{matrix}l & ∫ log |T′_{l}|dμ_{16} \\ 3 & 0.6908569334901144991937353967411391919921 \\ 4 & 0.68449357504752260256819472868154757 \\ 5 & 0.67569106132695477097960253643 \\ 6 & 0.6656587731730144691648898 \\ 7 & 0.655103028496451495992 \\ 8 & 0.6444244568815129504 \\ 9 & 0.63384949603792114 \\ 10 & 0.623504776625946 \end{matrix}

Table 2. Approximate entropy of the a.c.i.m. for T_{l}(x) = 1 − |2x − 1|^{l}

of the (partial derivatives of the) Fredholm determinant. The quality of the approximation is better for lower values of l, reflecting the fact that the conjugate expanding map S_{l} has a larger analytic extension.

4.2 Perturbations of the doubling map. In section 2 we considered the family of maps T_{ε} : [0, 1] → [0, 1] defined by

T_{ε}(x) = 2x + ε sin 2πx (mod 1), for − \frac{1}{2π} < ε < \frac{1}{2π} .

Murray [M] considers a similar family of maps

S_{Ω}(x) = 2x + Ω + \frac{sin 2πx}{4π} (mod 1).

Using Ulam’s method, with a partition of 10,000 subintervals, he estimates [M, p. 81] the entropies of the a.c.i.m.’s in this family to within an accuracy of 0 · 0411. The map T_{1/4π} = S_{0} is common to both families, so let us compute the entropy of the a.c.i.m. for this map. We will also compare our method of approximation (using the measures μ_{M}) to that obtained by using the measures m_{M} defined in (0.1).

We remarked in the introduction that the convergence arising from the measures m_{M} is merely exponential. The approximate entropies h_{M} = ∫ log |T′| dm_{M} are given by

h_{M} = \frac{∑_{x∈Fix(M)} log |T′(x)|/|(T^{M})′(x)|}{∑_{x∈Fix(M)} 1/|(T^{M})′(x)|}.  (4.2)

The reason for the comparatively slow convergence is that these expressions h_{M} do not fully exploit all periodic points up to period M, but rather are defined only in terms of points of period exactly M. Thus each length-M cylinder set (in the corresponding subshift of finite type) is represented by the unique period-M point lying within it. However any other consistent choice of representative would result in the same order of convergence (though the corresponding measures would no longer be invariant). Indeed by fixing some point y and summing over its preimages under T^{M}, we can define approximations

H_{M} = \frac{∑_{T^{M} x=y} log |T′(x)|/|(T^{M})′(x)|}{∑_{T^{M} x=y} 1/|(T^{M})′(x)|},  (4.3)

which will converge to the true entropy at the same rate as the h_{M}. But

H_{M} = \frac{L_{T}^{M}(log |T′|)(y)}{L_{T}^{M}(1)(y)} ⟶ \frac{ρ(y) ∫ log |T′| dμ}{ρ(y) ∫ 1 dμ} = h(μ),  (4.4)

where the convergence in (4.4) is at exponential rate O(γ^{M}), with γ the second largest eigenvalue of L_{T} (see [Ru2]).

In Table 3 we compare, for the map T_{1/4π} = S_{0}, the approximate entropies given by the two sequences of measures μ_{M} (super-exponential convergence) and m_{M} (exponential convergence).

\begin{matrix}M & ∫ log |T′_{1/4π}| dμ_{M} & ∫ log |T′_{1/4π}| dm_{M} \\ 6 & 0.68377196111065572152584683874828 & 0.684006 \\ 7 & 0.68377196024189881811155811511344 & 0.683903 \\ 8 & 0.68377196024214511529529028557809 & 0.683836 \\ 9 & 0.68377196024214513962679407279747 & 0.683805 \\ 10 & 0.68377196024214513961916059090822 & 0.683788 \\ 11 & 0.68377196024214513961916071092967 & 0.683780 \\ 12 & 0.68377196024214513961916071100328 & 0.683776 \end{matrix}

Table 3. Successive approximations to the entropy of the a.c.i.m. for T_{1/4π}(x) = 2x + \frac{1}{4π} sin(2πx)

5. Some final comments

Our method also applies to real-analytic expanding Markov maps in higher dimensions. Interesting examples are the various continued fraction algorithms, such as the Jacobi-Perron algorithm, designed to give simultaneous diophantine approximations. In dimension d the approximation rate for the metric entropy and the Fourier coefficients is O(θ^{M^{1+1/d}}).

If we relax the analyticity requirement, and demand only that T be C^{2}, say, then the same method applies, and all the rates of approximation will be exponential.

References

[Bowen] R. Bowen, Equilibrium states and the ergodic theory of Anosov diffeomorphisms, Lecture Notes in Mathematics 470, Springer, Berlin, 1975.

[C-E] P. Collet and J.-P. Eckmann, Iterated maps on the interval as dynamical systems,

Birkhauser, Boston, 1980.

[Fried] D. Fried, The zeta functions of Ruelle and Selberg I, Ann. Sci. ENS 19 (1986), 491–517.

[Froy1] G. Froyland, Finite approximation of Sinai-Bowen-Ruelle measures for Anosov systems in two dimensions, Random Comput. Dynam. 3 (1995), 251–264.

[Froy2] G. Froyland, Using Ulam’s method to calculate entropy and other dynamical invariants, Nonlinearity 12 (1999), 79–101.

[HuntB] B. R. Hunt, Estimating invariant measures and Lyapunov exponents, Ergodic Theory Dynam. Systems 16 (1996), 735–749.

[HuntF] F. Hunt, A Monte Carlo approach to the approximation of invariant measures, Random Comput. Dynam. 2 (1994), 111-133.

[Gr] A. Grothendieck, Produits tensoriels topologiques et espaces nucléaires, Mem. Amer. Math. Soc. 16 (1955).

[Kato] T. Kato, Perturbation theory for linear operators, Springer, Berlin, 1966. [K-H] A. Katok and B. Hasselblatt, Introduction to the modern theory of dynamical systems,

C.U.P., Cambridge, 1995.

[K-M-Y] M. Keane, R. Murray and L.-S. Young, Computing invariant measures for expanding

circle maps, Nonlinearity 11 (1998), 27–46.

[L-Y] A. Lasota and J. A. Yorke, On the existence of invariant measures for piecewise mono-

tonic transformations, Trans. Amer. Math. Soc. 186 (1973), 481–488.

[M] R. Murray, Discrete approximation of invariant densities, Ph.D. thesis (Cambridge), 1997.

[No-vS] T. Nowicki and S. van Strien, Invariant measures exist under a summability condition

for unimodal maps, Invent. Math. 105 (1991), 123–136.

[Pa] W. Parry, On the β-expansions of real numbers, Acta. Math. Acad. Sci. Hungar. 11 (1960), 401–416.

[Pa-Pol] W. Parry and M. Pollicott, Zeta functions and the periodic orbit structure of hyperbolic

dynamics, Astérisque vol 187-188, Soc. Math. France, Paris, 1990.

[Pe] J. B. Pesin, Lyapunov characteristic exponents and smooth ergodic theory, Russ. Math. Surveys 32 (1977), 55–114.

[Renyi] A. Rényi, Representations of real numbers and their ergodic properties, Acta Math. Hungar. 8 (1957), 477–493.

[Ro] V. A. Rohlin, Exact endomorphism of a Lebesgue space, Amer. Math. Soc. Transl. 39 (1964), 1–36.

[Ru1] D. Ruelle, Zeta functions for expanding maps and Anosov flows, Invent. Math. 34 (1976), 231–242.

[Ru2] D. Ruelle, Thermodynamic Formalism, Wiley, New York, 1978.

[Ulam] S. Ulam, Problems in Modern Mathematics, Interscience, New York, 1960.

[Wal1] P. Walters, Ruelle’s operator theorem and g-measures, Trans. Amer. Math. Soc. 214 (1975), 375–387.

[Wal2] P. Walters, An introduction to ergodic theory, Springer-Verlag, New York, 1982.

M. Pollicott, Department of Mathematics, University of Manchester, Oxford Road, Manchester M13 9PL, UK

   E-mail address: mp@ma.man.ac.uk

O. Jenkinson, UPR 9016 CNRS, Institut de Mathématiques de Luminy, 163 avenue de Luminy, case 907, 13288 Marseille, cedex 9, France.

   E-mail address: omj@iml.univ-mrs.fr