in question (?). First, they divided the text of length $T$ into $M$ parts, of
lengths $T_{1},T_{2},\dots,T_{M}$. The frequency of each word $w_{i}$ in part
$m$ was written as $f_{i}^{m}=n_{i}^{m}/T_{m}$, where $n_{i}^{m}$ was the
number of occurrences of $w_{i}$ in $m$. The quantities

$p_{i}^{m}=\frac{f_{i}^{m}}{\sum_{k=1}^{M}f_{i}^{k}}$ (3.16)

define a normalized distribution over the $M$ parts of the text: for each
word, $\sum_{m}p_{i}^{m}=1$. The entropy associated with this distribution
is111Here, in contrast to Sec. 1.3, we use for the entropy the lower-case
notation $h_{i}$ to emphasize that it is a quantity defined for each single
word, and not for the set of all the words in the text. A similar notation
will later be used in Chap. 4.

$h_{i}=-\sum_{m=1}^{M}p_{i}^{m}\log_{M}p_{i}^{m}.$ (3.17)

The extreme values of this entropy, $h_{i}=0$ and $1$, are attained when
$w_{i}$ appears in only one part, and when its number of occurrences in each
part $m$ is proportional to $T_{m}$, respectively.

It can be shown that, when the parts are equal in length, the expected value
of the entropy $h_{i}$ for a word whose $n_{i}$ occurrences are distributed
uniformly at random along the text is $h_{i}=1-(M-1)/2n_{i}\ln M$ for large
$n_{i}$ (?). On the basis of this result, ? suggested to characterize the
heterogeneity in the distribution of word $w_{i}$ over the text partition by
means of the index

$E_{i}=\frac{2\ln M}{M-1}n_{i}(1-h_{i}).$ (3.18)

For equal parts and a random uniform distribution, $E_{i}\approx 1$. Words
with heterogeneous distributions, on the other hand, are expected to have
larger values of $E_{i}$.

The index $E_{i}$ was calculated for all the words in Darwin’s On the Origin
of Species. The partition of the text was chosen to coincide with its sixteen
chapters. In order of decreasing $E_{i}$, the twenty words with the largest
indices were the following: hybrids, I, sterility, islands, species, forms,
varieties, instincts, breeds, fertility, formations, crossed, selection,
organs, characters, nest, instinct, rudimentary, formation, and genera. Except
for I, which appears second in the list, it is clear that all these words are
highly topical to the book.

These results reinforce the notion that heterogeneity in the distribution of a
word is a signature of topicality and, at the same time, show that entropy-
like measures are also suitable to describe such heterogeneity. While the
introduction of a partition adds in principle a largely arbitrary set of
parameters (the part lengths $T_{m}$), thus weakening the generality of
quantitative results, applying the method to a natural partition of the text
—for instance, its division into chapters— may enhance the significance of the
heterogeneity in the distribution of certain words with respect to that
partition. Frequent words specific to a given part, in particular, would be
assigned maximal values of the index $E_{i}$.

On the other hand, the presence of the non-topical word I high in the above
list puts forward a caveat on the use of this kind of methods for keyword
detection. The large value of $E_{i}$ for the word I is related to the
switching of Darwin’s style along On the Origin of Species, between scholarly
discourse and first-person narrative (?), which naturally makes the
distribution of I very heterogeneous. However, methods such as those described
above —which are purely based on a statistical characterization of burstiness—
cannot discern between different sources of heterogeneity. As other algorithms
for automatic text analysis, thus, they should be regarded as potential
components of a battery of tools whose efficiency depends, precisely, on being
used in combination with each other.

As a closing note, it is interesting to mention that the burstiness measure
defined in Eq. (3.15) has also been applied to DNA sequences (?). It is well
known that deoxyribonucleic acid (DNA) is a biological macromolecule that
stores the genetic information on which the ontogenic development of all
living organisms is based. Structurally, it consists of a sequence of
nucleotides of four types (A, T, C, and G), whose specific ordering encodes
the information conveyed by the sequence. As an information carrier, the four-
symbol DNA code is appealingly reminiscent of language. It should be recalled,
however, that not all of the DNA sequence bears genetic information: large
non-coding sectors, whose function is not yet understood, are intercalated
between coding sections (?).

Figure 3.6: Average burstiness index $\sigma$ for DNA “words” in four
biological species, as a function of the “word” length $l$. A “word” is
defined as an array of $l$ consecutive nucleotides in the DNA sequence.
Adapted from ?.

? divided long samples of DNA sequences of several biological species into
non-overlapping “words” consisting of $l$ contiguous nucleotides. There are
$4^{l}$ such “words.” For each $l=1,2,\dots,6$ —and starting at $l$
consecutive places in the sequence, to take into account all its possible
partitions— the burstiness index $\sigma_{i}$ was calculated for each “word”
and then averaged over the whole “lexicon.” Figure 3.6 displays the average
burstiness $\sigma$ as a function of $l$ for four living species: the
bacterium Escherichia coli, the yeast Saccharomyces cerevisiae, the nematode
Caenorhabditis elegans, and the hominid Homo sapiens. In all cases, and for
all values of $l$, the index is larger than one, revealing the ubiquity of
burstiness in DNA. The values of $\sigma$, however, are well below those found
for some topical words in language samples (see Table 3.2).

The most interesting feature is, in any case, the peak in the burstiness index
at $l=3$ (except for H. sapiens). Nucleotide triads have been identified as
the most elementary units of genetic information —the codons— each of them
controlling the process of production of a different aminoacid (?). The coding
sections of DNA are arrays of contiguous codons. It is noticeable that the
position of the maximum of $\sigma$ coincides with the length of these basic
“words” of the genetic code. The fact that the peak becomes less significant
as the complexity of the organisms grows has been associated with their
increasing relative contents of non-coding DNA, which reaches more than 98%
for H. sapiens. The results shown in Fig. 3.6 for our species suggest that, if
non-coding DNA stores any information, one- and two-nucleotide “words” might
be playing a relevant role in this function.

##  Chapter 4 Order, Entropy, and Information in Written Texts

From the perspective of quantitative linguistics, measuring the amount of
information conveyed by human language is a fascinating challenge. This quest
—which is directly related to the quantification of redundancy in speech and
writing, of the constraints imposed by the function of language as a means of
communication, and of the degree of order in linguistic patterns— is best
dealt with using the tools of information theory. It is in this conceptual
framework, in fact, that a generic communication channel can be mathematically
characterized, gauging the roles of source, transmitter, receiver, and the
intervening noise. Information theory was applied to the analysis of language
from its very inception by Claude Shannon, who presented the first estimation
of the entropy of written English —as an inverse measure of its degree of
redundancy, predictability, and organization— in 1951. This classical result
immediately elicits many intriguing questions. Are all human tongues, from a
statistical viewpoint, equally organized? Does the information contents of a
text depend on its literary genre or style? Was the emergence of redundancy
favored or hindered along language evolution? Most of these questions remain,
to a large extent, unexplored. In the last few decades, however, a renewed
interest in the applications of information theory to human language —also
inspired by the affinity with other natural “languages,” such as the genetic
code stored in DNA (see Sec. 3.3)— has led to novel results on the statistical
properties of grammatical and semantic patterns.

We begin this chapter with a review of the classical definition and
calculation of the entropy of language, as conceived by Shannon, which regards
language samples as partially predictable sequences of letters. Then, we focus
on information-theoretical approaches which, more significantly from a
linguistic viewpoint, analyze the statistical properties of word sequences. In
this framework, it has been shown that the amount of information which is lost
when shuffling the words in a sample of language is the same in very distant
tongues, thus constituting a kind of quantitative linguistic universal. In
turn, the mutual information between the bursting distribution of topical
words and a partition of the text to which they belong, makes it possible to
define a typical scale —of the order of several hundred to a few thousand
words— associated with the unfolding of semantic contents. Finally, not only
topicality but also the grammatical function of words is shown to influence
the uniformity of their usage across literary texts.

###  4.1 Shannon’s Evaluation of the Entropy of Printed English

“Can we define a quantity which will measure, in some sense, how much
information is ‘produced’ by… a [stochastic] process, or better, at what rate
information is produced? Suppose we have a set of possible events whose
probabilities… are known but that is all we know concerning which event will
occur. Can we find a measure of how much ‘choice’ is involved in the selection
of the event or of how uncertain we are of the outcome?” With these questions,
Claude Shannon motivated, in his foundational papers on information theory,
the introduction of the entropy of a source of information (??). At that
stage, he conceived an information source as the emitter of a message in the
form of an ordered sequence of discrete symbols, able in principle to produce
infinitely long sequences.

According to Shannon, the entropy per symbol —or entropy rate (?)— of the
information source is given by the limit

$h=\lim_{n\to\infty}\frac{H_{n}}{n},$ (4.1)

with

$H_{n}=-\sum_{\\{s_{1},s_{2},\dots,s_{n}\\}}p(\\{s_{1},s_{2},\dots,s_{n}\\})\log_{2}p(\\{s_{1},s_{2},\dots,s_{n}\\}).$
(4.2)

