arXiv:1701.08723v3 [math.DS] 2 Jun 2017

AN ASYMPTOTIC EQUIPARTITION PROPERTY FOR
MEASURES ON MODEL SPACES
TIM AUSTIN
A BSTRACT. Let G be a sofic group, and let Σ “ pσn qně1 be a sofic
approximation to it. For a probability-preserving G-system, a variant
of the sofic entropy relative to Σ has recently been defined in terms of
sequences of measures on its model spaces that ‘converge’ to the system
in a certain sense. Here we prove that, in order to study this notion,
one may restrict attention to those sequences that have the asymptotic
equipartition property. This may be seen as a relative of the Shannon–
McMillan theorem in the sofic setting.
We also give some first applications of this result, including a new formula for the sofic entropy of a pGˆ Hq-system obtained by co-induction
from a G-system, where H is any other infinite sofic group.

1. I NTRODUCTION
Let G be a countable sofic group, and let
`
˘
Σ “ σn : G ÝÑ SympVn q ně1

be a sofic approximation to it.
A G-system is a triple pX, µ, T q in which pX, µq is a standard probability space and T “ pT g qgPG is a µ-preserving measurable action of G on
X. Using the sofic approximation Σ, one can construct an isomorphisminvariant of pX, µ, T q called its sofic entropy. It is denoted by hΣ pµ, T q.
It was introduced by Lewis Bowen in [5] under some extra conditions and
then made fully general in [12, 13]. It solves various classic problems in
ergodic theory, such as distinguishing Bernoulli shifts of unequal base entropy over many natural discrete groups [5, 11]. Bowen’s recent survey [3]
gives a thorough introduction to this invariant and explains many directions
of current research.
A G-process is a G-system of the form pX G , µ, Sq, where X is another
standard measurable space, S is the left coordinate-shift action of G on X G ,
and µ P ProbpX G q is shift-invariant. A metric G-process is a quadruple
2010 Mathematics Subject Classification. 37A35 (primary), 37A50, 28D15, 28D20,
94A17.
Key words and phrases. Sofic entropy, measures on model spaces, asymptotic equipartition property, co-induced dynamical systems.
1

2

TIM AUSTIN

pX G , µ, S, dq consisting of a G-process and a compact metric d on X which
generates the σ-algebra of X as its Borel sets.
Following [1], we use a definition of sofic entropy which initially applies only to metric G-processes, and is then extended to other systems by
isomorphism-invariance. For a metric G-process pX G , µ, S, dq, sofic entropy is defined in terms the spaces X Vn , and is abbreviated to hΣ pµq. For
each element of X Vn , one defines an empirical distribution on X G by a kind
of ‘pulling back’ under σn . An element of X Vn is a ‘good model’ for µ if
its empirical distribution is close to µ in the weak˚ topology of ProbpX G q,
where X G has the product topology resulting from d. Loosely, the sofic
entropy hΣ pµq is defined as the exponential growth rate of the sizes of the
sets of these good models. Here ‘size’ refers to cardinality if X is finite and
to small-radius covering numbers if pX , dq is compact but not finite.
Starting with [6] and [1], more recent works have considered variants of
the sofic entropy which are defined in terms of sequences of measures on
the spaces X Vn that ‘converge’ in a certain sense to the process µ. In particular, [1] discussed several notions of convergence for these measures, and
showed how they play a role in determining when sofic entropy is additive
under forming Cartesian products of systems.
The key variant of sofic entropy which appears in [1] is ‘model measure
sofic entropy’, denoted here by hm
Σ pµq. This relies on a notion of convergence for a sequence µn P ProbpX Vn q to a process µ which in that paper is
called ‘doubly quenched’ convergence.
In the present paper we consider this notion again. However, here we use
a different terminology for this mode of convergence. We call it ‘local and
lde
doubly empirical’ or ‘LDE’ convergence, and denote it by µn ÝÑ µ. We
propose this name change because the name ‘quenched convergence’ could
create a serious conflict with older uses of the word ‘quenched’ in statistical
physics: this is explained further in Section 2. Unfortunately this possible
conflict did not occur to the author at the time of writing [1]. Because of
this name change, our notation hm
Σ also differs from [1]: in that paper this
dq
quantity is denoted by ‘hΣ ’.
The present paper also uses the notion of local weak˚ convergence, delw˚
noted by µn ÝÑ µ, which is weaker than LDE convergence. This also
played a role in [1], but it has an older history in probability theory.
The definitions of these modes of convergence and of model-measure
sofic entropy are recalled in Section 2.
1.1. The asymptotic equipartition property. Our first main result is that
one obtains the same value for hm
Σ pµq if one uses only sequences µn which
satisfy the asymptotic equipartition property (‘AEP’) of information theory.

AN AEP FOR MEASURES ON MODEL SPACES

3

The Shannon–McMillan theorem provides a similar conclusion for the finite
marginals of a Z-process, but this similarity is rather superficial: in our
setting there is generally no canonical choice of a convergent sequence of
measures, and we allow ourselves to change the sequence in order to secure
the AEP.
To explain the result precisely, suppose first that pX G , µ, Sq is a G-process
with X finite. Let µn be any sequence of probability measures on the spaces
X Vn , and let h P r0, 8q. The sequence pµn qn has the asymptotic equipartition property, or AEP, with rate h if
(
µn x P X Vn : e´h|Vn |´ε|Vn| ă µn txu ă e´h|Vn |`ε|Vn | ÝÑ 1
as n ÝÑ 8 @ε ą 0.
Some processes cannot be represented using a finite state space, so those
require a generalization of this notion. The simplest approach uses finite
measurable partitions of the state space X , via the following auxiliary definition. For any measurable space X, probability measure µ on X, finite
measurable partition P of X, and ε ą 0, we define
!
´ď ¯
)
covε pµ; Pq “ min |P1 | : P1 Ď P and µ
P1 ą 1 ´ ε .
This reduces to the ε-covering number covε pµq in case X is finite and P is
the partition into singletons.
Now consider a shift-invariant measure µ on X G for an arbitrary standard
measurable space X , fix a finite measurable partition P of X , and let µn be
a sequence of members of ProbpX Vn q as before. For each n, let P Vn be the
partition of X Vn into products of cells of P. The sequence pµn qn has the
AEP rel P with rate h if
´ď
(¯
µn
C P P Vn : e´h|Vn|´ε|Vn | ă µn pCq ă e´h|Vn |`ε|Vn | ÝÑ 1
as n ÝÑ 8 @ε ą 0.

This reduces to the previous definition if X is finite and P is the partition
into singletons.
Theorem A. Let pX G , µ, S, dq be a metric G-process, let P be a finite
measurable partition of X , and let νn P ProbpX Vn q be a sequence such
that
lde
i) νn ÝÑ µ, and
ii) we have
1
log covε pνn ; P Vn q ÝÑ h
|Vn |
as n ÝÑ 8 and then ε Ó 0.

4

TIM AUSTIN

Then there is another sequence µn P ProbpX Vn q which has the same two
properties and also has the AEP rel P with rate h.
This is proved in Section 4, following two introductory sections. In fact
we prove a slightly stronger and more precise variant of this theorem: see
Theorem 4.1 below.

1.2. A new formula for model-measure sofic entropy. Let pX G , µ, S, dq
be a metric G-process. Using Theorem A, we can prove a new formula for
hm
Σ pµq in terms of finite partitions of X and associated Shannon entropies.
To do this for a general space pX , dq, we must now allow a whole family
P of Borel partitions of X , and insist that this family is compatible with d
in the following two ways:
Pi) For every δ ą 0 there exists P P P all of whose cells have diameter
less than δ.
Pii) Let µe be the marginal of µ at the identity element e of G. If P P P,
then every cell C P P is a continuity set for the marginal µe : that is,
µe pBCq “ µtx P X G : xe P BCu “ 0.
For example, if pX , dq is totally disconnected (such as an abstract Cantor
set), then one may take P to consist of all partitions into subsets that are
both closed and open. For a general compact metric space pX , dq, a routine
argument shows the existence of families satisfying both properties (Pi) and
(Pii). Indeed, for any δ ą 0 and x P X , all but countably many radii
r P p0, δq must satisfy
µe pBBpx, rqq “ µe ty P X : dpx, yq “ ru “ 0.
Therefore, by compactness, X has a finite cover consisting of open balls
with radii less than δ and which are all continuity sets for µe . Now consider the Borel partition generated by all these balls and their complements.
The cells of this partition are still continuity sets for µe and they all have
diameter less than 2δ.
Having chosen a family P as above, we actually obtain two new formulae
for hm
Σ pµq.

AN AEP FOR MEASURES ON MODEL SPACES

5

Theorem B. Let pX G , µ, S, dq be a metric G-process and let P be any
family having properties (Pi) and (Pii) above. Then
!
1
m
hΣ pµq “ sup lim sup
log covε pµi ; P Vni q : ε ą 0, P P P,
iÝÑ8 |Vni |
)
lde
ni Ò 8 and µi ÝÑ µ over pσni qiě1
!
1
Hµi pP Vni q : P P P,
“ sup lim sup
iÝÑ8 |Vni |
)
lde
ni Ò 8 and µi ÝÑ µ over pσni qiě1 .
This is proved in Section 5. In the proof, we first show that the two righthand formulae agree if we fix a single partition P. This is the argument that
needs Theorem A. Then we complete the proof by showing that the first
of these formulae always agrees with hm
Σ pµq. This second step is a fairly
routine exercise in regularity properties of Borel measures. We include both
formulae in the statement of Theorem B for completeness, but the second
is the main new innovation.
One could formulate and prove the obvious analog of this result for the
lower model-measure sofic entropy hm
Σ pµq (see [1, Section 6]), but we leave
the details aside. In a different direction, a little more work should yield
a generalization of Theorem B to the case of a Polish space pX , dq using
similar arguments to [9], but we do not pursue this here either.
The second formula in Theorem B is useful because it makes available
some of the good computational properties of Shannon entropy, such as
additivity under products. The proof of Theorem C below is an example.
Previously, a valuable special case of Theorem B was already given in [6,
Theorem 4.1], where it was used to calculate the sofic entropies of certain
actions of algebraic origin. Another use of Shannon entropies to provide
lower bounds for covering numbers in this context appeared recently in [2].
In case X is a finite set, the best choice of P in either of the formulae in
Theorem B is the partition into singletons. From this choice we obtain the
following corollary.
Corollary B1 . If X is finite, then
!
1
m
hΣ pµq “ sup lim sup
log covε pµi q : ε ą 0,
iÝÑ8 |Vni |
lde

ni Ò 8 and µi ÝÑ µ over pσni qiě1

)

)
!
1
lde
Hpµi q : ni Ò 8 and µi ÝÑ µ over pσni qiě1 .
“ sup lim sup
iÝÑ8 |Vni |

6

TIM AUSTIN


The first of these formulae already appears in [1, Proposition 8.1].
Section 5 also includes examples showing that hypotheses (Pi) and (Pii)
on P are not superfluous in Theorem B.
Remark. Although a given partition P of X generates a factor of the Gsystem pX G , µ, Sq, the expressions on the right in Theorem B are not simply the sofic entropy of that factor. Indeed, those expressions still depend
on the entire metric process pX G , µ, S, dq because of the requirement that
lde
the measures satisfy µi ÝÑ µ. In the setting of non-amenable groups, it
is known that both sofic entropy and model-measure sofic entropy can increase under factor maps, so the sofic entropy of a factor should not appear
inside a supremum such as either right-hand side in Theorem B.
⊳
1.3. The entropy of certain co-induced systems. Now let H be another
sofic group with a sofic approximation T “ pτn qně1 , where
τn : H ÝÑ SympWn q.
Then the product group G ˆ H has a product sofic approximation Σ ˆ T
consisting of the Cartesian product maps
σn ˆ τn : G ˆ H ÝÑ SympVn ˆ Wn q : pg, hq ÞÑ σng ˆ τnh .
If pX, µ, T q is a G-system, then the space pX H , µˆH q supports natural
commuting actions of G and H: G acts diagonally through copies of T ,
and H acts by coordinate left-translation. Together these define a measurepreserving action of G ˆ H. It is called the co-induction of T to G ˆ H
and denoted by CIndGˆH
T . If pX, µ, T q is a G-process pX G , µ, Sq, then
G
its co-induction is the pG ˆ Hq-process pX GˆH , µˆH , Sq, where we use the
same letter S to denote the left coordinate-shift action on either of these
spaces. Co-induction can be defined more generally given any containment
of two discrete groups, but we do not discuss that generality here.
In Section 6 we apply Theorem B to deduce a general formula for the
behaviour of model-measure sofic entropy under co-induction of systems.
Theorem C. Let pX G , µ, S, dq be a metric G process and let P be a family
of finite Borel partitions of X having properties (Pi) and (Pii). Assume that
the sofic approximation T satisfies |Wn | ÝÑ 8 as n ÝÑ 8. Then
!
1
ˆH
hm
pµ
q
“
sup
lim sup
Hµi pP Vni q : P P P, ni Ò 8 and
ΣˆT
iÝÑ8 |Vni |
)
lw˚
µi ÝÑ µ over pσni qiě1 .

AN AEP FOR MEASURES ON MODEL SPACES

7

This theorem gives a formula for the model-measure sofic entropy of
the co-induced system pX GˆH , µˆH , S, dq in terms of convergent measures
for the original system pX G , µ, S, dq. It looks very similar to the second
formula in Theorem B, but it has the important difference that LDE convergence has been weakened to local weak˚ convergence on the right-hand
side.
The condition that |Wn | ÝÑ 8 is clearly not superfluous. Without it, we
could simply let H be the trivial group and let each Wn be a singleton, in
ˆH
which case hm
q “ hm
ΣˆT pµ
Σ pµq. This is certainly not always equal to the
right-hand side above, because of the difference between local weak˚ and
lw˚
LDE convergence. Indeed, there may exist a sequence µi ÝÑ µ even in
cases where hm
Σ pµq “ ´8: see Example 4.6 below.
Theorem C is clarified by some important special cases. To discuss these,
let us write r
hΣ pµq for the right-hand formula in Theorem C.
First, if H is infinite, then any sofic approximation must have |Wn | ÝÑ
8. In that case, [1, Theorem E] has already shown another entropy equality
ˆH
for the co-induced system: that hΣˆT pµˆH q “ hm
q. So in this case
ΣˆT pµ
we obtain the following.
Corollary C1 . If H is infinite, then
ˆH
hΣˆT pµˆH q “ hm
q“r
hΣ pµq.
ΣˆT pµ



Secondly, one can let H be the trivial group, and so identify G ˆ H with
G. Then the maps τn in the sofic approximation T are also trivial, but the
finite sets Wn are arbitrary. Since we assume that |Wn | ÝÑ 8, this really
r to G
amounts to replacing Σ with a new, enlarged sofic approximation Σ
defined by
σ
rng :“ σng ˆ IdWn P SympVn ˆ Wn q.
Equivalently, σ
rn is a direct sum of several copies of σn , their number tending to 8 with n. In this case, Theorem C tells us that this enlargement
of the sofic approximation enables a new formula for model-measure sofic
entropy.
Corollary C2 . In the situation described above, we have
r
hm
r pµq “ hΣ pµq.
Σ



An immediate consequence of either Corollary C1 or Corollary C2 is that
the quantity r
hΣ pµq is invariant under measure-theoretic isomorphisms of
processes. Its definition may therefore be extended unambiguously to any

8

TIM AUSTIN

G-system pX, µ, T q by picking an arbitrary isomorphism from that system
to a metric G-process and picking a suitable family P. We write r
hΣ pµ, T q
for the quantity obtained this way.
However, this invariant of G-systems is often not new. If the metric Gprocess pX G , µ, S, dq is weakly mixing, then local weak˚ convergence implies LDE convergence [1, Corollary 5.7 and Lemma 5.15], and then r
hΣ pµq
does coincide with the second formula in Theorem B. This gives our third
special case of Theorem C.
Corollary C3 . If pX, µ, T q is a weakly mixing G-system then
ˆH
hm
, CIndGˆH
T q “ hm
ΣˆT pµ
Σ pµ, T q.
G

This is equal to hΣˆT pµˆH , CIndGˆH
T q in case H is infinite.
G



I do not know whether Corollary C3 has a natural variant in case µ is
ergodic but not weakly mixing.
In light of Corollary C1 , the quantity r
hΣ pµ, T q may be viewed as a kind
of ‘stabilized’ sofic entropy. We can obtain r
hΣ pµ, T q by choosing any other
infinite sofic group — Z, for example — and then using the sofic entropy
of the co-induced system
` Z ˆZ
˘
X , µ , CIndGˆZ
T
.
G

Alternatively, by Corollary C2 , we may retain the group G but enlarge the
r In particular, either approach gives a new formula
sofic approximation to Σ.
m
for hΣ pµ, T q in case pX, µ, T q is weakly mixing, by Corollary C3 . Much
like the relation to power-stabilized sofic entropy established in [1, Section
8], this gives a meaning to model-measure sofic entropy which does not refer to any sequences of measures on model spaces. It is restricted to weakly
mixing G-systems, but avoids another problem with the results of [1, Section 8]: those are presently known only for systems with finite generating
partitions.
1.4. Next steps. A few remaining open problems are scattered below. However, another problem which deserves mention here is to generalize any of
the results above to the relative setting: that is, so that they apply to a notion
of relative sofic entropy for a factor map pX, µ, T q ÝÑ pY, ν, Sq between
two G-systems.
2. BACKGROUND

ON

LDE

CONVERGENCE AND MODEL - MEASURE
SOFIC ENTROPY

Aside from our new terminology for LDE convergence, our formalism
and notation essentially agree with those of [1]. This section simply recalls
the main definitions. More discussion can be found in that paper.

AN AEP FOR MEASURES ON MODEL SPACES

9

Let G be a countable sofic group and let Σ “ pσn qn be a sofic approximation to it, where σn : G ÝÑ SympVn q. Let pX G , µ, S, dq be a metric
G-process. We endow each of the spaces X Vn with the compact product
topology, and more specifically with the Hamming average dpVn q of the
metric d, defined by
1 ÿ
dpxv , yv q.
dpVn q px, yq :“
|Vn | vPV
n

Given x P X

Vn

and v P Vn , the pullback name of x at v is the element
Πσv n pxq “ pxσng pvq qgPG P X G .

The empirical distribution of x is
1 ÿ
δΠσv n pxq P ProbpX G q.
Pxσn “
|Vn | vPV
v

If U is a weak˚ neighbourhood of µ in ProbpX G q, then the U-good models for µ over σn are the elements of the set
(
ΩpU, σn q “ x P X Vn : Pxσn P U .
The sofic entropy of µ rel Σ is the quantity
`
˘
1
hΣ pµq :“ sup inf lim sup
log covδ ΩpU, σn q, dpVn q ,
δą0 U nÝÑ8 |Vn |

where the infimum is over all weak˚ neighbourhoods U of µ, and
`
˘
covδ ΩpU, σn q, dpVn q

denotes the least number of δ-balls in the metric dpVn q needed to cover
ΩpU, σn q. See [1] for a comparison of this with older definitions of sofic
entropy.
Now suppose in addition that µn P ProbpX Vn q for each n.
Definition 2.1. The sequence pµn qn locally weak˚ converges to µ over Σ if
ˇ
(ˇ
ˇ v P Vn : pΠσn q˚ µn P U ˇ “ p1 ´ op1qq|Vn |
v

lw˚

for every weak˚ neighbourhood U of µ. This is denoted by µn ÝÑ µ.

The next definition was the first main innovation of [1], but here it has its
new name.
Definition 2.2. The sequence pµn qn locally and empirically converges (or
‘LE-converges’) to µ over Σ if
lw˚

i) µn ÝÑ µ, and also
ii) µn pΩpU, σn qq ÝÑ 1 for every weak˚ neighbourhood U of µ.

10

TIM AUSTIN
le

We denote this by µn ÝÑ µ.
The sequence pµn qn locally and doubly empirically converges (or ‘LDE
le
converges’) to µ over Σ if µn ˆ µn ÝÑ µ ˆ µ over Σ. We denote this by
lde
µn ÝÑ µ.
Section 5 of [1] is devoted to these notions of convergence. In that paper,
LE-convergence is called ‘quenched convergence’, and LDE convergence
is called ‘doubly-quenched convergence’. This usage was motivated by the
use of the word ‘quenched’ in statistical physics: it indicates a property
that holds with high probability as some thermodynamic or other limit is
approached, rather than just on average. However, I now realize that my
previous terminology could create a serious conflict. In case G is a free
group, it is common and natural to produce sofic approximations to it randomly (see, for instance, [4]). In this case, if we are to use ‘quenched’ as
in statistical physics, it should be applied to the random choice of sofic approximation, not to the choice of model given a fixed sofic approximation.
This is the why I have switched to the new names above for these modes of
convergence for the measures µn .
Finally, the model-measure sofic entropy of pX G , µ, S, dq rel Σ is the
quantity
!
1
hm
pµq
“
sup
sup lim sup
log covε,δ pµi , dpVni q q :
Σ
|V
|
δ,εą0 iÝÑ8
ni
)
lde
ni Ò 8 and µi ÝÑ µ over pσni qiě1 ,
where covε,δ pµi , dpVni q q denotes the least number of δ-balls in the metric
dpVni q needed to cover more than 1 ´ ε of the measure µi .
Model-measure sofic entropy is defined and studied in [1, Section 6]
(but beware that it also has a different notation: it is denoted by ‘hdq
Σ pµq’
in [1]). According to [1, Theorem 6.4], it is an invariant of the process under measure-theoretic isomorphism, so in particular it does not depend on
the choice of d, and can be defined unambiguously for any G-system.
3. A

