On Estimates for the Entropy of a Language According to Shannon

A. P. Savčuk

Teoriâ veroâtnostej i ee primeneniâ, Tome 9 (1964) no. 1, pp. 154-157

Résumé

C. E. Shannon proposed the upper and lower estimates for the entropy of a language. It is proved in this paper that in order to attain the lower estimate, it is necessary and sufficient that some letters be equally probable, the probability of the rest being equal to zero after any combination $b_i^N$ of $N$ letters such that $p(b_i^{N-1})>0$. In order to attain the upper estimate, it is necessary and sufficient that the probability that the $k$-th letter appears after $b_i^N$ be dependent on $k$ and $N$, and independent of $i$, for a sequence of language letters arranged in descending order as to the probability that they appear after $b_i^N$ (note that the arrangement of letters in this sequence, however, depends on $i$). In the latter result it is supposed that no letter occurs with the probability $=1$, which is true for every real language.