Here, $p(\\{s_{1},s_{2},\dots,s_{n}\\})$ is the probability of occurrence,
along the symbol sequence, of the $n$-symbol subsequence (or block)
$\\{s_{1},s_{2},\dots,s_{n}\\}$. The sum runs over all the possible
subsequences of length $n$; if the number of different symbols is $V$, there
are $V^{n}$ such subsequences. In Eq. (4.2), $H_{n}$ is the entropy associated
with the probability distribution $p(\\{s_{1},s_{2},\dots,s_{n}\\})$ over the
set of $V^{n}$ subsequences. The choice of the logarithm base amounts to
fixing the units in which the block entropies $H_{n}$ and the entropy per
symbol $h$ are measured. Using $\log_{2}$ defines such units as bits and bits
per symbol, respectively (see Sec. 1.3). When the sequence is a written text
where each letter is identified with a symbol, in Shannon’s words, if the text
“is translated into binary digits (0 or 1) in the most efficient way, $h$ is
the number of binary digits (i.e. bits) required per letter of the original
language” (?).

Since $h$ integrates knowledge about the probabilities of all possible symbol
arrays of any length, it bears information on the statistical correlations of
the sequence —and, thus, on its organizational structure— at all scales. Large
values of the entropy are obtained when the probabilities of different
subsequences of a given length are similar, and therefore correspond to high
degrees of uncertainty. In this situation, the signal redundancy is small, and
the observation of any given subsequence provides little information about the
rest of the signal. Small entropies, on the other hand, are associated with
repetitive, redundant, highly predictable sequences. Shannon gave a
quantitative definition of redundancy as

$r=1-\frac{h}{h_{\max}},$ (4.3)

where $h_{\max}=\log_{2}V$ is the maximum entropy per symbol attainable by a
sequence built up from the collection of $V$ symbols. This corresponds to a
random sequence where all symbols occur with the same probability,
uncorrelated to each other. The redundancy $r$ is a measure of the fraction of
the sequence that is determined by its structural constrains or, as Shannon
put it, the part that cannot be “chosen freely.”

In an alternative formulation of the same definition for the entropy, Shannon
introduced the quantities

$F_{n+1}=-\sum_{\\{s_{1},\dots,s_{n}\\}}\sum_{\\{s_{n+1}\\}}p(\\{s_{1},\dots,s_{n},s_{n+1}\\})\log_{2}p(s_{n+1}|\\{s_{1},\dots,s_{n}\\}),$
(4.4)

where $p(s_{n+1}|\\{s_{1},\dots,s_{n}\\})$ is the conditional probability of
occurrence of symbol $s_{n+1}$ given that it was preceded by the subsequence
$\\{s_{1},\dots,s_{n}\\}$. It can be proven that $F_{n+1}=H_{n+1}-H_{n}$ and,
from here, that

$h=\lim_{n\to\infty}F_{n}.$ (4.5)

The quantity $F_{n+1}$ measures the degree of uncertainty in the $(n+1)$-th
symbol, under the assumption that one knows the precedent $n$ symbols.
Therefore, it provides an inverse measure of the predictability of the
sequence, given a certain amount of information about its foregoing
constitution.

While Shannon’s work was aimed at giving a mathematical basis to the
description of generic communication processes —including, in particular,
those occurring between or mediated by artificial (electrical) devices— his
references to human language were unavoidable (?). Three years after his first
papers on the subject, he published his own empirical results on the entropy
of written (or “printed”) English (?). In this study, English texts were
viewed as sequences of $27$ symbols, including the $26$ letters of standard
English and the space between words. Any other written symbols were
disregarded.

Shannon estimated the entropy on written English on the basis of its
predictability, namely, from the evaluation of the quantities $F_{n}$ defined
from Eq. (4.4). For the first few values of $n$, he relied on preexisting
tabulations of the frequencies of single letters, digrams (two-letter
subsequences) and trigrams (three-letter subsequences) in large corpora of
English texts, which yielded $F_{1}=4.03$, $F_{2}=3.32$, and $F_{3}=3.1$ bits
per letter. For longer subsequences, however, tabulations were not available,
and it was necessary to resort to different means to evaluate predictability
beyond three letters. Shannon’s ingenious solution to this problem was to
devise a method that exploited the fact that “anyone speaking a language
possesses, implicitly, and enormous knowledge of the statistics of language.
Familiarity with the words, idioms, clichés and grammar enables him to fill in
missing or incorrect letters in proof-reading, or to complete an unfinished
phrase in conversation” (?).

With this idea in mind, Shannon designed two experiments, involving human
subjects.111In view of Shannon’s acknowledgements in his 1951 paper, the
subjects were his wife, Mrs. Mary E. Shannon, and his collaborator, Dr. B. M.
Oliver. In the first one, a text unfamiliar to the subject was selected, and
the subject was asked to guess the first letter in the passage. If the guess
was correct, he or she was so informed and proceeded to guess the following
letter (or space). If it was not, the subject was told the correct letter and
then proceeded to the next guess. This procedure was continued through the
whole text. The correct text up to each point was available to the subject for
use in predicting the following letters. A typical result of this experiment,
exemplified by a short sentence, was as follows:

The first line reproduces the original text. In the second line, dashes and
letters indicate correct and incorrect guesses, respectively.

In this first experiment, out of a total of $129$ letters, $89$ (69%) were
guessed correctly. Errors, not unexpectedly, occurred more frequently at the
beginning of words and syllables. Shannon pointed out that, at first sight, it
might seem that the second line contains much less information than the first.
Actually, however, their information contents is the same, in the sense that
the subject was able to build up the original text just with the information
given in the second line. A subject’s “mathematically identical” twin, who
would respond exactly in the same way when faced to the same problem, should
be able to recover the first line from the second. The redundancy of 69%
($r=0.69$) found in this experiment was sensibly higher than the value
obtained for written English in work previous to Shannon’s, of about 50% (?).

The second experiment provided a more direct evaluation of predictability. As
in the first one, the subject knew the text up to the current point and was
asked to guess the next letter. If the guess was wrong, he or she was told so
and was asked to guess again. This was repeated until the correct letter was
found, and the number of guesses needed to find the correct letter was
recorded at each step. A typical result was as follows:

Here, the second line indicates the corresponding number of guesses for each
letter (or space).

To make the experiment’s results statistically more significant, each subject
was required to guess the text, letter by letter, of one hundred samples of
literary English —taken at random from D. Malone’s Jefferson the Virginian—
fifteen letters in length each. Additionally, a similar test was performed in
which $100$ letters were known to the subject and the 101-st letter was to be
guessed. The fraction of times $q_{k}^{n}$ that the $n$-th letter was
correctly guessed at the $k$-th guess was recorded.

Shannon noticed that the quantities $q_{k}^{n}$ are linked to the conditional
probabilities $p(s_{n+1}|\\{s_{1},\dots,s_{n}\\})$ of Eq. (4.4) by the
relation

$q_{k}^{n+1}=-\sum_{\\{s_{1},\dots,s_{n}\\}}p(s_{k}|\\{s_{1},\dots,s_{n}\\}),$
(4.6)

where the sum runs over all the subsequences of length $n$ and $s_{k}$ is the
$k$-th most likely letter to follow each particular subsequence. This relation
makes it possible, through rather involved algebraic arguments, to find a
connection between the quantities $q_{k}^{n}$ and $F_{n}$. Specifically, it is
possible to show that

$\sum_{k=1}^{27}k(q_{k}^{n}-q_{k+1}^{n})\log_{2}k\leq
F_{n}\leq-\sum_{k=1}^{27}q_{k}^{n}\log_{2}q_{k}^{n},$ (4.7)

which fixes lower and upper bounds for $F_{n}$.

Figure 4.1: Lower and upper bounds for the quantities $F_{n}$ measured in bits
per letter, as functions of the subsequence length $n$, estimated for written
English from inequalities (4.7). The limit of $F_{n}$ for $n\to\infty$ gives
the entropy per symbol of a sequence. Dashed lines are plotted as a guide to
the eye. Adapted from ?.

Figure 4.1 shows a plot of the bounds for $F_{n}$ as functions of $n$,
computed from the results of Shannon’s second experiment. Perhaps the most
significant feature emerging from these results is that, while $F_{n}$ seems
to have attained a rather stable value for $n=15$, there is still a
substantial difference with the estimation of $F_{100}$. Throughout the range
not covered by the experiment, $F_{n}$ decays from around $2$ bits/letter to
about half that value. This reveals the existence of nontrivial structures in
the letter sequence, extending for at least several tenths of symbols. The
estimation of the entropy of written English arising from the experiment is of
about $1$ bit per letter. The corresponding redundancy is just below 80%.

Since Shannon’s times, several different procedures have been used to obtain
other estimates of the entropy of English. ? proposed a gambling game to
evaluate predictability in language, again involving human subjects, and found
$h\approx 1.3$ bits/letter. This method however, was criticized on the basis
of the tendency of humans to overestimate the probability of very unlikely
events (?) —a critique that may have also been applied to Shannon’s
experiments. Non-human methods included text compression based on prediction
from partial matching (PPM), which was applied to English texts of several
genres and styles, yielding $h\approx 1.5$ bits/letter (?). ?, in turn, used
elaborate nonparametric entropy estimators and got, for four novels by Jane
Austin, $h=1.8$ bits/letter. Other authors (?) complemented the calculation of
the entropy with a detailed analysis of scaling properties in the convergence
of the normalized block entropies $H_{n}/n$ towards $h$, Eq. (4.1), as $n$
tends to infinity.

While all these studies gave values for the entropy per letter in written
English within a well defined range of $1$ to $2$ bits/letter, it cannot be
said that they yielded a quantitatively very consistent, accurate result. The
discrepancies can in part be ascribed to methodological differences but,
surely, the fact that they were applied to different kinds of texts also
played a role. Probably none of the English corpora involved in these studies
was, from a broad statistical viewpoint, really representative of their
language.

There is however another major drawback in the above approaches to the
definition of the entropy of written language, which jeopardizes their
interest for linguistics. Considering a text as a sequence of letters (and
other characters) brings into the calculation of entropy a contribution from
the specific order in which letters are combined to form words, which has
essentially no relevance to grammar (see also Sec. 3.1). Syntactic structures,
as well as longer-ranged linguistic patterns, are expected to be largely
impervious to the organization of letters inside words. Lexical similarities
between distant languages, with quite disparate grammatical rules, suggest
that the two aspects have had independent evolutionary origins. In the
following sections, we review several information-theoretical studies of the
statistics of language patterns which consider written texts as sequences of
words, instead of letters. This linguistically more compelling point of view
should help to better discern between the different contributions to the
information conveyed by language.

###  4.2 The Information Stored in Word Ordering

In the framework of information theory, the convenience of viewing written
texts as word sequences —instead of character sequences, as in the preceding
section— is well illustrated by the following simple experiment. Suppose that,
in a given text, each different word is substituted by a number, for instance,
its rank in the Zipf frequency list (see Secs. 2.1 and 3.2). Obviously, this
“translation” will leave the message communicated by the text unaltered. It
suffices to have the proper “dictionary” to fully recover the original text
from the numeric sequence. On the other hand, the entropy per symbol of this
numeric sequence is expected to substantially differ form that of the original
sequence of letters. Indeed, the amount of information associated with the
specific ordering of letters inside words will not contribute to the former.

This observation recalls that language structures occur at many levels of
organization, from the internal morphology of individual words to the long
word sequences that define the contextual elements which endow the message
with intelligibility and meaning. While all these levels contribute to the
degree of order of language, their linguistic roles are not the same. The
inflection of words —namely, the different word forms that derive from a
single root through conjugation or declension— defines, at the shortest-range
level, grammatical categories such as person, number, gender, and tense. At an
intermediate level, the rules of syntax determine the relative order of words
inside a phrase or sentence. In some human tongues, the mutual position of
words is crucial to discern between subjects, actions, and objects, while
others compensate a larger flexibility in syntactic order with more complex
inflection (?). Finally, semantic structures —those associated with the global
meaning of a message— emerge at even larger ranges, involving several
sentences or paragraphs, as the information contained in the message is
unraveled and developed.

The fact that the words in the lexicon of a given language sample are not all
used with the same frequency, as described by Zipf’s law (see Chap. 2),
reveals already a certain degree of nontrivial linguistic organization,
amenable to quantification by means of an entropy-like measure. If, in a text
of length $T$ with a lexicon of $V$ different words, the word $w_{i}$
($i=1,2,\dots,V$) occurs $n_{i}$ times, the quantity

$H_{Z}=\log_{2}\frac{T!}{n_{1}!n_{2}!\cdots n_{V}!}$ (4.8)

is the entropy (measured in bits, see Sec. 1.3) associated with Zipf’s
distribution for the text in question. It equals the entropy of the ensemble
of all the possible orderings of the text’s words and can therefore be
identified with the entropy of a random shuffling of the text. When the
numbers $n_{i}$ are generally large, by virtue of Stirling’s formula (?),
$H_{Z}$ can be approximated as

$H_{Z}\approx-\sum_{i=1}^{V}n_{i}\log_{2}\frac{n_{i}}{T}=-T\sum_{i=1}^{V}f_{i}\log_{2}f_{i},$
(4.9)

where $f_{i}=n_{i}/T$ is the frequency of appearance of $w_{i}$. Taking into
account that, in a typical text or speech, there are many words which occur
only a small number of times, the quality of the Stirling approximation must
nevertheless be carefully assessed in each particular case. However, it turns
out to be very convenient for analytical treatment. The quantity $H_{Z}$ can
be interpreted as the entropy of an infinitely long sequence of words —or of
an infinitely large ensemble of finite sequences— where each word $w_{i}$
appears with frequency (or probability) $f_{i}$.

The Zipf entropy $H_{Z}$ is to be compared with $H_{0}=T\log_{2}V$, which
stands for the entropy of a uniform probability distribution over the whole
lexicon: $f_{i}=V^{-1}$ for all words $w_{i}$. The two quantities would
coincide if all the words of the lexicon appeared in the text exactly the same
number of times. The difference

$H_{0}-H_{Z}=T\log_{2}V+T\sum_{i=1}^{V}f_{i}\log_{2}f_{i}$ (4.10)

is always positive, and is an estimation of the information associated with
the actual distribution of word occurrences with respect to a “text” where all
words are used with the same frequency. Note that the entropies $H_{Z}$ and
$H_{0}$ are proportional to the text length $T$. It makes therefore sense to
define such quantities as $h_{Z}=H_{Z}/T$ and $h_{0}=H_{0}/T$, which provide
measures of the entropy (or of the information) per word.

| $\ \ \ h_{Z}\ \ \ $ | $\ \ \ h_{0}\ \ \ $ | $h_{0}-h_{Z}$
---|---|---|---
Æneid | $12.27$ | $14.02$ | $1.75$
Don Quijote | $9.60$ | $14.50$ | $4.90$
D. Copperfield | $9.28$ | $13.78$ | $4.50$
Table 4.1: Entropies per word, $h_{Z}$ and $h_{0}$, as defined in the text,
for Æneid, Don Quijote, and David Copperfield, and their difference
$h_{0}-h_{Z}$. The three quantities are measured in bits per word.

Table 4.1 shows the entropies per word, $h_{Z}$ and $h_{0}$, and their
difference, for Virgil’s Æneid, Miguel de Cervantes’s Don Quijote, and Charles
Dickens’s David Copperfield (see also Chap. 2). Owing to the comparable
lexicon size of the three works, the respective values of $h_{0}$ are similar.
On the other hand, $h_{Z}$ is sensibly higher for Æneid. This is directly
related to the fact that its Zipf distribution is much flatter than for the
other two texts, as discussed in Chap. 2 in connection with Fig. 2.1.
Accordingly, the information per word associated with the distribution of word
occurrences, $h_{0}-h_{Z}$, is smaller for the Latin poem.

At a higher organizational level, the structure of a language sample is
determined by the particular manner in which words are arranged along their
ordered sequence. The increment from the information contained in the mere
collection of different words, each one considered with its respective number
of occurrences, to the information contained in the specific word sequence
that constitutes the actual text or speech, is a quantification of the cost of
constructing a message useful to communication out of a disordered assemblage
of words.

In order to capture the whole contribution of the correlations implicit in the
sequence of words of a real text, according to Eqs. (4.1) and (4.2), its
entropy should be obtained from the block entropies

$H_{n}=-\sum_{\\{w_{1},w_{2},\dots,w_{n}\\}}f(\\{w_{1},w_{2},\dots,w_{n}\\})\log_{2}f(\\{w_{1},w_{2},\dots,w_{n}\\})$
(4.11)

where, for each $n$, the sum runs over all the possible arrays of $n$ words,
$\\{w_{1},w_{2},\dots,w_{n}\\}$. The quantity
$f(\\{w_{1},w_{2},\dots,w_{n}\\})$ is the frequency (i.e., an estimation of
the probability) of appearance of each array over the whole text under study.
From Eq. (4.1), the entropy per word to be assigned to the text is
$h=\lim_{n\to\infty}H_{n}/n$. Any real text, however, is of course finite in
length, so that the limit for $n\to\infty$ cannot be achieved. Moreover, the
long-range correlations present in language (??) make a direct evaluation of
the block entropies $H_{n}$ highly inaccurate. More precise methods, which
deal efficiently with correlations, are based on the fact that the entropy of
a symbolic sequence provides a lower bound for the length of a lossless
compressed version of the same sequence (?). In other words, the entropy can
in principle be evaluated by finding the length of the sequence after having
been compressed by means of an optimal algorithm. On the basis of the
classical Lempel–Ziv compression algorithm (?), Kontoyiannis and coworkers,
among others, have developed efficient entropy estimators, with robust
convergence even in the presence of strong correlations (??). These estimators
advantageously replace the calculation of $h$ by means of block entropies.

In an extensive study, applied to a large corpus consisting of 7077
texts,222For the study, the texts were mostly downloaded in electronic format
from the public-domain depository of Project Gutenberg, www.gutenberg.org. At
the time of this writing, Project Gutenberg stands as the largest free source
of electronic books in various languages. the entropy per word $h$ of each
text was calculated using one of Kontoyiannis’s estimators (?). The texts were
written in eight languages belonging to five different linguistic families and
including a language isolate: English, French, and German, from the Indo-
European family; Finnish, from the Finno-Ugric family; Tagalog, from the
Austronesian family; Sumerian, which is unrelated to other known languages;
Old Egyptian, from the Afro-Asiatic family; and Chinese, from the Sino-Tibetan
family (?). The corpus comprised texts from several periods, genres, and
styles, including literary, scientific, and humanistic writings. For each
text, the entropy per word associated to the distribution of word occurrences,
$h_{Z}$, was also computed. As discussed above, the difference $D=h_{Z}-h$ is
a measure of the increment of information when passing from a random version
of the text, where each different word appears with a probability taken from
Zipf’s distribution, to the ordered word sequence of the actual text. In the
context of information theory, $D$ can be identified as an estimation of the
Kullback–Leibler distance per word between the probability distributions of
the ordered text and its random counterpart (see Sec. 1.3).

Figure 4.2: Schematic representation of the distributions of entropy per word
in the actual text, $h$, the entropy per word in a random version of the text,
$h_{Z}$, and their difference, $D=h_{Z}-h$, for collections of $5112$ texts in
English, $101$ in Finnish, and $392$ in Chinese. Entropies are measured in
bits per word. Adapted from ?.

Figure 4.2 shows distributions of the values obtained for $h$, $h_{Z}$, and
$D$, for the English, Finnish, and Chinese sub-corpora, comprising 5112, 101,
and 392 texts, respectively. Note that the languages belong to three different
families. It turns out that, for the three languages, the distributions of the
entropy difference $D$ are narrower than those of $h$ and $h_{Z}$. Moreover,
although the distributions for both $h$ and $h_{Z}$ are shifted from each
other across languages, the distributions for $D$ seem to attain their maxima
around the same value.

Similar results reveal that this is also the case for the other languages
considered in the study. Table 4.2 shows the average values obtained for $h$,
$h_{Z}$, and $D$ in each language. Over different languages, the entropies $h$
and $h_{Z}$ average, respectively, $5.3$ and $8.9$ bits per word. Their
standard deviations, in turn, represent 23% and 14% of the respective
averages. On the other hand, for the difference $D=h_{Z}-h$ the standard
deviation is below 6% of the average of 3.6 bits per word. In other words, the
value of $D$ is much better defined across languages than the entropies $h$
and $h_{Z}$. An equivalent conclusion stands when the Stirling approximation
of Eq. (4.9) is not introduced, but the exact form of $H_{Z}$, Eq. (4.8), is
used instead: for the eight languages considered in the study, the
corresponding difference $D$ is narrowly concentrated around $3.3$ bits per
word.

| $\ \ \ \ \ h\ \ \ \ \ $ | $\ \ \ \ \ h_{Z}\ \ \ \ \ $ | $D=h_{Z}-h$
---|---|---|---
English | $5.7$ | $9.2$ | $3.5$
French | $5.8$ | $9.4$ | $3.6$
German | $6.2$ | $9.8$ | $3.5$
Finnish | $7.1$ | $10.9$ | $3.8$
Tagalog | $5.1$ | $8.5$ | $3.4$
Sumerian | $3.5$ | $7.5$ | $3.9$
Old Egyptian | $3.7$ | $7.0$ | $3.3$
Chinese | $5.3$ | $9.1$ | $3.8$
Table 4.2: Entropy per word in the actual text, $h$, entropy per word in a
random version of the text, $h_{Z}$, and their difference, $D$, averaged over
the texts in each language. The three quantities are measured in bits per
word. Adapted from ?.

Due to the broad dissimilarity of grammar rules and vocabulary inflections
across linguistic families, the entropies of the ordered texts and their
random counterparts show substantial variations from language to language.
Their difference, on the other hand, remains bounded around a well defined
value. Beyond the obvious diversity between different tongues, therefore, the
contribution of word ordering to the information conveyed by language emerges
as a robust universal statistical feature.

It turns out that the homogeneity of the entropy related to word ordering,
when compared across languages, can be understood in terms of the existence of
a balance between lexical diversity and correlation lengths in word sequences
(?). Simple model languages and real human tongues show an inverse relation
between word correlation lengths and the entropy per word associated with the
distribution of word occurrences, $h_{Z}$. In model languages, moreover, it is
possible to prove that this inverse relation is directly linked to a constant
difference between $h_{Z}$ and the entropy per word in the ordered text, $h$.

To illustrate this fact, it is useful to introduce a minimal model language,
with a lexicon consisting of only two words. Word sequences are built up by
means of a first-order Markov process (?) defined by the transition matrix

$M=\left(\begin{array}[]{cc}\mu_{1}&1-\mu_{2}\\\
1-\mu_{1}&\mu_{2}\end{array}\right),$ (4.12)

where the element $M_{ij}$ ($i,j=1,2$) is the probability that word $i$
follows word $j$ in the sequence. Introducing an abstract variable to identify
the two words, say, $x=0$ for the first word and $x=1$ for the second, a
correlation length $\lambda$ for the word sequence can be estimated by
computing the auto-correlation function (see Sec. 1.2)

$c(\tau)=\langle x_{t+\tau}x_{t}\rangle-\langle
x_{t}\rangle^{2}\sim\exp\left(-\tau\ln\frac{1}{\mu_{1}+\mu_{2}-1}\right),$
(4.13)

namely,

$\lambda=\left(\ln\frac{1}{\mu_{1}+\mu_{2}-1}\right)^{-1}.$ (4.14)

The entropy per word of the distribution of word occurrences is, in turn,

$h_{Z}=-p_{1}\log_{2}p_{1}-p_{2}\log_{2}p_{2},$ (4.15)

where $p_{1}=(1-\mu_{2})/(2-\mu_{1}-\mu_{2})$ and
$p_{2}=(1-\mu_{1})/(2-\mu_{1}-\mu_{2})$ are the unconditional probabilities of
the first and the second word, respectively. Running over different pairs of
values for the parameters $\mu_{1}$ and $\mu_{2}$, sequences with different
correlation length $\lambda$ and entropy $h_{Z}$ can be generated. For each
ordered sequence, the entropy $h$, and thus the difference $D=h_{Z}-h$, can be
estimated as well.

Figure 4.3: Left panel: Schematic representation of the curves of constant
$D=h_{Z}-h$ in the plane with coordinates given by the entropy of word
occurrences $h_{Z}$, measured in bits per word, and the correlation length,
$\lambda$, for a Markovian two-word model language. Right panel: Fluctuation
exponent $\gamma^{\prime}$ (which, as explained in the text, is a measure of
the slowness of correlation decay) as a function of the entropy $h_{Z}$,
averaged over texts in four languages. Adapted from ?.

The left panel of Fig. 4.3 shows curves of constant $D$ on the plane
($h_{Z},\lambda$), for the two-word Markovian language. The inverse relation
between $h_{Z}$ and $\lambda$ defined by these curves implies that, to
maintain a fixed level for $D$ in this class of languages, it is necessary to
either increase the entropy $h_{Z}$ while decreasing the correlation length
$\lambda$, or vice versa. The same result was obtained for Markovian languages
with lexicons of three and four words.

Does this relation between $h_{Z}$ and the correlation length also hold for
human languages? As already mentioned in Sect. 3.3, correlations in real word
sequences do not decrease exponentially, as in Eq.(4.13), but rather as a
power law: $c(\tau)\sim\tau^{-\gamma}$, with $\gamma>0$ (?). While in this
situation it is not possible to define the correlation length as a typical
decay length for $c(\tau)$, the exponent $\gamma$ provides, qualitatively, the
same kind of measure: small and large $\gamma$ correspond, respectively, to
slow- and fast-decaying correlations. More directly, the fluctuation exponent
$\gamma^{\prime}=(2-\gamma)/2$ (??) is large for long-range correlations and
small for short-range correlations.

The right panel of Fig. 4.3 shows the fluctuation exponent $\gamma^{\prime}$
as a function of the entropy per word associated with the distribution of word
occurrences, $h_{Z}$, averaged over the texts in four languages which showed
statistically significant differences in $\gamma^{\prime}$: English, French,
German, and Finnish. For each text, the exponent was calculated using the
technique of detrended fluctuation analysis (?). These languages, for which
the difference $D$ is approximately constant, define a curve with the same
interdependency between entropy and correlation as found in the Markovian
models.

As for many other quantitative parameters related to language, the diversity
in the values of the entropy of word occurrences and of the word correlation
length across different tongues may be ascribed to progressive divergencies
along their evolution, not unlike those that separated groups of biological
species from each other. The above results suggest, however, that linguistic
evolutionary drift was constrained to occur keeping the difference of entropy
associated with word order at a constant level. This difference seems to
capture a fundamental quantitative property of language, common to a broad
group of human tongues. Hence, the mechanisms underlying the way in which we
assemble long words sequences to convey meaning may ultimately derive from
universal cognitive constraints, inherent to the human species.

###  4.3 The Scales of Meaning

