Word length using entropy : Maximum entropy criteria

Question

The question is based on research paper titled, Markovian language model of the DNA and its information content In the supplementary document, the Authors show how they determine the word length of DNA sequence using entropy. A word is a consecutive occurence of DNA symbols. The optimal word length is selected as the one which produces maximum entropy out of all the different length words. But it is not quite clear to me from the plot, if they are using Shannon's entropy rate to plot the curve or just entropy. This is because in the text they mention that the plot is entropy but th formula they have used is of the entropy rate. So, my question is what is the correct way to determine word length using entropy concept.

Consider a toy example for which the implementation in Matlab is given:

A sequence of data of length $N$ can be subdivided into equal sixed blocks each of length (size) $l$. For each block, $w$, we can calculate the entropy known as the block entropy. Considering, entropy calculation by varying the size of the blocks ie., the window size is different. The entropy of the entire sequence is $H_N = 1.99$. I then create subwords using different sized windows : Window = [1,2,4,6,8,10,12] This gives Shannon's entropy for each sub-word (block) as

$H_w = \{H_1 = 1.99119952705784, H_2 = 3.20880064685926, H_4= 4.97725978596446, H_6= 6.10391179247315, H_8= 6.40200948312778,H_{10}=6.44186057426463, H_{12} = 6.45326152085405\}$ respectively.
Out of these entropy values for each block the maximum entropy value is, maxEntropy = 6.4638 for block of size blksze = 12.

General questions, not specific to topic of DNA or text sequence data : My confusion and questions are

1. Based on these values of block entropy, is it possible to determine what is the optimal length $l$ of the sequence ? For which value of sequence length $l <N$ would the entropy of this sequence $H_l$ converge towards the entropy of $H_N$? Please correct me where wrong.

2. Can entropy of the whole sequence be less than the block size? For equiprobable occurrece of symbols, $H_N \le log2(4)= 2$ this is the theoretical value. But, when the block size 12 I got entropy for $H_{w} = H_{12} = 6.45326152085405$ which is greater than $H_N = 1.99$. I don't know if this result is correct and what I should expect theoretically.

3. Is my implementation correct? How to infer the plots?

Details:

Consider a source that emits codewords consisiting of adjacent symbols of length $l$. The sequence length is $N > l$. If the source is binary ($n=2$ symbols), then I have $N(w) = n^l$ possible words of length $l$. Each word is associated with a probability and I need to estimate the probability numerically since it is unknown. Let, $n=4$ and the alphabet set is $A = {1,2,3,4}$. Let the symbol sequence be $s =[2, 3, 4, 1, 2, 2,1, 3,2, 1, 2, 4,\ldots]' $ and $N$ denotes the number of elements in the sequence.

A block of size $l$ is defined as a segment of $l$ consecutive elements of the symbol sequence or in other words a concatenation of several symbols. If $w$ is a symbol sequence of size $l$, then $N(w)$ denotes the number of blocks of $s$ which are identical to $w$.

$p(w)$ is the probability that a block from $b$ is identical to a symbol sequence $w$ of size $l$ i.e. $$p(w) = \frac{N(w)}{n-|w|+1}$$

Let, a symbol sequence of length $N = 10$ be $s = \{1,3,4,1,2,1,1,3,4,2\}$, here the alphabet set is $\mathcal{A} = \{1,2,3,4\}$ and the number of symbols $|\mathcal{A}| = n = 4$. Each symbol can be represented by 4 bits.

Answer 1

Disclaimer: This is based on generic information theory knowledge only. Too long for a comment.

Summary: The pointwise product of your two plots should go to some limit, as the relevant blocklengths and sequence lengths increase.

I don't know if this applies to DNA but in theory if your sequence is ergodic (stationary, and time averages are the same as ensemble averages, for long enough sequences) then the two entropies are related intimately.

The whole point is, if you obtain a "block" entropy $H(X_1,\ldots,X_n)$ for a block of length $n,$ then $$ \lim_{n\rightarrow\infty} \frac{H(X_1,\ldots,X_n)}{n}=H_0 $$ which is the entropy per symbol, i.e., the entropy rate, what you call shannon entropy as opposed to block entropy.

Now, the question of estimating these is a different question. In fact your program does this by a sliding window technique, which then means that it is averaging overlapping thus dependent samples.

Define the shorthand $X_i^j=(X_i,X_{i+1},\ldots,X_{j})$ where $j\geq i.$ I am sure that under suitable conditions an estimator of the form $$ \frac{\sum_{k=1}^{n-\ell+1}\hat{H}(X_k^{k+\ell-1})}{n-\ell+1} $$ where $\hat{H}(X_k^{k+\ell-1})$ is a suitable estimator for block entropy, will converge to a multiple of the entropy rate, i.e., to $\ell \times f$ where $f$ is a correction factor. However, one may need to let $\ell$ grow with $n.$