# Estimate entropy of a binary process in terms of decay of correlations

Suppose $( X_{n} )$ is an ergodic binary process with $$\mathbb P(X_{n}=1)= \mathbb P(X_{n}=0)=\frac 12.$$

Naturally the entropy (rate) $h(X)$ of $X=(X_{n})$ satisfies $$h(X)=\lim_{n\to\infty} \frac 1n H(X_1,\ldots, X_n)\le H(\frac 12)=\log 2.$$ The entropy will "drop" due to dependencies in $(X_n)$.

Suppose that $$\sigma^2=\sum_{n=2}^{\infty} \sup_{a,b\in\{0,1\} }\Bigl| \mathbb P(X_{1}=a,X_{n}=b)-\mathbb P(X_{1}=a)\mathbb P(X_{n}=b)\Bigr|$$ is very small: $\sigma^2\ll 1$. Small $\sigma^2$ suggests that $(X_{n})$ are nearly independent. Can one derive a lower bound for $h(X)$ of the form $$h(X)\ge \log 2- f(\sigma^2),$$ where $f$ is a continuous function with $f(0)=0$? My feeling is that small $\sigma^2$ should imply that the $\bar{d}$-metric between $\{X_{n}\}$ and the $\text{Ber}(1/2)$-process should be small, hence implying that entropies should be close as well.

In the oposite direction, suppose $\sigma^2$ is large. Then the entropy entropy drop $\log 2- h(X)$ should be substantial as well. For example, for every $\epsilon>0$ one can find $D>0$ such that for every binary process with $\sigma^2>D$ $$h(X)\le \log 2 -\epsilon.$$

Any ideas, references?

-

I would not be surprised if small $\sigma^2$ does indeed imply small d-bar distance to Bernoulli, but I think that the converse is false. Rather, processes with arbitrarily small d-bar distance to Bernoulli can have $\sigma^2=+\infty$.

To see this let $(x_n)$ be a sequence which generates the $(\frac{1}{2},\frac{1}{2})$-Bernoulli process, and let $N>0$. Define a new sequence $(z_n)$ by taking $z_n:=x_n$ when $n$ is not divisible by $2^N$. Otherwise, take $z_n:=1$ if $n=k2^N$ for even $k$, and $z_n:=0$ if $n=k2^N$ for odd $k$.

Now consider the (ergodic) process generated by $(z_n)$. It is not difficult to see that $0$ and $1$ have equal probability, and when $n$ is divisible by $2^{N+1}$ we have $$\mathbb{P}(X_1=X_n=1)=\left(1-\frac{1}{2^N}\right)\cdot \left(\frac{1}{2}\right) + \left(\frac{1}{2^N}\right)\cdot 1 = \frac{1}{2}+\frac{1}{2^{N+1}}$$ so that $$\sup_{a,b}\left|\mathbb{P}(X_1=a,X_n=b)-\mathbb{P}(X_1=a)\mathbb{P}(X_n=b)\right|\geq \frac{1}{2^{N+1}}.$$ In particular $\sigma^2=+\infty$ as claimed.

-

There is no continuity in the relationship between $h(X)$ and $\sigma^2$ either way.

In one direction the example of Ian shows that the entropy can be arbitrarily close to $\log 2$, whereas $\sigma^2 = \infty$. Let me slightly reformulate and simplify it. Take an integer $N$ (there is no reason for it to be a power of 2) and define the following stationary sequence of 0 and 1. First take the sequence of alternating 0 and 1 with distance $N$ between consecutive digits and position it on $\mathbb Z$ randomly and uniformly (by assigning to each of the $2N$ ways of doing that equal probabilities). Then fill the remaining gaps with eguidistributed 0,1-valued Bernoulli variables. The resulting measure is obviously shift invariant and ergodic. Its entropy is $(1-1/N)\log 2$, whereas, as Ian explained, $\sigma^2=\infty$ (the summands in the definition of $\sigma^2$ are, up to a constant multiplier, just the total variation differences between the uniform measure on $(0,1)$ and the conditional measure conditioned by the $n$-h coordinate, which take the same non-zero value for all multiples of $N$) .

In the opposite direction one can construct an example with $\sigma^2=0$ (all the coordinates are pairwise independent), whereas the entropy is strictly smaller than $\log 2$. It is based on the classical example of 3 random variables which are not jointly independent in spite of being pairwise independent. Namely, if $\Omega$ is the probability space which consists of 4 atoms $\omega_1,\omega_2,\omega_3,\omega_4$ with equal weights 1/4, then the indicator functions $\alpha_1,\alpha_2,\alpha_3$ of the respective subsets $(\omega_1,\omega_4), (\omega_2,\omega_4),(\omega_3,\omega_4)$ [how does one make curly brackets here?] do the job. Now take the Bernoulli scheme with the base $\Omega$, then for the random sequence $$\dots \alpha^{-1}_3,\alpha^0_1,\alpha^0_2, \alpha^0_3, \alpha^1_1, \dots$$ all the coordinates are pairwise independent (so that $\sigma^2=0$), whereas the entropy is $(2/3)\log 2$.

-

-
Thinking back, I have absolutely no idea why I used powers of two! – Ian Morris Dec 26 '12 at 12:10
Thanks, the process I want to understand has many other useful properties I can use, I was looking for minimal conditions. – user12345678 Dec 26 '12 at 19:48