The entropy of word ordering, as a measure of the information needed to define
a specific arrangement of words out of the mere collection of word
occurrences, is a global quantitative property of the particular language
stream for which it is computed. According to the discussion of Sec. 3.3,
however, it is to be expected that different words contribute in different
degrees to that information. Burstiness —namely, the high heterogeneity in the
distribution of certain words along a text— determines a large increase in the
information associated with the order of words. This contribution is granted
by topical words, whose occurrences are concentrated in localized parts of the
text, in contrast with functional words, whose role in language determines a
more homogeneous usage.

The localization of topical words along a text is a characteristic feature of
the way in which humans organize the contents of a complex message,
articulating meaning as the discourse progresses. Topical words, which are
borne with the semantic essence of the message, tag the parts to which they
belong. From a statistical viewpoint, an interesting question is —for a long
array of words conveying coherent information— to determine the optimal
partition that maximizes the capability of words to tag each part. This
question points to the problem of defining typical text lengths associated
with the development of meaningful contents in elaborate communication (?).

Take a text of $T$ words, with a lexicon of $V$ words
$\\{w_{1},w_{2},\dots,w_{V}\\}$, and divide it into $M$ parts of equal
size.333If the text length $T$ is not an integer multiple of the number of
parts $M$, one can truncate the text at the largest multiple of $M$ below $T$.
At most, the cut will be of length $M$ for coarse partitions (small $M$) or
$T/M$ for fine partitions (large $M$). In the cases of interest in practice,
which involve long texts, relevant partitions are those with $M\ll T$, and the
effect of truncation is negligible. The probability that a randomly chosen
occurrence of word $w_{i}$ belongs to part $m$ is

$p_{i}^{m}=\frac{n_{i}^{m}}{n_{i}},$ (4.16)

where $n_{i}^{m}$ is the number of occurrences of $w_{i}$ in that part, and
$n_{i}$ is its total number of occurrences all over the text. Note that, under
the condition that all parts have the same size, $p_{i}^{m}$ coincides with
the homologous quantity defined in Eq. (3.16). The entropy associated with the
distribution of $w_{i}$ over the text partition is

$h_{i}=-\sum_{m=1}^{M}p_{i}^{m}\log_{2}p_{i}^{m}.$ (4.17)

Being an entropy defined for each single word, the units of $h_{i}$ are bits
per word (see also footnote $1$ in Sec. 3.3). In the present analysis, the
number of parts $M$ is a variable and, therefore, is not used as the logarithm
base to normalize the entropy, in contrast with Eq. (3.17).

Much like in the study presented in the previous section, the aim here is to
compare the value of $h_{i}$ in an actual text with the entropy $h_{i}^{R}$
obtained from a random shuffling of the text in question. However, there are
two main differences. First, as pointed out above, $h_{i}$ is now separately
computed for each word $w_{i}$. Second, the degree of order of the actual text
with respect to its random surrogate is measured up to the partition size,
i.e. within a scale $s=T/M$. This scale characterizes the coarseness with
which the distribution of words over the text is ascertained. Since
$n_{i}^{m}$ does not change by rearranging the word’s occurrences within each
part, $h_{i}$ is not sensible to the text randomization below such scale. The
average value of $h_{i}^{R}$ over all possible word orderings can be evaluated
analytically, as

$\langle
h_{i}^{R}\rangle=-M\sum_{k=1}^{K}\frac{k\left(\begin{array}[]{c}n_{i}\\\
k\end{array}\right)\left(\begin{array}[]{c}T-n_{i}\\\
s-k\end{array}\right)}{n_{i}\left(\begin{array}[]{c}T\\\
s\end{array}\right)}\log_{2}\frac{k}{n_{i}},$ (4.18)

with $K=\min\\{n_{i},s\\}$ (?).

Figure 4.4: Entropies of individual words from Darwin’s On the Origin of
Species, in bits per word, plotted against the respective number of
occurrences. The text was divided into $64$ parts of equal length. Black and
grey dots correspond, respectively, to the entropies evaluated from the
ordered text, $h_{i}$, and from a random shuffling of it, $h_{i}^{R}$. The
curve stands for the average of the random-text entropy, Eq. (4.18). Adapted
from ?.

As an illustration of the difference between the entropy $h_{i}$ and its
random-text counterpart $h_{i}^{R}$, Fig. 4.4 shows the two quantities for the
words of Charles Darwin’s On the Origin of Species, dividing the whole text
into $M=64$ parts. To ease the comparison with each other and with $\langle
h_{i}^{R}\rangle$, entropies are plotted against the number of occurrences of
each word. Black and grey dots stand, respectively, for the entropies $h_{i}$
and $h_{i}^{R}$ of each individual word. The random-text entropies were
calculated from a single shuffling of the original text. The curve corresponds
to the average random-text entropy, given by Eq. (4.18). As expected, the
random-text entropies are generally above those calculated from ordered
version. Note that, for very large numbers of occurrences, the two entropies
collapse on the same value, of $\log_{2}M=6$ bits/word. These highly frequent
words —most of which are functional words such as articles, prepositions, and
connectors— are distributed in a way that can hardly be discerned from a
random arrangement. At the other end, for words with a few occurrences, the
difference between the two entropies is also not too large, and varies around
$1$ bit/word. The largest discrepancies are found for words with intermediate
frequencies, $10\lesssim n_{i}\lesssim 200$, where the entropy difference can
attain some $4$ bits/word.

While, for any given word, the difference $d_{i}=\langle h_{i}^{R}\rangle-
h_{i}$ is typically a positive quantity —which measures the degree of order in
the word’s distribution over the text partition— its specific value depends on
the partition size. Indeed, consider the limiting case in which $M=1$, so that
all the word’s occurrences belong to the same part, whose size equals the text
length ($s=T$). In this case, any shuffling leaves the number of occurrences
per part unchanged, so that $d_{i}=0$. Even more, for $M=1$ both $h_{i}$ and
$h_{i}^{R}$ are identically equal to zero. Similarly, in the opposite limit
where the text is divided into as many parts as words, $M=T$ ($s=1$), each
part can contain at most one occurrence. The corresponding entropies are again
identical: $h_{i}=h_{i}^{R}=\log_{2}n_{i}$. Thus, $d_{i}=0$ also for $M=T$. On
the other hand, the entropy difference $d_{i}$ should be positive for
intermediate partitions. In particular, it may attain one or more maxima for
$1<M<T$.

Figure 4.5: The entropy difference $d_{i}=\langle h_{i}^{R}\rangle-h_{i}$,
measured in bits per word, for four words from Darwin’s On the Origin of
Species, as a function of the partition scale $s$. Dashed curves are
polynomial fittings drawn as guides to the eye. Note that the four plots have
the same scales in both axes.

Figure 4.5 shows the entropy difference $d_{i}$ as a function of the scale
$s=T/M$, for four words from On the Origin of Species: islands, instinct  (see
also Fig. 3.4), species, and for. In the four cases, there is a well defined
intermediate maximum. However, the scale at which this maximum occurs, as well
as its height, differ considerably from word to word. The two topical words
islands and instinct display high maxima, both above $2$ bits/word, attesting
their very heterogeneous distribution along the text. The positions of the
maxima —respectively, $s_{\max}\approx 2000$ and $5000$— give typical scales
for such heterogeneity. The word for, on the other hand, shows much smaller
values of $d_{i}$, which discloses its very uniform use. The maximum, slightly
above $0.1$ bits/word, occurs for a scale $s_{\max}\approx 150$. The case of
species is intermediate: it is a frequent word with a rather homogeneous
distribution —though not as homogeneous as a typical functional word. Its
maximum, at $s_{\max}\approx 200$, is above $0.5$ bits/word.

The entropy differences $d_{i}$ for the individual words in a text can be
integrated into a single quantity, characteristic of the whole text, given by

$d=\sum_{i=1}^{V}f_{i}d_{i},$ (4.19)

where the sum runs over the whole lexicon, and $f_{i}=n_{i}/T$ is the total
frequency of each word. The quantity $d$, which depends on the partition size
and is also measured in bits per word, characterizes the mutual information
between the distribution of words and the partition: the product $f_{i}d_{i}$
gauges how much information is contained in an occurrence of word $w_{i}$
about its belonging to any given part of size $s$ in the real text, with
respect to a random distribution (?). The left panel of Fig. 4.6 shows the
mutual information $d$ as a function of the scale $s$ for three books in
English: Charles Darwin’s On the Origin of Species ($T=155800$), Herman
Meville’s Moby Dick ($T=218284$), and Bertrand Russell’s Analysis of the Mind
($T=89586$). In the three cases, the mutual information displays a well
defined peak at, respectively, $s_{\max}\approx 8000$, $4000$, and $3000$. For
this particular scale, the mutual information of the word distribution and the
text partition differs maximally between the real text and a random shuffling
of it. It is at this particular partition size that the distribution of words
better discriminates between different sections of the text.

Figure 4.6: Left panel: Mutual information $d$, in bits per word, as a
function of the partition scale $s$ for Ch. Darwin’s On the Origin of Species,
H. Meville’s Moby Dick, and B. Russell’s Analysis of the Mind. Right panel:
The zone in the plane of coordinates given by the text length $T$ and the
scale of maximal mutual information $s_{\max}$ occupied by a corpus of $5258$
books and other writings in English. Adapted from ?.

