3
$\begingroup$

Suppose we generate the following sequence by repeatedly picking a letter from the alphabet (26 letters):

LLL EEE HHH QQQ MMM QQQ OOO TTT EEE YYY XXX GGG...

So the first letter of every group of 3 letters is drawn independently with a probability of $\frac{1}{26}$ and the next two are then deterministic and are equal to the letter drawn at the first position of each group.

The entropy of every first symbol of the sequence seems to me $\log26$ (we use base 2) as we need $\log26$ bits and $0$ the two letters after it, as they don't provide any new information and I don't need any new bits.

So with adding a new letter in the second sequence (in the example, the letter "E"), I would need $2$ times $\log26$ bits to describe 6 letters in the sequence, so I could eventually compress my sequence with a factor of $3$ and thus my entropy rate would be $\frac{\log26}{3}$.

But I'm lost with the theoretical derivation of it. It says the entropy rate is defined as:

$$H(X) = \lim_{n->\infty} \frac{1}{n}H(X_1, X_2, X_3, \dots X_n)$$

Then it says that $H(X)$ is a measure of the entropy per symbol of the variable $X_t$, and the function goes like:

$$\log26 + 0 + 0 + \log26 + 0 + 0+\dots+ \log26 + 0 + 0$$

Now it says this function is "squashed" between two bounds:

$\frac{\log26}{3}n \le H(X_1, X_2, X_3, \dots X_n) \le \frac{\log26}{3}(n+2)$

Dividing both bounds with $n$ I see that the entropy rate is indeed $\frac{\log26}{3}$.

But could someone explain the intuition behind the function $H(X)$ and how these bounds are established?

$\endgroup$
8
  • $\begingroup$ I guess by MMMM you meant MMM ? $\endgroup$
    – leonbloy
    Dec 16, 2021 at 16:52
  • $\begingroup$ ah yes, exactly =) $\endgroup$ Dec 16, 2021 at 16:53
  • 1
    $\begingroup$ What do you mean by the entropy rate of the particular realization? Entropy rate is generally with respect to the random variables $X_1, X_2, \dots$ that make up the stochastic process, not in terms of outcomes. The key insight of the Shannon entropy is that content is irrelevant- the entropy of a random variable depends on the probability law (e.g. the PMF of the random variable, not the outcome itself). $\endgroup$ Dec 16, 2021 at 17:15
  • 1
    $\begingroup$ @TravisCCuvelier I kind of rephrased my question a bit, maybe this makes more sense. $\endgroup$ Dec 16, 2021 at 17:38
  • 1
    $\begingroup$ fair enough. Edited the question. $\endgroup$ Dec 17, 2021 at 18:17

2 Answers 2

3
$\begingroup$

Sketch:

In general, $n$ can be written as $$n = 3 m + r $$ where $m,r$ are non-negative integers and $r \in \{1,2, 3\}$ is the remainder of $n$ divided by $3$, plus one.

Then $$H_n = (m +1)H(X) = \left(\frac{n+3-r}{3}\right) H(X)$$

Can you go on from here?

$\endgroup$
0
2
$\begingroup$

$X_i^{1} \sim U(\{1,2,\ldots 26\})$, i.i.d., s.t., $H(X_i^{1})=\log_2{26}$, where the r.v. represents the first symbol of the $i^{th}$ group $X_i$. All the groups (except possibly the last one) contain (at most) 3 variables, with the $1^{st}$ being random, the others being completely deterministic.

There can be 3 cases:

  1. $n \equiv 0 (\text{mod } 3)$: there are $\frac{n}{3}$ groups for which the first one is randomly (uniformly) chosen from $26$ symbols, the other two are fully determined, hence total entropy $H(X)=\sum\limits_{i=1}^{\frac{n}{3}}H(X_i^{1})=\frac{n}{3}\log{26}$.

  2. $n \equiv 1 (\text{mod } 3)$: there are $\frac{n-1}{3}$ groups for which the first one is randomly (uniformly) chosen from $26$ symbols, the other two are fully determined, additionally there is one single symbol in the group $X_{\frac{n-1}{3}+1}$, hence total entropy $=\sum\limits_{i=1}^{\frac{n-1}{3}}H(X_i^{1})+H\left(X_{\frac{n-1}{3}+1}^{1}\right)=\frac{n-1}{3}\log{26}+\log{26}=\frac{n+2}{3}\log{26}$.

  3. $n \equiv 2 (\text{mod } 3)$: there are $\frac{n-2}{3}$ groups for which the first one is randomly (uniformly) chosen from $26$ symbols, the other two are fully determined, additionally there is a last group with two symbols in the group $X_{\frac{n-2}{3}+1}$, hence total entropy $=\sum\limits_{i=1}^{\frac{n-2}{3}}H(X_i^{1})+H\left(X_{\frac{n-2}{3}+1}^{1}\right)=\frac{n-2}{3}\log{26}+\log{26}=\frac{n+1}{3}\log{26}$.

Hence, $\frac{n}{3}\log{26}\leq H(X) \leq \frac{n+2}{3}\log{26}$.

$\endgroup$
1
  • 1
    $\begingroup$ Typographical thing - $\LaTeX$ has an explicit command for logarithms, $\log$, which is generally preferred to $log$, e.g. $\log x$ vs $log x$. $\endgroup$ Dec 17, 2021 at 7:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .