3
$\begingroup$

The following is an excerpt from Information Theory: A Tutorial Introduction, page 65.

Now, supposing the identity of each letter in English does not depend on any letter that is more than 10 letters away. In practice, the dependency between letters diminishes rapidly as inter-letter distance increase, as shown in Fig. 3.6. Once the block length has grown to $N = 10$, the identity of every letter in a given block $B_k$ depends on other letters in that block and exactly two other blocks: the previous block $B_{k-1}$ and the next block $B_{k+1}$. All other blocks contain letters which are more than 10 letters away from, and therefore independent of, every letter in block $B_k$.

If the original text is sufficiently long, and if there are a large number of blocks, then the dependency between adjacent blocks just described accounts for a tiny proportion of the overall dependency between blocks. Thus, the more blocks there are, and the longer each block is, the smaller the dependency between blocks. By analogy, it is as if each block is one of a large number of independent super-symbols, and if the blocks are independent then finding their entropy is relatively simple. The only question is, how long do those blocks have to be to ensure that they are independent?

The block length beyond which inter-letter dependence falls to zero is called correlation length $N_C$. Once the block length exceeds the correlation length, it is as if all blocks are effectively independent, so increasing the block length $N$ beyond $N_C$ has a negligible effect on the estimated entropy $G_N$. At this point, $G_N$ equals the entropy of English; that is $G_N = H$. This matters because Shannon's theorems are expressed in terms of infinite block lengths, but in practice these theorems apply to any block length which exceeds the correlation length of the sequence under consideration.

Given some block, I can't see how block count decreases dependency on two blocks adjacent to it. Could someone, please, explain?

$\endgroup$
  • 1
    $\begingroup$ I think the word increase doesn't mean by 2 adjacent block.It means when the string gets bigger, block sizes change and also percentange of dependency of total blocks, decrease $\endgroup$ – Hamed_gibago Jan 3 at 12:31
  • $\begingroup$ @Hamed_gibago now that I reread the passage, everything looks clear, thanks to your comment and to the answer below $\endgroup$ – user3496846 Jan 4 at 13:52
2
+50
$\begingroup$

The more blocks there are, and the longer each block is, the smaller the dependency between blocks.

There are two tendencies. Let us explain one by one.

(Tendency of more blocks) Assume the block size does not change. The more blocks there are in a string, the smaller the dependency between blocks.

Suppose the block size is greater than 10. Suppose there are $N$ blocks. Since each block depends only two other blocks, the previous block and the next block, the total number of (unordered) dependent pairs of blocks is $N-1$ as each block is dependent on its next block except that there is no next block to the last block. There are $N(N-1)/2$ (unordered) pairs of blocks in total. The ratio of dependent pairs to all pairs, $\dfrac{N-1}{N(N-1)/2}=\dfrac 2N$ becomes smaller and smaller and can be arbitrarily close to 0 when $N$ goes bigger and bigger. That is one way in which we can understand the meaning of tendency of more blocks.

If the block size is not greater than 10, we can argue similarly since each block will depends on at most previous $\lceil\dfrac {10}{\text{block size}}\rceil$ blocks and next $\lceil\dfrac {10}{\text{block size}}\rceil$ blocks.

(Tendency of longer blocks) The larger each block size is, the smaller the dependency between adjacent blocks.

Consider two adjacent blocks $B$ and $C$ with $C$ following $B$. Let us consider the ordered pairs of letters where the first letter is in $B$ and the second letter is in $C$. Since every letter does not depend on any letter that is more than 10 letters away, there are at most $1+2+\cdots+10=55$ such pairs in which the two letters are dependent. As the block size $S$ goes bigger and bigger, the number of all possible pairs $S\times S$ becomes bigger and bigger quadratically. However, the number of dependent pairs stays at 55 once the block size is no less than 10. Hence the ratio of dependent pairs to all pairs becomes smaller and smaller. This is one way how we can understand the meaning of tendency of longer blocks.

If we agree that the nearer the letters, the stronger the dependency between them, then we can see that the dependency between adjacent blocks becomes smaller and smaller when the block size grows bigger and bigger even if we do not require the block sizes are no less than 10.


The above explanation follows roughly the same style as the original text. To be more precise, we should define the correlation of two blocks in mathematical terms and we should show how the ordered dependent pairs of letters from two blocks contribute/determine to the correlation of two blocks. That will not be an easy undertaking to be done rigorously. However, it is, I believe, intuitively clear that ratio of dependent pairs from two blocks to the total pairs is in proportional (not necessarily linearly) to the dependency of the two blocks, as long as the latter is defined reasonably. So the above explanation should convince you the correctness of the quoted conclusion. After all, that quoted conclusion is supposed to be easy and intuitive to understand.


Given some block, I can't see how block count decreases dependency on two blocks adjacent to it.

If "block count" means the number of letters in a block, then "larger block count decreases dependency between the given block and either of the two blocks adjacent to it" is the tendency of more blocks as I have explained in the above.

If we consider "block count" as the number of blocks, then "larger block count" does not decreases dependency between the given block and either of the two blocks adjacent to it, as you believed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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