Note that, for the three books considered above, there is no direct relation
between the book’s length $T$ and the scale at the maximum of the mutual
information. In an analysis of a corpus containing almost $5300$ texts in
English, nevertheless, it was found that there is a tendency of $s_{\max}$ to
grow as $T$ increases (?). The corpus included English and American
literature, as well as texts on science, technology and humanities. The left
panel in Fig. 4.6 shows the zone in the plane ($T,s_{\max}$) where the texts
of that corpus are found. It is interesting to realize that at the lower–left
corner of this zone, corresponding to short texts with small $s_{\max}$, one
finds collections of short quotations with no thematic unity, such as
Quotations of Lord Chesterfield and Quotes and Images From The Novels of Georg
Ebers. For these texts, $s_{\max}$ is below $100$ words. The opposite corner,
with $s_{\max}\approx 10000$, is occupied by such books as E. Gibbon’s History
of The Decline and Fall of the Roman Empire and J. Burckhardt’s Civilization
of the Renaissance in Italy, two long treatises with very consistent, uniform
subjects.

Over the whole corpus, the typical scale of maximum mutual information varies
around several hundred to a few thousand words. Clearly, such lengths are far
beyond the scope of the rules of syntax. Syntactic constraints, in fact, apply
at the level of phrases and sentences, spanning several words at most. The
values of $s_{\max}$, on the other hand, should be related to the
characteristic scales associated with the development of the successive
thematic subjects covered by a book. If the text is divided into sections of
size $s_{\max}$, the distribution of words in those parts bears maximum
information with respect to a random distribution. For single texts with
overall semantic unity, $s_{\max}$ should represent the typical length of the
spans over which semantic structures develop.

On the Origin of Species | Moby Dick | Analysis of the Mind
---|---|---
species | I | image
varieties | whale | memory
hybrids | you | word
forms | Ahab | belief
islands | is | desire
selection | Queequeg | sensations
genera | thou | object
plants | he | past
seeds | captain | knowledge
sterility | boat | contents
Table 4.3: Some of the words with largest individual contribution to the total
mutual information $d$, in three books in English. Adapted from ?.

This conjecture is supported by the identification, in each text, of the words
whose contribution to the overall mutual information $d$ —given, according to
Eq. (4.19), by the product $f_{i}d_{i}$— is large. Table 4.3 extracts some of
the words with the largest contributions to $d$ in On the Origin of Species,
Moby Dick, and Analysis of the Mind. Their relation to the semantic contents
of each book is apparent in Darwin’s and Russell’s treatises. In Meville’s
novel, such words as the pronouns I, you, and he —which in other texts would
play an essentially functional role— attain high relevance due to the
narrative style of the work, whose structure is built up around its
characters.

The typical scales $s_{\max}$ which emerge from this quantitative analysis
coincide with the text lengths that, in English, are widely recognized as the
span which allows for the development of a coherent line of argument. As an
example, at the time of the present writing (August 2011), the influential
scientific journal Nature was accepting manuscripts of two kinds, Letters and
Articles, whose recommended lengths were $1500$ and $3000$ words,
respectively. Editorial comments in the same journal, in turn, contained some
$600$ words. The magazine Science accepted longer articles, but all shorter
contributions —Brevia, Technical Comments, Perspectives, among others— were
limited to around $1000$ words in length.

The analysis of the above mentioned corpus included also the determination of
the maximal mutual information per word, $d_{\max}$, in each book. It turns
out that the distribution of $d_{\max}$ over the whole corpus is sharply
peaked around $0.2$ bits/word. Therefore, whereas the partition size which
maximizes the mutual information, $s_{\max}$, varies substantially between
different texts in English, the accuracy with which words tag each part is
much more uniform.

Figure 4.7:  Distribution of the maximal mutual information per word,
$d_{\max}$, measured in bits per word, for three sub-corpora of English books:
$3329$ literary words, $1374$ books on history and philosophy, and $555$ books
on science and engineering. Adapted from ?.

This picture changes, however, when books are differentiated from each other
by their main theme or genre. The corpus can be divided into three groups:
$3329$ literary texts, $1374$ treatises on history and philosophy, and $555$
books on science and engineering. Figure 4.7 shows the distribution of the
mutual information at the maximum, $d_{\max}$, over the three groups. It turns
out that literary and humanistic texts tend to have lower values of the
information per word than the books on science and engineering. The latter
have a broader distribution, extending over higher values of the maximal
mutual information. This indicates that the usage of language in scientific
and engineering books is such that the distribution of words tags more
efficiently the different parts of the text.

In summary, the study of the mutual information of the distribution of
individual words, with respect to a given partition of the text, confirms
that, as seen in Sec. 3.3, heterogeneity and topicality are closely related
features. Additionally, we see now that the information-theoretical approach
to word distributions makes it possible to identify, for each text, a typical
scale given by the partition size at which the mutual information attains a
maximum. For such partition, word occurrences tag most efficiently the
different parts of the text. The analysis of a large corpus of English books
showed that those typical scales vary between several hundred to a few
thousand words, and are therefore much longer than the range at which
grammatical rules apply. They are rather related to the spans needed to
expound and unfold the contents that an elaborate and coherent piece of human
language conveys.

###  4.4 Word Patterns Across Texts

The same kind of information-theoretical techniques discussed in Secs. 3.3 and
4.3 for analyzing the structures of the distribution of words among different
parts of a given text, can be used to disclose patterns of word usage across
different texts. In a corpus formed by the concatenation of several texts
—each of them being a self-consistent piece of language, with its own style
and topic— heterogeneity in word usage may emerge from a variety of factors.
Very topical words, related to the specific subjects of just one or a few
texts in the corpus, will be highly concentrated in those parts. The entropy
associated with their distribution will correspondingly be relatively small.
On the other hand, functional words with no special relation to particular
topics should display a more homogeneous distribution. However, their marginal
heterogeneities may be the signature of more subtle differences. Genre and
style, indeed, are expected to have an effect on the usage of such words,
influencing both their frequency and their arrangement along each text. The
quantitative analysis of differences in the usage of the most frequent words
—including articles, prepositions, pronouns, and connectors, which have a
mainly functional role in language— is in fact a basic tool in authorship
attribution (??).

Heterogeneity in the distribution of word occurrences has been studied in
connection with the grammatical role of each word, in a corpus formed by the
concatenation of $36$ plays by William Shakespeare (?), including tragedies
and comedies of historical (Roman and English) and fictional inspiration. The
average length of the plays was close to $24600$ words, and the corpus had
$23150$ different words. For each word $w_{i}$, the entropy $h_{i}$ given by
Eq. (3.17) was calculated, with each part of the corpus corresponding to an
individual play ($M=36$). By construction, $h_{i}=0$ for words that occur in
only one play, and $h_{i}\approx 1$ for highly frequent, evenly distributed
words. If all plays had equal lengths, an evenly distributed word with a total
of $n_{i}$ occurrences —for which the number of occurrences in each play were
approximately proportional to the play’s length— would have $h_{i}\approx
1-(M-1)/2n_{i}\ln M$ for large $n_{i}$.

The upper panel of Fig. 4.8 shows the quantity $(1-h_{i})n_{i}$ for all the
words in the Shakespeare corpus plotted against their number of occurrences
$n_{i}$. Words over the oblique dashed line are those with $h_{i}=0$. The
horizontal dashed line, whose vertical coordinate equals $(M-1)/2\ln M$, would
in turn coincide with the position of very frequent words with a homogeneous
distribution over a partition of the corpus into equal parts. It turns out
that the words in this corpus are widely spread between the two boundaries.
The identification of different word types in different parts of this plot
confirms some expected features, but also discloses less obvious patterns.

Figure 4.8: Upper panel: The quantity $(1-h_{i})n_{i}$ as a function of the
number of occurrences $n_{i}$ for the $23150$ different words of $36$ plays by
William Shakespeare. The entropy $h_{i}$ is measured in bits per word. The
oblique dashed line corresponds to $h_{i}=0$. The horizontal dashed line is
the value expected for frequent, evenly distributed words, in the case that
all the plays has the same length. The position of several words is identified
by labels. Lower panel: Schematic representation of the zones occupied by five
grammatical classes over the same plane as in the upper panel: (A) proper
nouns, (B) nouns referring to nobility status, (C) pronouns, (D) verbs and
adverbs, and (E) common nouns and adjectives. Note that the horizontal scales
of the two panels are not the same. Adapted from ?.

Predictably, close to the line $h_{i}=0$ one finds proper nouns corresponding
to character names —many of which are unique to a single play— but also to the
name of countries, towns, and other places. Each of these words is strongly
related to, at most, a few parts of the corpus. Slightly less specific to
individual plays are nouns who refer to the status of human beings, in
particular, to nobility titles —which are highly frequent, and topically very
important, in Shakespeare’s plays. The position of some of these words has
been identified in the upper panel of Fig. 4.8.