STABILITY RESULT FOR

LDE

CONVERGENCE

The new sequence of measures µn given by Theorem A is obtained by
conditioning: this is made explicit in the refined statement of Theorem 4.1
below. It is crucial for the proof that conditioning on sets which are not too
small cannot disrupt LDE convergence. We state and prove this as a separate
theorem since it has independent interest and may find other applications
elsewhere.
Fix a metric G-process pX G , µ, S, dq.

AN AEP FOR MEASURES ON MODEL SPACES

11

Theorem 3.1 (Stability of LDE convergence under conditioning). Suppose
lde
that µn ÝÑ µ, and let An Ď X Vn be subsets which all satisfy µn pAn q ě a
lde
for some a ą 0. Then also µn p ¨ | An q ÝÑ µ.
The proof of this rests on the following elementary lemma.
Lemma 3.2. Let X be a compact metrizable space and let ProbpXq be
the space of all Borel probability measures on it, endowed with the weak˚
topology. Let θ be a probability distribution on ProbpXq, and let µ be its
barycentre, meaning that
ż
(1)
µpAq “ νpAq θpdνq @ Borel A Ď X.
Suppose in addition that
(2)

µˆµ“

ż

ν ˆ ν θpdνq.

Then θ is the point mass at µ.
Proof. If A Ď X is Borel, then (2) implies that
ż
2
µpAq “ νpAq2 θpdνq.
In combination with (1), this is possible only if νpAq “ µpAq for θ-a.e.
ν. Letting A run through a countable sequence which generates the Borel
σ-algebra of X, it follows that θptµuq “ 1.

