MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer

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


share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.