The analysis of the Shakespeare corpus comprised the classification of the
$2000$ most frequent words into five classes, according to their grammatical
function (?). This sub-lexicon coincides, approximately, with all the words
that occur more than $40$ times in the corpus. Two of the classes were, as
mentioned above, proper nouns, and nouns referring to nobility status. The
other three classes were pronouns, verbs and adverbs, and common nouns and
adjectives. The lower panel of Fig. 4.8 shows the regions of the same plane of
the upper panel which are occupied by each class.

As advanced, proper and nobility nouns (respectively, zones A and B) lie along
the line $h_{i}=0$, the former closer than the latter. The case of pronouns
(zone C) is more striking. While, not unexpectedly, they are located in the
region corresponding to very frequent words, with large $n_{i}$, their
relatively high position in the plot reveals a surprising degree of
heterogeneity across the corpus. Since all Shakespeare’s plays are supposed to
have been written by the same author, within consistent genre and style, an
uneven use of pronouns —which have a mainly functional linguistic role— seems
anomalous. An account of this feature in terms of the plays’ themes, which are
their more conspicuous difference with each other, seems unlikely. Until now,
the anomaly has not been satisfactorily explained or explored further.

A comparison of verbs and adverbs (zone D) with common nouns and adjectives
(zone E) is also interesting. While the two zones intersect in a wide region,
the average position of common nouns and adjectives is clearly above that of
verbs and adverbs, revealing that the latter are more homogeneously
distributed over the corpus than the former. This difference, again, has not
been explained. Is it that, because of the very nature of the theatrical
genre, objects are more specific to a given subject than the actions in which
they are involved? Or, perhaps, is this the consequence of the essentially
different semantic nature of nouns and verbs —which, however, appear so
closely linked in the communication of any meaningful message? These questions
are still open. Answering them requires, along with sound linguistic
argumentation, extensive statistical analysis of large corpora in different
tongues, genres, and styles which, in spite of some consistent efforts in the
last few decades, remains largely incipient.