Proof of Theorem 3.1. Let νn :“ µn p ¨ | An q for each n.
le

Part 1: support on good models. Our assumptions include that µn ÝÑ µ,
so for any weak˚ neighbourhood U of µ in ProbpX G q we have
µn pΩpU, σn q X An q
µn pAn q
µn pAn q ´ µn pX Vn zΩpU, σn qq
ě
µn pAn q
Vn
µn pX zΩpU, σn qq
ě1´
a
ÝÑ 1 as n ÝÑ 8.

νn pΩpU, σn qq “

So νn is asymptotically supported on good models for µ.
lde
Using the full assumption that µn ÝÑ µ, we apply the same reasoning
to the measures µn ˆ µn and sets An ˆ An . It follows that νn ˆ νn is
asymptotically supported on good models for µ ˆ µ.

12

TIM AUSTIN

Part 2: local weak˚ convergence.
each v P Vn , let

lw˚

Next we show that νn ÝÑ µ. For

νn,v :“ pΠσv n q˚ νn P ProbpX G q.
Let θn be the uniform distribution on this collection of elements of ProbpX G q:
that is,
1 ÿ
δνn,v P ProbpProbpX G qq.
θn :“
|Vn | vPV
n

The desired local weak˚ convergence asserts that
θn pUq “

|tv P Vn : νn,v P Uu|
ÝÑ 1
|Vn |

as n ÝÑ 8

for any weak˚ neighbourhood U of µ. This is equivalent to the convergence
weak˚

θn ÝÑ δµ ,
where this refers to convergence in the weak˚ topology of ProbpProbpX G qq.
That topology is compact, by Alaoglu’s theorem, so it suffices to prove
that δµ is the only subsequential weak˚ limit of the sequence pθn qn . Let
θ “ limiÝÑ8 θni be any such subsequential limit. Since the formation of
product measures is continuous for the weak˚ topology, it follows that
ż
ż
1 ÿ
νni ,v ˆ νni ,v .
ν ˆ ν θpdνq “ lim ν ˆ ν θni pdνq “ lim
iÝÑ8
iÝÑ8 |Vni |
vPV
ni

The average inside this last limit may be re-arranged as
1 ÿ
1 ÿ σni
νni ,v ˆ νni ,v “
pΠv q˚ pνni ˆ νni q
|Vni | vPV
|Vni | vPV
ni
ni
ĳ
σn
1
“
Ppx,x
1 q νni pdxq νni pdx q.
However, Part 1 has shown that this last integral converges to µ ˆ µ. Therefore θ must satisfy
ż
ν ˆ ν θpdνq “ µ ˆ µ,
and so θ “ δµ , by Lemma 3.2.
lw˚
This shows that νn ÝÑ µ, and for local weak˚ convergence this implies
lw˚
immediately that νn ˆ νn ÝÑ µ ˆ µ.


AN AEP FOR MEASURES ON MODEL SPACES

4. O BTAINING

SEQUENCES WITH THE

13

