# How to deduce the following inequality by use of the Shannon-McMillan-Breiman theorem?

My question is how to deduce the red inequality from the Shannon-McMillan-Breiman theorem?

First I state some lemmas which will be used in the QUESTION: the proceeding lemmas are in the setting where $X$ is a non-compact metric space and $T$ is a homeomorphism.

Lemma::For any invariant measure $\mu$ and compact set $C$ with $\mu(C) > 1-\sigma/2$, there is a compact set $K \subset C$ with $\mu(K) > 1 - \sigma$ and an $N$ so that for every $n\ge N$ and $x\in K$ $$\frac{1}{n}\sum_{i=0}^{n-1}X_{A}(T^{i}x)\ge1-\sigma$$

lemma: Let $P = \{P_1,.-. ,P_k\}$ be a Borel partition of $X$, let $C_i\subset P_i$ be compact subsets and let $C = \{C_1, . . . , C_k\}$. Suppose that $K \subset C = \cup C_i$ is compact and that there exists $\delta > 0$ so that for all $n > N$ and all$x\in K$ $$\frac{1}{n}\sum_{i=0}^{n-1}X_{A}(T^{i}x)\ge1-\sigma$$ then

$$\limsup_{n\to \infty}\log r(n, C, K) \ge \limsup_{n\to \infty}\log r(n, P, K) -\epsilon(\sigma)$$ where $\epsilon(\sigma)\to 0$ as $\epsilon\to 0$.

where $r(n, C, K)$ is defined as below

Let $C = \{C_1,... , C_k\}$ be any finite collection of disjoint subsets of $X$; C need not be a cover of $X$. We say that a finite set $E \subset K$ is $(n, C)-$ separated if for any pair of distinct points $x, y \in E$, there exists $1<i<r\neq s<k$ and i\in {0,1,...,n-1}such that $T^i x \in C_r$ and $T^i y \in C_s$. Define $r(n, C, K)$ to be the maximal cardinality of a $(n, C)$-separated subset of $k$.

Now fix a metric $d$, an invariant Borel probability measure $\mu$, a finite Borel partition $P = \{ P_1 , . . . , P_k\}$ and $\sigma > 0$. Choose compact sets $k \subset C_r \subset P_r$ so that $C = \cup C_i$ satisfies it$\mu(C) > 1 - \sigma/2$. Choose $K$ and $N$ as in mentioned lemmas By the Shannon-McMillan-Breiman theorem

$$\color{red}{r(n,P, K) > (1 - 2\sigma)2 ^{(h_{\mu}(T'P)-\sigma)n}}.$$

This problems comes up from paper by Michael Handel, Bruce Kitchens and Daniel J. Rudolph on Entropy: http://link.springer.com/article/10.1007/BF02761650

• The inequality you are looking for has nothing to do with the compact sets; only the partition. S-M-B states that for a set of points $x$ of large measure (measure $1-2\sigma$), the measure of the element of $\bigvee_{i=0}^{n-1} T^{-i}\mathcal P$ containing $x$ is less than $2^{-n(h(\mu,\mathcal P)-\sigma)}$. Hence, in order to cover the space, one needs a large number of partition elements. Commented Jul 11, 2017 at 14:50
• I don't understand your first equality. The left side is a partition and the right side is an integer. I will explain the inequality below. Commented Jul 12, 2017 at 4:51

Let $T$ be an ergodic transformation of $(X,\mu)$. Let $\mathcal P$ be a partition of $X$. Write $\mathcal P(x)$ for the element of $\mathcal P$ in which $x$ lies. Now write $\mathcal P_n=\bigvee_{j=0}^{n-1}T^{-j}\mathcal P$, so that $\mathcal P_n(x)$ is the element of $\mathcal P_n$ containing $x$.
The Shannon-Macmillan-Breiman theorem states that if $T$ is an ergodic transformation of $(X,\mu)$ and $h=h_\mu(T,\mathcal P)$, then $\tfrac 1n\log\mu(\mathcal P_n(x))\to -h$ for $\mu$-a.e. $x$.
Since $\tfrac 1n\log_2\mu(\mathcal P_n(x))$ converges almost surely to $-h$, it also converges in measure. That is: for any $\epsilon>0$, there exists an $n_0$ such that for $n\ge n_0$, $$\mu\{x\colon |\tfrac 1n\log_2\mu(\mathcal P_n(x))+h|\le \epsilon\}>1-\epsilon.$$
In particular, for sufficiently large $n$, $\mu\{x\colon \mu(\mathcal P_n(x))\le 2^{-n(h-\epsilon)}\}>1-\epsilon$. Notice that $A=\{x\colon\mu(\mathcal P_n(x))\le 2^{-n(h-\epsilon)}\}$ is a union of sets of the form $\mathcal P_n(x)$. Since each has measure at most $2^{-n(h-\epsilon)}$, there must be at least $(1-\epsilon)2^{n(h-\epsilon)}$ such cylinder sets since $\mu(A)>1-\epsilon$.
The argument in the paper is a slight extension of this, obtained by intersecting $A$ with $K$.
• Thanks for your solution, but in this paper $/mu$is taken invariant measure. Commented Jul 12, 2017 at 12:20
• OK. So take any ergodic measure with entropy at least $h(\mu)$. The same argument works. Commented Jul 12, 2017 at 12:20