## Bibliography

  * Abramowitz, M. and Stegun, I. A. (1972). _Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables_ (Dover, New York).
  * Álvarez Lacalle, E., Dorow, B., Eckmann, J. P. and Moses, E. (2006). Hierarchical structures induce long-range dynamical correlations in written texts, _Proc. Natl. Acad. Sci. USA_ 103, 21, pp. 7956–7961.
  * Applebaum, D. (2005). _Lévy Processes and Stochastic Calculus_ (Cambridge University, Cambridge).
  * Auerbach, F. (1913). Das Gesetz der Bevölkerungskonzentration, _Petermans Mitteilungen_ 59, 1, pp. 74–76.
  * Bernstein, L. (1973). _The Unanswered Question_ (Harvard University, Cambridge).
  * Boroda, M. G. and Polikarpov, A. A. (1988). The Zipf–Mandelbrot law and units of different text levels, _Musikometrika_ 1, 1, pp. 127–158.
  * Borovik, A. S., Grosberg, A. Y. and Frank Kamenetskii, M. D. (1994). Fractality of DNA texts, _J. Biomolec. Struct. Dyn._ 12, 3, pp. 655–669.
  * Brown, C. M. and Hagoort, P. (2000). _The Neurocognition of Language_ (Oxford University, Oxford).
  * Buldyrev, S. V., Goldberger, A. L., Havlin, S., Mantegna, R. N., Matsa, M. E., Peng, C.-K., Simons, M. and Stanley, H. E. (1995). Long-range correlation properties of coding and noncoding DNA sequences: GenBank analysis, _Phys. Rev. E_ 51, 5, pp. 5084 –5091.
  * Burlando, B. (1990). The fractal dimension of taxonomic systems, _J. Theor. Biol._ 146, 1, pp. 99–114.
  * Burlando, B. (1993). The fractal geometry of evolution, _J. Theor. Biol._ 163, 2, pp. 161–172.
  * Burrows, J. F. (1987). Word patterns and story shapes: The statistical analysis of narrative style, _Liter. Ling. Comput._ 2, 1, pp. 61–70.
  * Burrows, J. F. (1992). Not unless you ask nicely: The interpretative nexus between analysis and information, _Liter. Ling. Comput._ 7, 2, pp. 91–109.
  * Church, K. W. and Gale, W. A. (1995). Poisson mixtures, _Nat. Lang. Eng._ 1, 2, pp. 163– 190.
  * Consul, P. C. (1991). Evolution of surnames, _Int. Stat. Rev._ 59, 3, pp. 271–278.
  * Cover, T. M. and King, R. C. (1978). Convergent gambling estimate of entropy of English, _IEEE Trans. Inf. Theor._ 24, 4, pp. 413–421.
  * Cover, T. M. and Thomas, J. A. (2006). _Elements of Information Theory_ (Wiley-Interscience, Hoboken).
  * Ebeling, W. and Neiman, A. (1995). Long-range correlations between letters and sentences in texts, _Physica A_ 215, 3, pp. 233–241.
  * Ebeling, W. and Poschel, T. (1994). Entropy and long-range correlations in literary English, _Europhys. Lett._ 26, 4, pp. 241–246.
  * Ehrenfest, P. and Ehrenfest, T. (1911). _Begriffliche Grundlagen der statistischen Auffassung in der Mechanik_ , _Enzyklopädie der mathematischen Wissenschaften mit Einschluss ihrer Anwendungen_ , Vol. IV.2 (Teubner, Leipzig), pp. 3–90.
  * Eldridge, R. C. (1911). _Six Thousand Common English Words_ (Clement, Buffalo).
  * Feder, J. (1988). _Fractals_ (Plenum, New York).
  * Ferrer i Cancho, R. and Elvevåg, R. (2010). Random texts do not exhibit the real Zipf’s law-like rank distribution, _PLoS ONE_ 5, 3, p. e9411.
  * Ferrer i Cancho, R. and Solé, R. V. (2001a). Two regimes in the frequency of words and the origin of complex lexicons: Zipf’s law revisited, _J. Quant. Linguistics_ 8, 3, pp. 165–173.
  * Ferrer i Cancho, R. and Solé, R. V. (2001b). The small-world of human language, _Proc. Roy. Soc. London B_ 268, 1482, pp. 2261–2265.
  * Ferrer i Cancho, R. and Solé, R. V. (2003). Least effort and the origins of scaling in human language, _Proc. Natl. Acad. Sci. USA_ 100, 3, pp. 788–791.
  * Gao, Y., Kontoyiannis, I. and Bienenstock, E. (2008). Estimating the entropy of binary time series: Methodology, some theory and a simulation study, _Entropy_ 10, 1, pp. 71–99.
  * Gardiner, C. (2004). _Handbook of Stochastic Methods: for Physics, Chemistry and the Natural Sciences_ (Springer, Berlin).
  * Gelbukh, A. and Sidorov, G. (2001). _Zipf and Heaps laws’ coefficients depend on language_ , _Lecture Notes in Computer Science_ , Vol. 2004 (Springer, Berlin), pp. 332– 335.
  * Gibrat, R. (1932). _Les inégalités économiques_ (Sirey, Paris).
  * Greenberg, J. H. (1963). _Universals of Languages_ (MIT Press, Cambridge).
  * Hanley, M. L. (1937). _Word Index to James Joyce’s Ulysses_ (University of Wiconsin, Madison).
  * Harris, T. E. (1963). _The Theory of Branching Processes_ (Springer, Berlin).
  * Heaps, H. S. (1978). _Information Retrieval: Computational and Theoretical Aspects_ (Academic Press, Orlando).
  * Herrera, J. P. and Pury, P. A. (2008). Statistical keyword detection in literary corpora, _Eur. Phys. J. B_ 63, 1, pp. 135 –146.
  * Huang, K. (1987). _Statistical Mechanics_ (Wiley, New York).
  * Indurkhya, N. and Damerau, F. J. (2010). _Handbook of Natural Language Processing_ (Chapman and Hall–CRC, Boca Raton).
  * Islam, M. N. (1995). A stochastic model for surname evolution, _Biom. J._ 37, 1, pp. 119 –126.
  * Kanter, I. and Kessler, D. A. (1995). Markov processes: Linguistics and Zipf’s law, _Phys. Rev. Lett._ 74, 22, pp. 4559–4562.
  * Katz, S. M. (1996). Distribution of content words and phrases in text and language modelling, _Nat. Lang. Eng._ 2, 1, pp. 15–59.
  * Klug, W. S. and Cummings, M. R. (1997). _Concepts of Genetics_ (Prentice–Hall, Upper Saddle River).
  * Kontoyiannis, I., Algoet, P. H., Suhov, Y. M. and Wyner, A. J. (1998). Nonparametric entropy estimation for stationary processes and random fields, with applications to English text, _IEEE Trans. Inf. Theor._ 44, 12, pp. 1319–1327.
  * Krumhansl, C. L. (1990). _Cognitive Foundations of Musical Pitch_ (Oxford University, Oxford).
  * Landini, G. (2001). Evidence of linguistic structure in the Voynich Manuscript using spectral analysis, _Cryptologia_ 25, 4, pp. 275–295.
  * Lerdahl, F. and Jackendoff, R. (1983). _A Generative Theory of Tonal Music_ (MIT Press, Cambridge).
  * Lewis, M. P. (2009). _Ethnologue: Languages of the World_ (SIL International, Dallas).
  * Li, W. (1992). Random texts exhibit Zipf’s-law-like word frequency distribution, _IEEE Trans. Inform. Theor._ 38, 6, pp. 1842–1845.
  * Lü, L., K.Zhang, Z. and Zhou, T. (2010). Zipf’s law leads to Heaps’ law: Analyzing their relation in finite-size systems, _PLoS ONE_ 5, 12, p. e14139.
  * Maess, B., Koelsch, S., Gunter, T. and Friederici, A. D. (2001). Musical syntax is processed in Broca s area: an MEG study, _Nature Neurosci._ 4, pp. 540–545.
  * Manaris, B., Vaughan, D., Wagner, C., Romero, J. and Davis, R. B. (2003). _Evolutionary music and the Zipf–Mandelbrot law: Progress towards developing fitness functions for pleasant music_ , _Lecture Notes in Computer Science_ , Vol. 2611 (Springer, Berlin), pp. 522–534.
  * Mandelbrot, B. B. (1951). Adaptation d’un message à la ligne de transmission. I & II, _Comptes Rendues (Paris)_ 232, pp. 1638–1740 & 2003–2005.
  * Mandelbrot, B. B. (1955). _On recurrent noise limiting coding_ (Interscience, New York), pp. 205–221.
  * Mandelbrot, B. B. (1959). A note on a class of skew distribution function. Analysis and critique of a paper by H. A. Simon, _Information and Control_ 2, 1, pp. 90–99.
  * Mandelbrot, B. B. (1997). _Fractals and Scaling in Finance. Discontinuity, Concentration, Risk_ (Springer, New York).
  * Manrubia, S. C., Derrida, B. and Zanette, D. H. (2003). Genealogy in the era of genomics, _American Scientist_ 41, 2, pp. 158–165.
  * Manrubia, S. C. and Zanette, D. H. (2001). Vertical transmission of culture and the distribution of family names, _Physica A_ 295, 1, pp. 1–8.
  * Manrubia, S. C. and Zanette, D. H. (2002). At the boundary between biological and cultural evolution: The origin of surname distributions, _J. Theor. Biol._ 216, 4, pp. 461–477.
  * Miller, G. A. (1965). Introduction, to G. K. Zipf, The Psycho-Biology of Language. An Introduction to Dynamic Philology (MIT Press, Cambridge, 1965), pp. v–x.
  * Miller, G. A. (1981). _Language and Speech_ (Freeman, San Francisco).
  * Miyazima, S., Lee, Y., Nagamine, T. and Miyajima, H. (2000). Power-law distribution of family names in Japanese societies, _Physica A_ 278, 1–2, pp. 282– 288.
  * Montemurro, M. A. (2001). Beyond the Zipf–Mandelbrot law in quantitative linguistics, _Physica A_ 300, 3–4, pp. 567–578.
  * Montemurro, M. A. and Pury, P. A. (2002). Long-range fractal correlations in literary corpora, _Fractals_ 10, 4, pp. 451 –461.
  * Montemurro, M. A. and Zanette, D. H. (2002a). Entropic analysis of the role of words in literary texts, _Adv. Compl. Sys._ 5, 1, pp. 7–17.
  * Montemurro, M. A. and Zanette, D. H. (2002b). New perspectives on Zipf’s law: from single texts to large corpora, _Glottometrics_ 4, 1, pp. 86–98.
  * Montemurro, M. A. and Zanette, D. H. (2009). The statistics of meaning: Darwin, Gibbon and Moby Dick, _Significance_ 6, 4, pp. 165–169.
  * Montemurro, M. A. and Zanette, D. H. (2010). Towards the quantificantion of the semantic information encoded in written language, _Adv. Compl. Sys._ 13, 2, pp. 135–153.
  * Montemurro, M. A. and Zanette, D. H. (2011). Universal entropy of word ordering accross linguistic families, _PLoS ONE_ 6, 5, p. e19875.
  * Murray, J. D. (2002). _Mathematical Biology. An Introduction_ (Springer, New York).
  * Ortuño, M., Carpena, P., Bernaola Galván, P., Muñoz, E. and Somoza, A. M. (2002). Keyword detection in natural languages and DNA, _Europhys. Lett._ 57, 5, pp. 759–764.
  * Panaretos, J. (1989). On the evolution of surnames, _Int. Stat. Rev._ 57, 2, pp. 161–167.
  * Pareto, V. (1896). _Cours d’économie politique_ (F. Rouge, Lausanne).
  * Patel, A. D. (2008). _Music, Language, and the Brain_ (Oxford University, New York).
  * Peng, C.-K., Buldyrev, S. V., Goldberger, A. L., Havlin, S., Sciortino, F., Simons, M. and Stanley, H. E. (1992). Long-range correlations in nucleotide sequences, _Nature_ 356, 6365, pp. 168 –170.
  * Peng, C.-K., Buldyrev, S. V., Havlin, S., Simons, M., Stanley, H. E. and Goldberger, A. L. (1994). Mosaic organization of DNA nucleotides, _Phys. Rev. E_ 49, 2, pp. 1685 –1689.
  * Schenkel, A., Zhang, J. and Zhang, Y. (1993). Long-range correlations in human writings, _Fractals_ 1, 1, pp. 47 –57.
  * Schwartz, B. and Reisberg, D. (1991). _Learning and Memory_ (W. W. Norton and Co., New York).
  * Shannon, C. E. (1948a). A mathematical theory of communication, _Bell Syst. Tech. J._ 27, 3, pp. 379–423.
  * Shannon, C. E. (1948b). A mathematical theory of communication — Part III, _Bell Syst. Tech. J._ 27, 4, pp. 623–656.
  * Shannon, C. E. (1951). Prediction and entropy of printed English, _Bell Syst. Tech. J._ 30, 1, pp. 50–64.
  * Simon, H. A. (1955). On a class of skew distribution functions, _Biometrika_ 42, 3–4, pp. 425–440.
  * Simon, H. A. (1957). _Models of Man. Social and Rational_ (Wiley, New York).
  * Simon, H. A. (1961). Reply to Dr. Mandelbrot’s post scriptum, _Information and Control_ 4, 3, pp. 305–308.
  * Sornette, D. (1998). Multiplicative processes and power laws, _Phys. Rev. E_ 57, 4, pp. 4811–4813.
  * Sornette, D. (2000). _Critical Phenomena in Natural Sciences. Chaos, Fractals, Seforganization, and Disorder: Concepts and Tools_ (Springer, Berlin).
  * Stanley, H. E., Buldyrev, S. V., Goldberger, A. L., Goldberger, Z. D., Havlin, S., Mantegna, R. N., Ossadnik, S. M., Peng, C. K. and Simons, M. (1994). Statistical mechanics in biology: how ubiquitous are long-range correlations? _Physica A_ 205, 1–3, pp. 214–253.
  * Teahan, W. J. and Cleary, J. G. (1996). The entropy of English using PPM-based models, in _Proc. Data Compression Conference (DCC’96)_ (Snowbird, USA), pp. 53–62.
  * van Eemeren, F. H. (2001). _Crucial Concepts in Argumentation Theory_ (Univerity of Chicago, Chicago).
  * Voss, R. F. (1985). _Random fractal forgeries_ (Plenum, New York), pp. 1–11.
  * Willis, J. C. and Yule, G. U. (1922). Some statistics of evolution and geographical distribution in plants and animals, and their significance, _Nature_ 109, pp. 177–179.
  * Yule, G. U. (1925). A mathematical theory of evolution, based on the conclusions of Dr. J. C. Willis, _Phyl. Trans. R. Soc. London Ser. B_ 213, pp. 21–87.
  * Zanette, D. H. (2001). Self-similarity in the taxonomic classification of human languages, _Adv. Compl. Sys._ 4, 2–3, pp. 281–286.
  * Zanette, D. H. (2006). Zipf’s law and the creation of musical context, _Musicae Scientiae_ 10, pp. 3–18.
  * Zanette, D. H. (2008). Playing by numbers, _Nature_ 453, pp. 988–989.
  * Zanette, D. H. and Manrubia, S. C. (2007). _Multiplicative processes in social systems_ , _World Scientific Lecture Notes in Complex Systems_ , Vol. 7, chap. 6 (World Scientific, Singapore), pp. 129–158.
  * Zanette, D. H. and Montemurro, M. A. (2005). Dynamics of text generation with realistic Zipf’s distribution, _J. Quant. Linguistics_ 12, 1, pp. 29–40.
  * Zhou, H. and Slater, G. W. (2003). A metric to search for relevant words, _Physica A_ 329, 1–2, pp. 309 –327.
  * Zipf, G. K. (1936). _The Psycho-Biology of Language. An Introduction to Dynamic Philology_ (Routledge, London).
  * Zipf, G. K. (1949). _Human Behaviour and the Principle of Least Effort. An Introduction to Human Ecology_ (Addison–Wesley, Cambridge).
  * Ziv, J. and Lempel, A. (1977). Universal algorithm for sequential data compression, _IEEE Trans. Inf. Theor._ 23, 4, pp. 337–343.