AEP

This section proves Theorem A and some related results. In fact we formulate and prove a version which gives a slightly stronger conclusion and
which describes how the new measures are obtained.
For the statement, let pX G , µ, Sq, P, and pνn qn be as in the statement of
Theorem A, satisfying the properties (i) and (ii) listed there. We say that
a sequence µn P ProbpX Vn q has the strong AEP rel P with rate h if for
every ε ą 0 we have
´ď
(¯
Vn
´h|Vn |´ε|Vn |
´h|Vn |`ε|Vn |
µn
“1
CPP : e
ă µn pCq ă e
for all sufficiently large n.
Theorem 4.1 (Stronger version of Theorem A). There are measurable sets
An Ď X Vn with νn pAn q ě e´opnq such that the sequence of conditional
measures
µn :“ νn p ¨ | An q
has properties (i) and (ii) and also has the strong AEP rel P with rate h.
We present the proof following a couple of preparatory lemmas. The first
justifies the use of diagonal arguments for LDE-convergent sequences of
measures.
Lemma 4.2 (Passing to a diagonal subsequence). Suppose µk,n P ProbpX Vn q
lde
for every k, n P N, and that µk,n ÝÑ µ as n ÝÑ 8 for every fixed k. Then
lde
also µkn ,n ÝÑ µ whenever the integer sequence k1 ď k2 ď . . . tends to 8
sufficiently slowly.
Proof. Let U1 Ě U2 Ě . . . be a basis of weak˚ neighbourhoods around
µ ˆ µ. By assumption, for each k there exists Nk such that
ˇ
(ˇ
ˇ v P Vn : pΠσv n q˚ pµk,n ˆ µk,n q P Uk ˇ ě p1 ´ 2´k q|Vn |
@n ě Nk
and

`
˘
pµk,n ˆ µk,nq ΩpUk , σn q ě 1 ´ 2´k

@n ě Nk .

Provided pkn qn tends to 8 so slowly that n ě Nkn for all sufficiently large
n, these imply the LDE convergence of µkn ,n .

Secondly, we need to know that having the AEP with a given rate actually controls the Shannon entropy and covering numbers of a sequence of
measures. The following simple facts can be traced to arguments in [16].
The proof is standard, but we include it for completeness.

14

TIM AUSTIN

Lemma 4.3. If pµn qn satisfies the AEP rel P with rate h, then also
1
log covε pµn ; P Vn q ÝÑ h
|Vn |

as n ÝÑ 8

for all ε P p0, 1q, and
1
Hµ pP Vn q ÝÑ h as n ÝÑ 8.
|Vn | n
Proof. For each n, let εn ą 0, let
Qn :“ tC P P Vn : e´h|Vn |´εn |Vn | ă µn pCq ă e´h|Vn |`εn |Vn | u,
Ť
and let An :“ Qn Ď X Vn . By the AEP, if we choose εn tending to zero
sufficiently slowly, then these sets satisfy µn pAn q ÝÑ 1. We now assume
this.
Suppose that 0 ă ε ă 1. Then µn pAn q ą 1 ´ ε for all sufficiently large
n. Since the measures µn pCq for C P Qn must sum to at most 1, we have
|Qn | ď eh|Vn |`εn |Vn | “ eh|Vn |`op|Vn |q ,
and so covε pµn ; P Vn q ďŤeh|Vn |`op|Vn |q . On the other hand, consider any
P1 Ď P Vn satisfying µn p P1 q ą 1 ´ ε, and choose some ε1 P pε, 1q. If n
is sufficiently large, then we have
´ď
¯
µn
pQn X P1 q ą 1 ´ ε1 ą 0.

Since any cell in Qn X P1 has measure at most e´h|Vn |`εn |Vn | , this implies
that
|P1 | ě |Qn X P1 | ą p1 ´ ε1 qeh|Vn |´εn |Vn | “ eh|Vn |´op|Vn |q
once n is sufficiently large. So in fact covε pµn ; P Vn q “ eh|Vn |`op|Vn |q .
Lastly, we may estimate Hµn pP Vn q by first conditioning on the coarser
partition into An and X Vn zAn :
Hµn pP Vn q “ Hµn pAn , X Vn zAn q ` µn pAn qHµn p ¨ |An q pP Vn q
` p1 ´ µn pAn qqHµn p ¨ | X Vn zAn q pP Vn q.

All three right-hand terms are non-negative. The first is at most log 2, and
the last is at most
p1 ´ µn pAn qq ¨ log |P Vn | “ p1 ´ µn pAn qq ¨ log |P| ¨ |Vn | “ op|Vn |q,
since µn pAn q ÝÑ 1. Finally, since the values µn pCq for C P Qn are all
equal to e´h|Vn |`op|Vn |q , a simple calculation gives
Hµn p ¨ |An q pP Vn q “ h|Vn | ` op|Vn |q.
Therefore the same asymptotic holds for Hµn pP Vn q.



AN AEP FOR MEASURES ON MODEL SPACES

15

Proof of Theorem 4.1. Let
Qa,n :“ tC P P Vn : νn pCq ą e´a|Vn | u.
for each n P N and any a ě 0. Clearly |Qa,n | ă ea|Vn | , and so for any k P N
we must have
´ď
¯
lim sup νn
Qh´1{k,n ă 1,
nÝÑ8

for otherwise the subfamily Qh´1{k,n Ď P Vn would violate assumption (ii)
in Theorem A. On the other hand, in order to compute covε pνn ; P Vn q, it
is most efficient to cover νn using cells of P Vn in order of decreasing νn measure. So condition (ii) in Theorem A also implies that
´ď
¯
νn
Qh`1{k,n ÝÑ 1 as n ÝÑ 8
for any k P N.
For each k P N, let

Ak,n :“

ď

Qh`1{k,n

Iď

Qh´1{k,n

and let µk,n :“ νn p ¨ |Ak,nq. The estimates above show that νn pAk,n q is
bounded away from 0 as n ÝÑ 8 for each k, so Theorem 3.1 shows that
lde
we still have µk,n ÝÑ µ for each k. Given this, Lemma 4.2 provides a
lde
sequence k1 ď k2 ď . . . growing slowly to 8 so that µkn ,n ÝÑ µ. Provided
that sequence grows slowly enough, we may also assume that νn pAkn ,n q ě
e´opnq .
Letting An :“ Akn ,n and µn :“ µkn ,n , these are of the form asserted in
Theorem 4.1. Let us show that they have all the desired properties. We
have already deduced conclusion (i). For the rest, observe that any C P
Qh`1{kn ,n zQh´1{kn ,n satisfies
1
1
e´ph`1{kn q|Vn | ă µn pCq ď
e´ph´1{kn q|Vn | ,
νn pAkn ,n q
νn pAkn ,n q
and that µn pCq “ 0 for any other C P P Vn . Since νn pAkn ,n q ě e´opnq and
kn ÝÑ 0, this shows the strong AEP rel P with rate h. By Lemma 4.3, this
also implies conclusion (ii) of the theorem.

Theorem 4.1 tells us how the new measures µn are obtained from νn in
Theorem A. This procedure has further consequences of its own. As an
illustration, let us show that we can actually obtain the AEP relative to a
whole family of partitions simultaneously. This requires one more preparatory lemma.
Lemma 4.4. Let P be a finite measurable partition of X and let h P r0, 8q.
Let νn P ProbpX Vn q for each n, and let Bn Ď An Ď X Vn be such that

16

TIM AUSTIN

i) νn pAn q ą 0 for all n and the conditional measures
νn p ¨ | An q
have the strong AEP rel P with rate h, and
ii) νn pBn q ě e´κn νn pAn q for some sequence κn “ opnq as n ÝÑ 8.
Then the conditional measures νn p ¨ | Bn q have the AEP (not necessarily
strong) rel P with rate h.
Proof. Let ε ą 0, and let

(
Qn :“ C P P Vn : e´h|Vn |´ε|Vn| ă νn pC | An q ă e´h|Vn |`ε|Vn | .

Assumption (i) gives that

νn

´ď

ˇ ¯
ˇ
Qn ˇ An “ 1

for all sufficiently large n, so the same holds with Bn in place of An (this
is the point at which we need to assume the strong AEP). Also, since the
values νpC | An q for C P Qn must sum to at most 1, we have |Qn | ă
eh|Vn |`ε|Vn| for every n.
If C P Qn , then
νn pC X Bn q
νn pC | Bn q “
ď eκn νn pC | An q ă e´h|Vn |`ε|Vn|`κn .
νn pBn q
This is less than e´h|Vn |`2ε|Vn| for all sufficiently large n. Now let
(
Q1n :“ C P Qn : νn pC | Bn q ě e´h|Vn |´2ε|Vn | .

Then the definition of Q1n gives
ˇ ¯
´ď
ˇ
νn
pQn zQ1n q ˇ Bn ď |Qn |e´h|Vn |´2ε|Vn | ă e´ε|Vn | ÝÑ 0

as n ÝÑ 8. Since ε was arbitrary, the family Q1n witnesses the AEP of
νn p ¨ | Bn q rel P with rate h.

Corollary 4.5. Let pX G , µ, S, dq be a metric G-process and let pPk qk be a
sequence of finite measurable partitions of X . Let hk P r0, 8q for each k,
and let νn P ProbpX Vn q be a sequence such that
lde

i) νn ÝÑ µ, and
ii) for every k we have
1
log covε pνn ; PkVn q ÝÑ hk
|Vn |
as n ÝÑ 8 and then ε Ó 0.
Then there is another sequence µn P ProbpX Vn q which has the same two
properties and which also has the AEP rel Pk with rate hk for every k.

AN AEP FOR MEASURES ON MODEL SPACES

17

Proof. First, Theorem 4.1 gives a sequence of subsets A1,n Ď X Vn with
νn pA1,n q ě e´opnq and such that the conditional measures
µ1,n :“ νn p ¨ | A1,nq
satisfy properties (i) and (ii) and also the strong AEP rel P1 with rate h1 .
Now we may apply Theorem 4.1 again, this time to the sequence µ1,n ,
to find subsets A2,n Ď X Vn with µ1,n pA2,n q ě e´opnq and such that the
conditional measures
µ2,n :“ µ1,n p ¨ | A2,n q
satisfy properties (i) and (ii) and also the strong AEP rel P2 with rate h2 . By
intersecting with A1,n if necessary, we may clearly also choose A2,n Ď A1,n .
Continuing in this way, a recursion on k produces a doubly-indexed array
pAk,n qk,n such that the following hold:
a) For each n, we have
X Vn Ě A1,n Ě A2,n Ě A3,n Ě ¨ ¨ ¨ ,
all these sets have positive measure according to νn , and
νn pAk`1,n q ě e´opnq νn pAk,n q

as n ÝÑ 8

for each k.
b) For each k, the sequence of measures νn p ¨ | Ak,nq satisfies properties
(i) and (ii) and also the strong AEP rel Pk with rate hk .
Using these properties and Lemma 4.2, it follows that if we choose k1 ď
k2 ď ¨ ¨ ¨ sufficiently slowly, then the sequence of sets Bn :“ Akn ,n satisfies
(3)

νn pBn q ě e´opnq Ak,n

as n ÝÑ 8

for each fixed k, and also the sequence
µn :“ νn p ¨ | Bn q
LDE converges to µ. Now property (b) above, the bound (3), and Lemma 4.4
imply that pµn qně1 still satisfies the AEP rel Pk with rate hk for every k. Finally, property (ii) still holds for µn by Lemma 4.3.

Before leaving this section, let us consider how the results above change
if the assumption of LDE convergence is weakened to local weak˚ convergence.
This makes no difference for G-systems that are weakly mixing, for then
the two modes of convergence coincide [1, Corollary 5.7 and Lemma 5.15].
However, if pX G , µ, Sq is not even ergodic, then Theorem A has no analog
for local weak˚ convergence.

18

TIM AUSTIN

Example 4.6. Let G be a sofic group with a finite generating set S “ S ´1 ,
and let Σ “ pσn qně1 be a sofic approximation to G with the property that
the graphs
Gn “ tpv, σns pvqq : v P Vn , s P Su Y tpσns pvq, vq : v P Vn , s P Su
are an expander sequence. (This holds, for instance, for a ‘typical’ sofic
approximation to a non-amenable free group, or for a sequence of finite
quotients of a group with Kazhdan’s property (T): see [1, Example 5.9].)
This assumption has the consequence that, for any sequence of elements
xn P X Vn , any weak˚ limit of the empirical measures Pxσnn in ProbS pX G q
must be ergodic.
Let X be a finite set with at least two elements, and let p, q P ProbpX q
be two probability distributions with Hppq ą Hpqq. Now let
1
1
µ :“ pˆG ` q ˆG .
2
2
This is a mixture of two ergodic measures. Similarly, let
1
1
µn :“ pˆVn ` q ˆVn .
2
2
lw˚

It is easy to show that µn ÝÑ µ. However, this is not empirical convergence. Indeed, once n is large, an element x P X Vn drawn at random
with distribution µn has empirical distribution Pxσn which is probably either close to pˆG or close to q ˆG , each with probability about 1{2, but in
neither case is x a good model for the whole of the measure µ.
A simple calculation gives that
(4)

log covε pµn q “ Hppq ¨ |Vn | ` op|Vn |q

for any ε P p0, 1{2q. This is because, in order to cover at least 1 ´ ε ą 1{2
of the measure µn , one must in particular cover a positive fraction of the
good models for pˆVn . All such good models have probability
`
˘
exp ´ Hppq ¨ |Vn | ´ op|Vn |q
according to µn , so such a covering requires
`
˘
exp Hppq ¨ |Vn | ` op|Vn |q

points of X Vn .
However, now suppose that νn P ProbpX Vn q is a sequence which satisfies
lw˚
the AEP and has νn ÝÑ µ. By a simple adaptation of the proof of [1,
Corollary 5.7], it follows that, once n is large, νn is mostly supported on
good models for either pˆG or q ˆG , each with probability about 1{2, just as
we saw above for the measure µn . But there are only at most
`
˘
exp Hpqq ¨ |Vn | ` op|Vn |q

AN AEP FOR MEASURES ON MODEL SPACES

19

good models for q ˆG , so if pνn qn satisfies the AEP, then it must do so with
rate at most Hpqq. Since this is strictly less than Hppq, we cannot match the
exponential growth rate of the covering numbers in (4).
⊳
This leaves us with the following.
lde

le

Question 4.7. Does Theorem A still hold if ‘ÝÑ’ is weakened to ‘ÝÑ’? ⊳
5. A LTERNATIVE

FORMULAE FOR MODEL - MEASURE SOFIC ENTROPY

5.1. Proof of the new formulae. This section proves Theorem B. First
we prove a preliminary result that relates the two right-hand formulae in
that theorem to each other. This is the point where we need Theorem A to
provide LDE-convergent sequences of measures which have the AEP.
Proposition 5.1. Let pX G , µ, S, dq be a metric G-process and let P be a
finite measurable partition of X . Then
!
1
sup lim sup
log covε pµi ; P Vni q : ε ą 0,
|V
|
iÝÑ8
ni
)
lde
ni Ò 8 and µi ÝÑ µ over pσni qiě1
)
!
1
lde
Vni
Hµi pP q : ni Ò 8 and µi ÝÑ µ over pσni qiě1 .
“ sup lim sup
iÝÑ8 |Vni |
Proof. Let h1 and h2 be the left- and right-hand sides here, respectively.
Step 1. Fix any sequences
pσni qiě1 and pµi qiě1 . For any i ě 1 and Q Ď
Ť
P Vni , we may let A “ Q and then condition on the partition tA, X Vni zAu
to obtain
Hµi pP Vni q “ Hµi pA, X Vni zAq ` µi pAqHµi p ¨ |Aq pP Vni q
` p1 ´ µi pAqqHµi p ¨ |X Vni zAq pP Vni q
ď log 2 ` µi pAq log |Q| ` p1 ´ µi pAqq|Vni | log |P|.
Optimizing over collections Q for which µi pAq ą 1 ´ ε, this gives
Hµi pP Vni q ď log 2 ` log covε pµi ; P Vn q ` ε|Vni | log |P|.
Since ε may be made arbitrarily small, this gives h1 ě h2 .
Step 2. Fix any sequences pσni qiě1 and pµi qiě1 and also ε ą 0. By passing to a further subsequence if necessary, we may assume that the quantities
1
log covε pµi ; P Vni q
|Vni |
actually converge to some h ě 0 as i ÝÑ 8, where this h is the limit
supremum for the original sequences.

20

TIM AUSTIN

Now Theorem A provides a new sequence of measures νi which still
lde
satisfy νi ÝÑ µ over pσni qiě1 and which also satisfy the AEP rel P with
rate h. Then Lemma 4.3 gives
1
Hν pP Vni q ÝÑ h,
|Vni | i
so this shows that h1 ď h2 .



Proof of Theorem B. Proposition 5.1 gives the equality of the two righthand expressions. Calling their common value h, we need only show that it
equals hm
Σ pµq.
Step 1. Let ε, δ ą 0, and let pσni qiě1 and pµi qiě1 be two sequences as in
the definition of hm
Σ pµq. By property (Pi), there exists P P P all of whose
cells have diameter less than δ. Now any cell of P Vni also has diameter less
than δ according to dpVni q , and therefore
covε,δ pµi , dpVni q q ď covε pµi ; P Vni q.
This shows that hm
Σ pµq ď h.
Step 2. Fix the sequences pσni qiě1 and pµi qiě1 and also ε ą 0 and P P
P. By property (Pii), we have
´ď
¯
µe
intpCq “ 1,
CPP

where intpCq denotes the interior of C. Therefore there exist r ą 0 and
further open subsets GC Ď C for each C P P such that
dpx, x1 q ą r

whenever x P GC , x1 P GC 1 and C ‰ C 1 ,

and such that the open set
G :“

ď

GC

CPP

has µe pGq ą 1 ´ ε2 {2. By the portmanteau theorem, it follows that the set
(
U :“ ν P ProbpX G q : νtx : xe P Gu ą 1 ´ ε2 {2
is a weak˚ neighbourhood of µ.
Next, observe that
ż
ÿ
µi tx P X Vni : xv P Gu
|tv P Vni : xv P Gu| µi pdxq “
vPVni

“

ÿ

σn

ppΠv i q˚ µi qptx P X G : xe P Guq

vPVni
σn

ą p1 ´ ε2 {2q|tv P Vni : pΠv i q˚ µi P Uu|.

AN AEP FOR MEASURES ON MODEL SPACES
lde

21

lw˚

Since µi ÝÑ µ, we have in particular that µi ÝÑ µ. Therefore the above
integral is greater than p1 ´ ε2q|Vni | for all sufficiently large i. By Markov’s
inequality, it follows that the sets
(
Zi :“ x P X Vni : |tv P Vni : xv P Gu| ą p1 ´ εq|Vni |
satisfy µi pZi q ą 1 ´ ε for all sufficiently large i. Let
Qi :“ tD X Zi : D P P Vni u.
Now suppose that δ ă εr and that x, y P Zi satisfy dpVni q px, yq ă δ. The
fact that x, y P Zi gives that
|tv P Vni : xv , yv P Gu| ą p1 ´ 2εq|Vni |.
Combining this with the fact that dpVni q px, yq ă δ and Markov’s inequality,
we obtain
ˇ
(ˇ
ˇ v P Vn : xv , yv lie in GC for the same C P P ˇ
i
ą p1 ´ 2ε ´ δ{rq|Vni | ą p1 ´ 3εq|Vni |.

It follows that if x P F Ď Zi , and if F has diameter at most δ according to
dpVni q , then F can have nonempty intersection with at most
2Hp3ε,1´3εq|Vni | ¨ |P|3ε|Vni |
cells of Qi , since this is an upper bound on the number of elements of Qi
that agree with the cells containing xv for at least p1 ´ 3εq|Vni | vertices
v. (This is a standard bound on the cardinality of Hamming balls: see, for
instance, [7, Section 5.4].)
Finally, once i is large enough that we have µi pZi q ą 1 ´ ε, the last
estimate implies that
log covε,δ{2 pµi , dpVni q q
ě log min k : DF1 , . . . , Fk Ď Zi all having diameter ă δ
and such that µpF1 Y ¨ ¨ ¨ Y Fk q ą 1 ´ 2ε
ě log cov2ε pµi ; P Vni q ´ Hp3ε, 1 ´ 3εq|Vni | ´ 3ε|Vni | log |P|.
Since we may choose ε arbitrarily small, this implies that hm
Σ pµq ě h.

(


Next let us see that Theorem B can fail if one does not assume both
properties (Pi) and (Pii). Without property (Pi), it is easy to see from the
proof that one could have h ă hm
Σ pµq, where again h denotes the right-hand
side in the theorem. More interestingly, without property (Pii), the reverse
failure can occur.

22

TIM AUSTIN

Example 5.2. Suppose that is X is an uncountable compact metric space
which has no isolated points, and let P consist of all finite Borel partitions
of X . Suppose also that hm
Σ pµq ě 0: this simply asserts that there are some
lde
subsequence ni Ò 8 and measures µi P ProbpX Vni q which satisfy µi ÝÑ µ
over pσni qiě1 . Let us show that in this case the right-hand formulae of
Theorem B are both equal to `8, irrespective of the exact value of hm
Σ pµq.
By the Baire category theorem, any co-countable subset of X is dense.
Using this fact, for any k P N, a simple recursion produces a Borel partition
P “ pC1 , . . . , Ck´1, Rq
in which C1 , . . . , Ck´1 are all countable dense subsets of X , and the remainder set R is also dense.
It follows that every cell of P Vni is dense in X Vni for every i. Therefore
we can make a sequence of smaller and smaller perturbations νi of µi in
lde
the weak˚ topologies so that, on the one hand, we still have νi ÝÑ µ; but,
on the other, each νi gives equal weight to every cell of P Vni , and hence
Hνi pP Vni q “ log k ¨ |Vni |. It follows that the second right-hand quantity in
Theorem B is greater than log k for every k P N, and so must be infinite.
Since Proposition 5.1 still applies, this is also true of the first right-hand
quantity.
⊳
5.2. Related results for local weak˚ convergence. Natural variants of
model-measure sofic entropy can be obtained by replacing LDE convergence in the definition with other modes of convergence. The paper [1]
already includes a notion which uses only LE convergence; there it was
called ‘quenched model-measure sofic entropy’, and here we denote it by
hle
Σ . Most of these variants probably have little value for ergodic theory, but
some may have an important auxiliary role in computing values of other,
existing entropy notions. For instance, the quantity r
hΣ pµq of Subsection 1.3
plays such a role through Theorem C.
Here we consider replacing LDE convergence with local weak˚ convergence. We have already seen that Theorem A has no analog in that setting. Some parts of the previous subsection do still work, but others fail. Of
course, problems appear only in case µ is not weakly mixing, since all these
modes of convergence coincide for weakly mixing processes.
In the proof of Proposition 5.1, Step 1 makes no reference to the specific
mode of convergence, so it still applies without change. On the other hand,
Step 2 relies on Theorem A, which is not available for local weak˚ convergence in case µ is not weakly mixing, as seen in Example 4.6. So in the
case of local weak˚ convergence we obtain only an inequality.

AN AEP FOR MEASURES ON MODEL SPACES

23

Proposition 5.3. Let pX G , µ, S, dq be a metric G-process and let P be a
finite measurable partition of X . Then
!
1
log covε pµi ; P Vni q : ε ą 0,
sup lim sup
iÝÑ8 |Vni |
)
lw˚
ni Ò 8 and µi ÝÑ µ over pσni qiě1
!
)
1
lw˚
ě sup lim sup
Hµi pP Vni q : ni Ò 8 and µi ÝÑ µ over pσni qiě1 .
iÝÑ8 |Vni |

Similarly, the argument above for Theorem B uses only the convergence
lw˚
lde
µi ÝÑ µ, not the full strength of the assumption that µi ÝÑ µ. So, together
with the above proposition, that proof can be re-applied for local weak˚
convergence. This gives a counterpart of Theorem B which again provides
only an inequality.
Theorem 5.4. Let pX G , µ, S, dq be a metric G-process and let P be any
family of finite Borel partitions of X having properties (Pi) and (Pii), as in
Theorem B. Then
!
1
sup sup lim sup
log covε,δ pµi , dpVni q q :
|V
|
ε,δą0 iÝÑ8
ni
)
lw˚
ni Ò 8 and µi ÝÑ µ over pσni qiě1
!
1
“ sup lim sup
log covε pµi ; P Vni q : ε ą 0, P P P,
iÝÑ8 |Vni |
)
lw˚
ni Ò 8 and µi ÝÑ µ over pσni qiě1
!
1
Hµi pP Vni q : P P P,
ě sup lim sup
|V
|
iÝÑ8
ni
)
lw˚
ni Ò 8 and µi ÝÑ µ over pσni qiě1 .

The last quantity in Theorem 5.4 is r
hΣ pµq again. The inequality can be
strict: Example 4.6 demonstrates this, too. By slightly adapting the proof
of [1, Theorem 6.4], it is not hard to show that the first two formulae above
give another quantity which is invariant under measure-theoretic isomorphism. We omit the details since I do not currently know of any applications
for this quantity. Moreover, I believe it can be related to existing invariants
as follows. For µi P ProbpX Vni q, we write
σn

P˚ i µi P ProbpProbpX G qq

24

TIM AUSTIN
σn

for the pushforward of µi under the empirical-distribution map x ÞÑ Px i .
σn
According to [1, Lemma 5.6], any weak˚ limit θ of the sequence pP˚ i µi qiě1
must be supported on ProbG pX G q and have barycentre equal to µ. Let us
σn

weak˚

pass to a subsequence so that in fact P˚ i µi ÝÑ θ. Then it should follow
that the first two formulae of Theorem 5.4 are equal to the essential supremum of hle
Σ pνq when ν is drawn from the distribution θ. In particular, if µ is
ergodic, then these two formulae simply compute hle
Σ pµq, as can be deduced
directly from [1, Corollary 5.7].
These facts would give a relative of some older work [20, 21] in information theory which addresses the following situation. Let pX Z , µ, Sq be
a stationary source with a finite alphabet, and let µn be the marginal of µ
on X n for each n. If µ is not ergodic, then the AEP can fail (put another
way: the Shannon-McMillan theorem does not hold in its usual form), and
the KS-entropy need not be equal to the exponential growth-rate of the covering numbers of the measures µn . In this case the KS-entropy is the average of the KS-entropies of the ergodic components, whereas the growth of
the covering numbers is governed by the full distribution of those entropy
values over the ergodic decomposition of µ. In particular, the exponential
growth rate of covε approaches the essential supremum of the KS-entropies
of the ergodic components as ε Ó 0. See also [22] for a generalization to
processes with arbitrary state spaces and a resulting non-ergodic generalization of Krieger’s generator theorem; and [17] for some more analysis of the
distribution of KS-entropies over ergodic components, with an application
to a source-coding theorem.
5.3. Alternative approaches for general metric processes. In this paper,
families of partitions which satisfy properties (Pi) and (Pii) are simply a
convenient way to bring Shannon entropy and the AEP to bear when studying processes with non-finite state spaces. Questions about the appropriate
‘entropy notion’ when faced with such general state spaces have a long
history in information theory. The traditional setting is shift-invariant measures on X Z for some standard measurable space X . In that case the classical Shannon–McMillan theorem becomes available upon suitably quantizing X , although one must be careful about taking limits in the right order.
See [8], for example, which also approaches quantization by starting with a
choice of suitable sequences of partitions.
I expect relatives of Theorem B can be found which do not start with
families satisfying (Pi) and (Pii). But two issues arise immediately: choosing a suitable ‘metric’ notion of Shannon entropy; and making sense of the
AEP without reference to a particular partition.
To address the first issue, one could seek a reformulation of Theorem
B using an appropriate version of ‘epsilon Shannon entropy’ for a metric

AN AEP FOR MEASURES ON MODEL SPACES

25

probability space pX, d, µq, such as the quantity
!
Hε,δ pd, µq :“ inf Hµ ptU0 , U1 , . . . , Uk uq :

U0 , . . . , Uk are a Borel partition of X,

µpU0 q ă ε and diampUi , dq ă δ @i “ 1, 2, . . . , k

)

for ε, δ ą 0. This still involves partitions of the metric space, but they are
hidden inside a natural ‘Shannon-like’ quantity which depends only on the
metric space itself.
Such quantities have their own place in information theory. In particular, [15, 14, 10] develop the basic properties of a quantity very similar to
Hε,δ pd, µq, and involve some similar estimates to those in the present paper.
Vershik has also explored notions with this flavour in the setting of ergodic
theory: see, for instance, the end of Section 4 in [19] or [18, Section 6].
Some of those works do study behaviour under Cartesian products, but
I do not know of an established metric-space version of the AEP. In our
setting, one candidate is as follows. Given a compact metric space pX , dq,
a sequence µn P ProbpX Vn q could satisfy the ‘metric AEP with rate h’ if
for every η ą 0 and every ε P p0, 1{2q there exists δ0 ą 0 such that
ˇ 1
ˇ
!
)
ˇ
ˇ
Vn
lim sup ˇ
log min |F | : F Ď X , µn pBδ pF qq ą a ´ hˇ ă η
nÝÑ8 |Vn |
for all δ P p0, δ0 q and all a P pε, 1´εq, where Bδ pF q is the δ-neighbourhood
of F according to the metric dpVn q . Informally, for any radius parameter δ
less than δ0 , this asserts that it takes roughly expph|Vn |q balls of radius δ to
cover µn , whether one wishes to cover 5% or 95% of this measure.
In case X is finite, it is not hard to deduce the above property from the
usual AEP. However, I have not explored further how this metric definition
is related to the other problems of the present paper in the case of general
pX , dq. It is not clear to me that this approach gives any real advantage over
the more explicit use of partition-families that we have adopted above.
6. A PPLICATION

TO CO - INDUCED SYSTEMS

This section proves Theorem C. Fix a metric G-process pX G , µ, S, dq, so
that the co-induced system is the metric pG ˆ Hq-process pX GˆH , µˆH , S, dq.
Let P be a collection of Borel partitions of X having the two properties (Pi)
and (Pii) required by Theorem B.
In this section we use the following notation. If µ P ProbpX G q and
E Ď G, then µE denotes the marginal of µ on X E : that is, the image
measure of µ under the coordinate projection map X G ÝÑ X E . Similarly,

26

TIM AUSTIN

if µ P ProbpX V q for some finite set V and U Ď V , then µU denotes the
marginal of µ on X U .
As in Subsection 1.3, let us write r
hΣ pµq for the right-hand formula in
ˆH
Theorem C. We must show that it equals hm
q. The proof is based
ΣˆT pµ
on Theorem B, together with two simple lemmas.
lw˚

lde

n
Lemma 6.1. If µn ÝÑ µ over Σ, then µˆW
ÝÑ µˆH over Σ ˆ T.
n

lw˚

n
Proof. Part 1. We first show that µˆW
ÝÑ µˆH . Let E Ď G and F Ď H
n
both be finite. Once n is sufficiently large, most vertices w P Wn have the
property that the map h ÞÑ τnh pwq is injective on F . For such w, and any
v P Vn , a simple calculation gives
`
` σn ˆτn
˘
˘ˆF
n
pΠpv,wq q˚ pµˆW
q EˆF “ ppΠσv n q˚ µn qE
.
n

Once n is sufficiently large, most v P Vn have the property that ppΠσv n q˚ µn qE
is close to µE in the weak˚ topology, and hence the above measure is close
to µˆF
E .

Part 2. If H is infinite, then the shift action of G ˆ H on pX GˆH , µˆH q
is weakly mixing. In this case local weak˚ convergence implies LDE convergence [1, Corollary 5.7 and Lemma 5.15], so Part 1 completes the proof.
So now suppose that H is finite. In this case we must use the weaker
assumption that |Wn | ÝÑ 8 to complete the proof. There are many ways
to do this. Here we use a simple trick of enlarging H to the infinite group
r :“ H ˆ Z without effectively changing the sofic approximation to H.
H
Indeed, since H is finite and T is a sofic approximation to it, the sets
Yn :“ w P Wn : τng pτnh pwqq “ τngh pwq @g, h P H

(
and τnh pwq ‰ w @h P HzteH u

must satisfy |Yn | “ p1 ´ op1qq|Wn |. By the definition of these sets, the
restrictions h ÞÑ τnh |Yn define a genuine action of H on Yn for each n, and
these actions are all free.
Since H is finite but |Yn | ÝÑ 8, it follows that Yn must consist of a
disjoint union of free H-orbits, their number tending to 8 with n. We may
therefore choose a sequence of permutations θn : Yn ÝÑ Yn such that each
θn commutes with the H-action on Yn and permutes the H-orbits cyclically.
Extending θn arbitrarily to a permutation of Wn , it follows that the maps
r ÝÑ SympWn q : ph, kq ÞÑ τ h ˝ θk
τrn : H
n

n

r Let T
r :“ pr
constitute a sofic approximation to H.
τn qně1 .
r
Now Part 1 still applies with the new group H and sofic approximation
lw˚
r
n
r
r Since H
r is infinite, this implies
T, giving that µˆW
ÝÑ µˆH over Σ ˆ T.
n

AN AEP FOR MEASURES ON MODEL SPACES

27

r

lde

n
r as explained above. Finally, applying
that also µˆW
ÝÑ µˆH over Σ ˆ T,
n
r
r
the coordinate projection map X GˆH ÝÑ X GˆH to µˆH and to the empirical measures of models chosen randomly from µˆWn , this implies that
lde
µˆWn ÝÑ µˆH over Σ ˆ T.


Remark. Recalling the definitions of LDE convergence and of the weak˚
topology on measures, Part 2 of the previous proof is equivalent to proving
that
ż
ˇ
ˇż
)
!
ˇ
σn ˆτn
ˆWn
ˆWn
ˆH
ˆH ˇ
pµn ˆ µn q px, yq : ˇ f dPpx,yq ´ f dpµ ˆ µ qˇ ă ε ÝÑ 1

as n ÝÑ 8 for any f P CpX GˆH ˆ X GˆH q and any ε ą 0. Rather than using the trick above to reduce to the case of infinite H, it is also easy to prove
this directly, just a little messier. First, by the Stone–Weierstrass theorem,
it suffices to assume that f depends on only finitely
many coordinates in
ş
σn ˆτn
may be written
X GˆH ˆ X GˆH . Having done so, the integral f dPpx,yq
as an average over Vn ˆWn of quantities that depend only on local ‘patches’
n
, one deduces
of the models x and y. Using the product structure of µˆW
n
that most pairs of terms in this average are independent once n is large.
Then a simple appeal to Chebychev’s inequality gives the convergence in
probability asserted above, much as in standard proofs of the weak law of
large numbers.
⊳
lde

Lemma 6.2. If νn ÝÑ µˆH over Σ ˆ T, then there are subsets Zn Ď Wn
such that
|Zn | “ p1 ´ op1qq|Wn |
and such that, for any selection of a sequence of vertices wn P Zn , we have
lw˚

pνn qVn ˆtwn u ÝÑ µ

over Σ.

Proof. Let U1 Ě U2 Ě . . . be a neighbourhood base for the weak˚ topology
around µ P ProbpX G q. Let eH be the identity of H, and let us commit
the slight abuse of identifying measures on X GˆteH u and on X G . Since
lde
νn ÝÑ µˆH , we have
ˇ
(ˇ
ˇ pv, wq P Vn ˆ Wn : ppΠσn ˆτn q˚ νn qGˆte u P Uk ˇ
H
pv,wq
ˇ
(ˇ
σn
ˇ
“ pv, wq P Vn ˆ Wn : pΠv q˚ ppνn qVn ˆtwu q P Uk ˇ
ÿ ˇ
(ˇ
ˇ v P Vn : pΠσn q˚ ppνn qVn ˆtwu q P Uk ˇu
“
v
wPWn

“ p1 ´ op1qq|Vn ˆ Wn |

for every k ě 1. Therefore, by Markov’s inequality, if we choose k1 ď
k2 ď . . . growing to 8 sufficiently slowly and also εn Ó 0 sufficiently

28

TIM AUSTIN

slowly, then the sets
!
)
ˇ
(ˇ
Zn :“ w P Wn : ˇ v P Vn : pΠσv n q˚ ppνn qVn ˆtwu q P Ukn ˇ ą p1 ´ εn q|Vn |
satisfy |Zn | “ p1 ´ op1qq|Wn |.



Proof of Theorem C. Part 1: (ď). Let P P P, let ni Ò 8, and let µi P
ProbpX Vni q be a sequence which locally weak˚ converges to µ over pσni qiě1 .
n lde
ÝÑ µˆH over pσni ˆ τni qiě1 . On
By Lemma 6.1, it also holds that µˆW
i
the other hand, the additivity of Shannon entropy gives
(5)

1
1
Hµi pP Vni q “
H ˆWn pP Vni ˆWni q.
|Vni |
|Vni ˆ Wni | µi i

Taking the limit supremum as i ÝÑ 8, the second formula from Theorem
B turns this equality into
lim sup
iÝÑ8

1
ˆH
q.
Hµi pP Vni q ď hm
ΣˆT pµ
|Vni |

Now taking the supremum over all such choices of P P P, pni qiě1 , and
ˆH
pµi qiě1 , this becomes r
hΣ pµq ď hm
q.
ΣˆT pµ

Part 2: (ě). Let P P P, let ni Ò 8, and let νi P ProbpX Vni ˆWni q be a
sequence which LDE converges to µˆH over pσni ˆ τni qiě1 .
Let Zi Ď Wni be a sequence of subsets as provided by Lemma 6.2. For
any selection of a sequence of vertices wi P Zi , we have
lw˚

pνi qVni ˆtwi u ÝÑ µ over pσni qiě1 ,
and therefore
lim sup
iÝÑ8

1
hΣ pµq,
pP Vni q ď r
Hpν q
|Vni | i Vni ˆtwi u

by the definition of r
hΣ pµq. Since we can choose the elements wi P Zi to
maximize the Shannon entropies appearing on the left-hand side here, we
must actually have
(6)

lim sup
iÝÑ8

1
hΣ pµq.
max Hpνi qVn ˆtwu pP Vni q ď r
i
|Vni | wPZi

AN AEP FOR MEASURES ON MODEL SPACES

29

Now subadditivity and standard bounds for Shannon entropy give
Hνi pP Vni ˆWni q
ÿ
Hpνi qVn
ď

i

ˆtwu

pP Vni q

wPWni

ď

ÿ

Hpνi qVn

i

ˆtwu

pP Vni q ` |Wni zZi | ¨ |Vni | ¨ log |P|

wPZi

ď |Wni | ¨ max Hpνi qVn
wPZni

i ˆtwu

pP Vni q ` op|Vni ˆ Wni |q ¨ log |P|,

and so (6) gives
lim sup
iÝÑ8

1
hΣ pµq.
Hνi pP Vni ˆWni q ď r
|Vni ˆ Wni |

Taking the supremum over all choices of P P P, pni qiě1 , and pνi qiě1 ,
ˆH
one final appeal to the second formula in Theorem B gives hm
qď
ΣˆT pµ
r
hΣ pµq.


Through its appeals to the second formula in Theorem B, the proof above
rests crucially on the use of measures µi or νi that have the AEP. This is
what allows us to compute the sofic entropies using Hµi pP Vni q in place of
covε pµi ; P Vni q, and so gives us access to the additivity in (5). Covering
numbers of more general measures need not behave so well under highdimensional Cartesian products.
Acknowledgements. This research was supported partly by the Simons Collaboration on Algorithms and Geometry.
⊳
R EFERENCES
[1] T. Austin. Additivity properties of sofic entropy and measures on model spaces. Forum Math. Sigma, 4:e25, 79, 2016.
[2] T. Austin and P. Burton. Uniform mixing and completely positive sofic entropy. To
appear, J. Anal. Math.
[3] L. Bowen. Examples in the entropy theory of countable group actions. Preprint, available online at arXiv.org: 1704.06349.
[4] L. Bowen. The ergodic theory of free group actions: entropy and the f -invariant.
Groups Geom. Dyn., 4(3):419–432, 2010.
[5] L. Bowen. Measure conjugacy invariants for actions of countable sofic groups. J.
Amer. Math. Soc., 23(1):217–245, 2010.
[6] L. Bowen. Entropy for expansive algebraic actions of residually finite groups. Ergodic
Theory Dynam. Systems, 31(3):703–718, 2011.
[7] C. M. Goldie and R. G. E. Pinch. Communication theory, volume 20 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge, 1991.
[8] R. M. Gray and J. C. Kieffer. Mutual information rate, distortion, and quantization in
metric spaces. IEEE Trans. Inform. Theory, 26(4):412–422, 1980.

30

TIM AUSTIN

[9] B. Hayes. Polish models and sofic entropy. To appear, J. Inst. Math. Jussieu. Preprint
available online at arXi.org: 1411.1510.
[10] M. Katětov. On extended Shannon entropies and the epsilon entropy. Comment. Math.
Univ. Carolin., 27(3):519–534, 1986.
[11] D. Kerr and H. Li. Bernoulli actions and infinite entropy. Groups Geom. Dyn.,
5(3):663–672, 2011.
[12] D. Kerr and H. Li. Entropy and the variational principle for actions of sofic groups.
Invent. Math., 186(3):501–558, 2011.
[13] D. Kerr and H. Li. Soficity, amenability, and dynamical entropy. Amer. J. Math.,
135(3):721–761, 2013.
[14] E. C. Posner and E. R. Rodemich. Epsilon entropy of probability distributions. In
Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971), Vol. III: Probability theory,
pages 699–707. Univ. California Press, Berkeley, Calif., 1972.
[15] E. C. Posner, E. R. Rodemich, and H. Rumsey, Jr. Epsilon entropy of stochastic processes. Ann. Math. Statist., 38:1000–1020, 1967.
[16] C. E. Shannon. A mathematical theory of communication. Bell System Tech. J.,
27:379–423, 623–656, 1948.
[17] Š. Šujan. Epsilon-rates, epsilon-quantiles, and group coding theorems for finitely additive information sources. Kybernetika (Prague), 16(2):105–119, 1980.
[18] A. M. Vershik. Dynamic theory of growth in groups: entropy, boundaries, examples.
Uspekhi Mat. Nauk, 55(4(334)):59–128, 2000.
[19] A. M. Vershik. The Kantorovich metric: the initial history and little-known applications. Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI), 312(Teor.
Predst. Din. Sist. Komb. i Algoritm. Metody. 11):69–85, 311, 2004.
[20] K. Winkelbauer. On discrete information sources. In Trans. Third Prague Conf. Information Theory, Statist. Decision Functions, Random Processes (Liblice, 1962), pages
765–830. Publ. House Czech. Acad. Sci., Prague, 1964.
[21] K. Winkelbauer. On the asymptotic rate of non-ergodic information sources. Kybernetika (Prague), 6:127–148, 1970.
[22] K. Winkelbauer. On the existence of finite generators for invertible measurepreserving transformations. Comment. Math. Univ. Carolinae, 18(4):789–812, 1977.
C OURANT I NSTITUTE OF M ATHEMATICAL S CIENCES , N EW YORK U NIVERSITY, 251
M ERCER S T, N EW YORK , NY 10012
E-mail address: tim@cims.nyu.edu
URL: www.cims.nyu.edu/„tim

