J. theor. Biol. (2000) 205, 147}159
doi:10.1006/jtbi.2000.2053, available online at http://www.idealibrary.com on

Language Evolution and Information Theory
JOSHUA B. PLOTKIN* AND MARTIN A. NOWAKInstitut for Advanced Study, Princeton, NJ 08540, ;.S.A.
(Received on 21 October 1999, Accepted in revised form 24 March 2000)

This paper places models of language evolution within the framework of information theory.
We study how signals become associated with meaning. If there is a probability of mistaking
signals for each other, then evolution leads to an error limit: increasing the number of signals
does not increase the "tness of a language beyond a certain limit. This error limit can beovercome by word formation: a linear increase of the word length leads to an exponential
increase of the maximum "tness. We develop a general model of word formation anddemonstrate the connection between the error limit and Shannon's noisy coding theorem.
 2000 Academic Press

1. Introduction
If we want to understand the evolution ofprimitive communication, then we should "rstconsider how signals acquire speci"c meanings.
In other words, we should explore how evolution
can lead to an association between signals andobjects of the world. Here &&object'' is used ina very broad sense to include everything which
can be referred to.
In previous papers, we have used evolutionary
game theory to study this question (Nowak& Krakauer, 1999; Nowak et al., 1999a). We haveassumed that communication is of bene"t to bothspeaker and listener. Correct communication
leads to a payo!. Each individual is characterizedby two matrices. The active matrix contains theprobabilities that a speaker will use a certain
signal when attempting to communicate abouta certain object. The passive matrix contains theprobabilities that a listener will associate a speci-*Author to whom correspondence should be addressed.
E-mail: plotkin@ias.edu0022}5193/00/130147#13 $35.00/0"c signal with a speci"c object. If there is a possibility of mistaking signals for each other then we
obtain an error limit. Using more and more signals cannot increase the "tness of a language
beyond a certain limit. In other words, natural
selection will design a communication systemthat has only a small number of signals referring
to a few important concepts. It seems that this is
the case for animal communication, while humanlanguage is (almost) unlimited.
The mechanism that can overcome the error
limit is word formation. We "nd that linearly
increasing word length can lead to exponentially
increasing maximum "tness (Nowak et al.,1999b). The evolution of word formation is atransition from an analog to a digital communication system. All human languages use a limited number of phonemes to generate a large
number of words. Moreover, word formation
is probably unique to human communication(Pinker, 1995; Miller, 1991). Bird song is certainly
combinatorial as well, but the interpretationof bird song is most likely not combinatorial(Marler, 1970; Hauser, 1996).
 2000 Academic Press

148

J. B. PLOTKIN AND M. A. NOWAKAn important feature which has been missing
from previous investigations is the connection
between language evolution and information theory as conceived by Shannon & Weaver (1949).
We build this bridge in the present paper. We willdevelop a more realistic model of word formationand discuss how the payo! in our evolutionary
language game is related to Shannon's error
probability and to the capacity of a channel.
Speci"cally, we show the relationship between
Shannon's noisy coding theorem and our "ndingthat word formation can overcome the error
limit.
Information theory is a mathematical discipline devoted to a precise de"nition and understanding of &&information'' in the vernacularsense. Following the seminal works of Shannon,
information theorists have used notions fromprobability theory to de"ne uncertainty and information. Information theory addresses suchquestions as the maximum rate at which information can be transfered over a noisy (or imperfect)channel. In particular, a coding system (e.g. repeating each message "ve times) may be used toincrease the "delity of a noisy channel. Shannon's
noisy coding theorem quanti"es the bene"ts
which coding systems may confer on an otherwise noisy communication channel.
Although information theory has been widely
applied in today's &&information age'', it has
seldom been used*nor was it conceived*in thesetting of language evolution. Despite this fact,
we shall see that Shannon's formalism provides
an excellent framework for considering language
evolution, and especially word formation. In fact,
when properly placed in this framework, the theory of language evolution should bene"t from theinsights of information theorists over the past 50
years.
This paper contains seven sections. In Section
2, we will outline the basic model of language
evolution. In Section 3, we present a new approach for describing word formation. In Section
4, some basic concepts of information theory are
discussed. In Section 5, we compare these concepts of information theory, in particular Shannon's noisy coding theorem, with our model ofword formation. In Section 6, we present a speci"c example of a very simple communication
system and analyse it from the perspective of

language evolution and information theory.
Section 7 is a short conclusion.
2. Evolving Arbitrary Signals
Consider a population of individuals who cancommunicate via signals. Signals may include
gestures, facial expressions, or spoken sounds.
We are interested how an arbitrary association
between signals and &&objects'' can evolve.
In the most simple model, each individual isdescribed by an active matrix, P, and a passive
matrix Q (Hurford et al., 1998). The entry
P denotes that the probability that the indiGH
vidual, as a speaker, will refer to object i by using
signal j. The entry Q denotes the probability
HG
that the individual, as a listener, will interpretsignal j as referring to object i. Both P and Q are
stochastic matrices; their entries lie in [0, 1], andtheir rows each sum to one. The &&language'' of anindividual, ¸"(P, Q), is de"ned by these two
matrices.
When one individual using ¸"(P, Q) communicates with another individual using ¸"(P, Q), we de"ne the payo! as the number ofobjects communicable between the individuals,
weighted by their probability of correct communication. Thus, the payo! of ¸ vs. ¸ is given by
1 L K
P Q #P Q .
F(¸, ¸)"
GH HG
GH HG
2
G H
There are n objects and m signals. Loosely speaking, this payo! function re#ects the total amountof information that ¸ can convey to ¸, and viceversa. In this basic model, any possible miscommunication results from a discrepancy between
the signal}object associations of the speaker andthe listener. The maximum possible payo! to two
individuals who share a common language is thesmaller of n or m.
2.1. TRANSMISSION ERROR

Miscommunication can arise from errors that
occur during the transmission of a signal. Such&&transmission errors'' can be described by a signal-error matrix ;. The entry ; denotes theGHprobability that, when a speaker sends signal i,the listener receives signal j. In this setting,LANGUAGE EVOLUTION AND INFORMATION THEORY

assuming that two individuals share a common
language ¸"(P, Q), the payo! is de"ned by
L K K
F(¸, ¸)"
P ; Q .
GH HI IGG H I

(1)

Again, this payo! function re#ects the sum of theinformation content which a speaker can convey
accurately to a listener and vice versa.
2.2. THE ERROR LIMIT

Let us now calculate the maximum payo! thata language, ¸, can achieve. Suppose n"m. The
maximum payo! will be obtained if P and Q are
identical permutation matrices. (A permutation
matrix has a single 1 entry per row and column,
all other entries being 0.) Without loss of generality, we set P "Q "1 for all i, and P "Q "0
GG
GG
GH
HG
for all iOj. In this case, we obtain the payo!
functionL
F(¸, ¸)"; .
III
The signal-error matrix, ;, can be constructed
to re#ect the similarities of the signals. In particular, we denote the similarity between signal i andsignal j by s . We stipulate that s "1 andGHGGs )1. The probability of mistaking signal i forGHsignal j quanti"es how similar signal i is to j compared with all other signals: u "s / L s . InGH
GH I GI
these terms, the "tness of a common language
can be expressed as
1L
F(¸, ¸)".
L s
G I GI
We imagine that the signals of the language areembedded in some pre-compact metric space, X,
and that d denotes the distance between signals
GHi and j. The similarity between two signals, then,is a decreasing function of the distance s "f (d ).
GHGH
It can be shown that in this situation the "tness isalways bounded by some constant depending
only on X and f, but not on n (Dress & Nowak,2000). In other words, even as the signal repertoire of a language increases, the "tness cannot
exceed a "xed value.

149

3. Word Formation
In Nowak et al. (1999b), we demonstrated thatword formation can overcome the constraint of
the error limit. We considered languages whosebasic signals consist of m phonemes. The words ofthe language were all assumed to be l-phonemes
long. For simplicity, we also assumed that a language includes all possible mJ words in its lexicon.
The similarity between words a and b was de"ned by the product of the similarity of theirphonemes. In other words,
J
S(a, b)"  s I I ,? @I
where aI denotes the k-th phoneme of word a.
Using this de"nition, we showed that the maximum"tness of the language increases exponentiallywith word length l. In this sense, word formation
allows the language to overcome the error limit.
We now develop a more general framework forword-based language. A language will be described by four components: a lexicon, an active
matrix P, a passive matrix Q, and a phoneme
error-matrix <.
As before, our model is based upon words
which are l-phonemes long. The lexicon of thelanguage, however, does not necessarily include
all possible mJ words. Instead, the lexicon contains a subset of all possible words. Speci"cally,
let us denote the phonemes of the language by theset U"+ , 2 , ,. We denote the lexicon byKsome subset CLUJ. We refer to the words in
C as the lexicon or proper vocabulary of the language. Let us denote the size of the lexicon by
n"" C " (i.e. n is the cardinality of the set C).
Notice that n also denotes the number of objects
expressible in the language.
The active matrix P de"nes the (probabilistic)
association between objects and words for the
speaker. P is now an n;mJ stochastic matrix
whose ij-th entry denotes the probability thata speaker will attempt to use word j to denoteobject i. By de"nition, non-zero entries in P may
occur only at columns corresponding to words inthe lexicon C.
The passive matrix Q maps all possible
perceived words (probabilistically) back into then objects. We specify the passive matrix via

150

J. B. PLOTKIN AND M. A. NOWAKa stochastic mJ;n matrix Q. The entry Q represHG
ents the probability that a listener who perceives
the j-th word will interpret it as the i-th object.
Finally, we must provide a description oftransmission errors. As before, we use an mJ;mJ
word error-matrix ;. The entry ; denotes theGHprobability that, when a speaker attempts to vocalize the i-th word, the listener perceives the j-thword. Notice that only the rows of ; corresponding to lexicon words matter; we have assumed
that a speaker will never attempt to vocalize an
improper vocabulary word (although a speaker
may, in fact, utter a word outside of the lexicon
via a transmission error).
In strict analogy with previous models, the ;matrix is built upon the similarity between thephonemes of which the words are comprised. In
particular, we start with a stochastic m;m phoneme error-matrix <. The entry < denote theGHprobability that, when a speaker attempts to vocalize the i-th phoneme, the listener hears the j-thphoneme. Therefore, as before, for words a and b,
we have the following expression for the word
error-matrix (notice that, since < is stochastic,; is as well):J; "  < I I .
?@
? @
I
Thus, a language ¸ is described completely by
the three matrices ¸"(P, Q, <). The matrix ; isderived from <, and C is determined by thosecolumns of P-containing non-zero entries. Finally, we stipulate that all individuals in a population share the same <-matrix. In other words,
all individuals use the same phonemic alphabet,
and they share the same imperfections in their
vocal and auditory organs.
In this setting, the proper payo! function (instrict analogy with previous models) is given by
the sum of the number of objects which speaker¸ can convey to speaker ¸, weighted by theprobability of communicating the objects correctly. In other words, letting w denote the i-thG
object, we de"neL
P ; Q
F(¸, ¸)"UG ? ?@ @UG
a3U J b 3U J
G
L
J
"
P
Q
 < I I .
UG ? b 3U J @UG? @G a3UJI

(2)

We now ask what is the maximum possible"tness a language can obtain. Of course, themaximum is obtained when the speaker and listener share a common language given by binary
active and passive matrices. But we do not yet
know, given P and <, what is the optimal listening matrix Q.
Moreover, there remains another issue to beaddressed: is it possible, by increasing the word
length l, to increase a language's payo! withoutbound? In light of the error limit, this inquiry
addresses a fundamental question regarding theadaptive bene"ts of word formation.
In order to answer these questions, we will "rsttake a detour into the information theory of
Shannon. We will use Shannon's classical theorem on noisy communication to show that word
formation does, indeed, remove the error limit
which constrains strictly phonemic communication. In fact, as we shall see, word formation
provides an exponential increase in "tness withword length l. This result places our evolutionary
theory of language within the larger frameworkof information theory.
4. Shannon:s Information Theory
We will outline some of the primary components of Shannon's theory as needed for our
purposes. For a detailed accounts of information
theory, we refer to Welsh (1988) and van derLubbe (1988).
4.1. THE NOISY CHANNEL

Shannon considers a discrete memorylesssource I which emits characters from an alphabet
U"+ , 2 , , according to some discreteK
probability distribution. Most often, Shannon
considers the special case of a binary alphabet,but his noisy coding theorem applies to arbitraryalphabets as well. The discrete source I is linked
to a noisy channel used to transmit information.
The channel is summarized by a channel matrix<. The entry < gives the conditional probabilityGH
Pr( received " sent).
H
G
Given a channel < and an input source, we
obtain a natural output stream. In this situation,
Shannon introduces the notion of the capacityof <. The capacity C(<)3[0, 1] measures the

LANGUAGE EVOLUTION AND INFORMATION THEORY

maximum rate at which information about an
input stream may be inferred by inspecting theoutput stream. (A more precise de"nition will begiven in Section 6.) Given a channel < with capacity C(<), Shannon asks how one can improve thereliability of the communication system by constructing codes while simultaneously keeping therequired number of transmissions small.
4.2. ENCODING AND DECODING

In order to increase "delity, Shannon de"nesa set of n codewords, C, each codeword beinga string of l characters from U. The encoder takes
input messages from the source I, encodes theinformation into codewords, and sends the codeword on to the noisy channel, letter by letter.
Shannon also requires the speci"cation of a deterministic decoder. The decoder is a map from all
possible outputs (from the noisy channel) back to
C. In other words, the decoder is a partition of UJ
into n disjoint subsets. (Of course, any good decoder will certainly include each codeword
w within the subset of UJ which is decoded as w.)
Shannon de"nes the error probability of thiscommunication system (Fig. 1) as
1 L
Pr(error in communication "
e(C)"
n
G
codeword w is transmitted).
G
Thus, the error probability measures the average
number of mis-interpreted codewords, assuming
codewords are transmitted with equal probabilities. Clearly, one would like to construct codes151

with error probability as small as possible. This isprecisely the problem which Shannon's fundamental theorem addresses.
4.3. THE NOISY CODING THEOREM

In this situation, Shannon's noisy coding
theorem states the following:
Theorem 4.1 (Shannon, 1948). If a discrete memoryless channel < has capacity C'0 and R is any
positive quantity with R(C, then there exists
a sequence of codes (C " 1)n(R) such that
L(a) C has 2 WRnX codewords of length l"n,L(b) the error probability satis,es e(C ))Ae\ L,
Lwhere the constants A and B depend only on thechannel < and on R.
In other words, Shannon's theorem provides
a sequence of communication systems with linearly increasing codeword length, exponentially
increasing number of codewords (and thus describable objects), and exponentially decreasing
error probability. [For a proof of Shannon's theorem, we refer the reader to Gallager (1968). In
essence, Shannon constructs each successive code
C by choosing random codewords and decodingL
via the maximum likelihood method.]
Shannon's coding theorem provides us withexponentially good codes. There is, however, an
important converse to this theorem. The converse tells us that we could hope for nothing
better. Speci"cally, we have the following result.
Theorem 4.2 (Wolfowitz, 1961). For a discrete
memoryless channel of capacity C and for any
R'C, there cannot exist a sequence of codes C
Lsuch that C has 20L codewords of length n andLerror probability tending to zero. In fact, sucha sequence of codes must have error probability
which approaches 1 as nPR.
5. Information Theory and Word-based
Language

FIG. 1. Schematic diagram of Shannon's communication
system. A source emits messages which are encoded into
codewords, transmitted over a noisy channel, and thendecoded.

In this section, we reinterpret Shannon's communication system and the noisy coding theorem
in terms of our language model.
In order to relate Shannon's theory to ourlanguage model, we make two trivial remarks.

152

J. B. PLOTKIN AND M. A. NOWAK

Notice "rst that a Shannon-encoder may be expressed as a binary n;mJ matrix P whose rows
sum to one. The entry P indicates whether orGH
not the encoder uses word j to denote object(or message) i. Similarly the decoder may be
expressed as a binary mJ;n matrix Q. The entry
Q denotes whether or not the j-th word is inHG
cluded in the subset words decoded as the i-th
codeword (or i-th message).
In this setting, Shannon's codeword communication through a noisy channel is easily seen to beequivalent to our model for language. Shannon'salphabet U plays the role of the phonemes, theencoder plays the role of the active matrix, and thedecoder the passive matrix. Shannon's &&codewords'' are simply strings of phonemes. Similarly,
the noisy channel < plays the role of the phoneme
error matrix. Shannon's communication system isalways deterministic; however, it requires that thematrices P and Q are binary. Notice that, when
P is binary, there is an unambiguous one-to-one
correspondence between lexicon words and objects. In this situation, the &&objects'' expressible inour original language model may be identi"edwith Shannon's codewords.
In light of the equivalence of these two systems,
it is important to relate the information-theoreticde"nition of error probability*whose behavior isdescribed by Shannon's theorem and its converse*with our de"nition of language "tness. Such a relation will allow us to use Theorem 4.1 to derive theThus, Shannon's theorem (together with its converse) reveals the maximal properties of FI (C).
We will show that FI (C) is equivalent to the"tness of language in our evolutionary model.
Thus, we claim
FI (C)"F(¸, ¸).
The proof of this statement is little more than an
exercise in unraveling de"nitions. We start withthe de"nition of FI :FI (C)"n[1!e(C)]

1 L
Pr(communication error "
"n 1!
n
G



w transmitted)
GL"n! (1!Pr(no communication error "Gw transmitted))GL" Pr(no communication error "Gw transmitted).
G
Recall that in Shannon's codeword system,
P and Q are binary matrices whose rows sum to
1. Therefore, given w3C, P "1 only whenU?
a"w. Thus, we may rewrite the last equality
above as follows:L
FI (C)"P Pr(no communication error " a transmitted).
UG ?
G a3U J
maximal "tness of our word-based model.
Towards this end, consider the information-theoretic expression FI (C)""C "(1!e(C))"n(1!e(C)).
By Shannon's theorem, given a channel < with
non-zero capacity, we can "nd a sequence ofcodes C with linearly increasing codeword
Llength and with exponentially increasing FI (C).

In order to calculate the probability of correctcommunication when a is transmitted, we consider all possible outputs b from the noisy channel, weighted by their respective probabilities.
For each output b, correct communication occurs only if b is decoded as codeword w . Thus,G
we derive the equations

L
FI (C)"P
Pr(b received " a transmitted)Pr(b is decoded as codeword w )UG ? b3UJ
G
a3U J
G
L
P
Pr(b received " a transmitted)Q .
"UG ? b3UJ
@UG
a3U J
G

153

LANGUAGE EVOLUTION AND INFORMATION THEORY

Finally, we must calculate the probability that,upon input a into the noisy channel, we receive
output b. The noisy channel produces its output
phoneme-by-phoneme (or &&letter by letter'').
Therefore, the probability we want equals the
product of the probabilities that each phoneme ofa will be transmitted as the respective phoneme ofb. Such quantities are given by the channel
matrix <. Thus, we see that

ministic, and they are not necessarily shared by the
speaker and listener. This generality allows us toview language in an evolutionary context, as weshall explore in the following extended example.
6. A Speci5c Example
In order to illustrate our somewhat abstract
model of language*as well as its relationship to
information theory*we now present a speci"cexample. Let us assume that the individuals ina population all speak the same language. In thissection, we will step through a complete speci"cation of the language ¸ and eventually calculateF(¸, ¸). Then, we will reconsider the example inlight of information theory and Theorem 5.1.

J
LP
Q  < I I .
FI (C)"? @UG ? b3UJ @UG
IG a3UJ
But this last formula coincides with our expression for the language "tness F(¸, ¸), de"ned in
eqn (2). Hence, we have shown FI (C)"F(¸, ¸).
Therefore, if all the individuals in a population
use the same language, and if that language has
binary P- and Q matrices, then the "tness F(¸, ¸)agrees with the information-theoretic quantity
FI (C). As a consequence, Shannon's coding theorem implies the following result.

6.1. THE PHONEMES

We "rst stipulate that the organisms in the
population are all limited, by their similar vocal
and auditory organs, to the use of three phonemes. We denote these phonemes by a, m and p.
Therefore, U"+a, m, p, and m"3. We also assume the population uses a language with word
length l"2. Therefore, the possible words which
an individual can utter are UJ"+aa, am, ap, ma,
mm, mp, pa, pm, pp,. Nevertheless, the population chooses only to describe three objects: father, mother and food. Hence, the population
uses a lexicon of n"3 proper vocabulary words.
Speci"cally, we stipulate that the population uses
the lexicon C"+pa, ma, mm,LUJ.

Theorem 5.1 (word formation). Given a phoneme
error-matrix < (with non-zero capacity), there exists
a sequence of languages ¸ with linearly increasingL
word length and exponentially increasing ,tness.
Thus, word formation overcomes the error
limit which constraints strictly phonemic communication; increasing word length can increase"tness without bound. This result highlights theimportance of word formation, which is more orless unique to the human species.
Note that this result is not limited by the restriction to binary active and passive matrices; asis usual in linear programming, we know a priorithat a maximally "t language must use binary
matrices.
As we have seen, information theory helps toanswer fundamental questions about our model ofword-based language. In one sense, however, ourmodel is more general than Shannon's communication system; P and Q are not necessarily deter-P "6.2. THE ACTIVE MATRIXNext we describe the active matrix, P, of thecommon language. We assume that, generally
speaking, a speaker attempts to use pa to convey
father, ma to convey mother and mm toconvey food. Nevertheless, the speaker does nothave a deterministic (binary) active matrix. Instead, there is always a slight probability that the
speaker will try to describe an object with the&&wrong'' vocabulary word. This leads to the following expression for the P-matrix:

aa am ap

ma

mm

mp

pa

pm pp

Mother

0

0

0

1!2e

e

0

e

0

0

Food

0

0

0

e

1!2e

0

e

0

0

Father

0

0

0

e

e

0

1!2e

0

0

.

154

J. B. PLOTKIN AND M. A. NOWAK

Notice that the columns of P with non-zero
entries correspond to proper vocabulary words.
In other words, when a speaker wants to communicate food, there is no chance that he willattempt to use a word outside of his language's
lexicon. The active matrix represents the
speaker's association between objects and proper
vocabulary words.

calculations employ the precise parameter values.)

6.3. THE TRANSMISSION ERROR MATRICES

As in Section 3, we use the similarity between
phonemes to de"ne the phoneme error matrix< "s / K s . For example, <a,a+1/(1#0.08
GH
GH I GI#0.02)"0.90. This leads to the following
stochastic phoneme error matrix <:sa,a"sm,m"sp, p"1,sa,m"sm,a+0.08,
sa, p"sp,a+0.02,
sm,p"sp,m+0.29.

Despite the form of the active matrix, there isalways a chance that when trying to communicate an object, the perceived output will not fall in
the lexicon. This phenomenon arises from errors
in vocalizing the intended word or hearing theoutput correctly. Such a phenomenon is a transmission error, as opposed to a interpretation error, and it is quanti"ed by the word error-matrix;.
In order to specify ;, we must "rst de"ne thephoneme error-matrix <. For illustrative purposes we derive < (and thus eventually ;) byusing the notion of phoneme similarity. We embed our phonemes into the compact metric space
X"[0, 1], and we de"ne their pairwise similarity as a declining function f of their pairwise
distances.
In particular let us embed UP[0, 1] by placing p at 0, m at 1/4, and a at 3/4. We have chosen
this particular embedding for purely illustrative
purposes; there has been no attempt to re#ect theactual phonetics of m, p, and a in the English
language (Fig. 2).
We de"ne phoneme similarity via a simple,
exponentially decreasing function of distance:s "f (d )"e\BGH. For example, sa,m" e\Ba,m"GH
GHe\ " \ ""e\+0.082. Similarly, sa,a"e\Ba,a "e"1. This leads us to the following
values for phoneme similarity. (For ease of presentation, we henceforth round all reported values
to two decimal places. Nevertheless, all of our

aa
ma

am

ap

a

m

a

0.90 0.07 0.02

< " m

0.06 0.73 0.21 .

p

0.02 0.22 0.76

(Notice that, if a row of a stochastic matrix appears not to sum to one, this is only an artifact ofour two-decimal presentation.)
Although the matrix above is stochastic, it is
not symmetric. For example, given < above, it ismore likely to mis-speak or mis-hear the phoneme p as m than it is to slip from m to p. Upona moment's re#ection, this situation is realistic;
certain phonemes lend themselves more easily totransmission error into others than vice versa.
Using the < matrix, we can derive the corresponding word-error matrix ;. For each pair ofwords we compare constitutive phonemes inturn. For example, ;ma, aa"<m,a <a,a+0.06 )0.90"0.05. Of course, the only rows of ; whichmatter correspond to words with positive probability in P*i.e. to the lexicon words. Thus, weonly report such rows below. This leads to thefollowing ; matrix:

ma

mm mp

pa

pm

pp

0.05 0.00 0.00 0.66

0.05 0.02 0.19 0.02 0.00

; " mm 0.00 0.04 0.01 0.04

0.53 0.15 0.01 0.15 0.04 .

pa

p0.02 0.00 0.00 0.20

0.02 0.00 0.69 0.06 0.02

155

LANGUAGE EVOLUTION AND INFORMATION THEORY
6.5. THE PAYOFF

Since the language ¸"(P, Q, <) has now been
completely speci"ed, we may calculate its payo!
via eqn (2):
FIG. 2. Schematic diagram of the embedding of phonemes U"+a, m, p, into the metric space X"[0, 1]. Onceembedded, phoneme similarity is de"ned by a decreasing
function of distance.

"

6.4. THE PASSIVE MATRIX

a3U J

Finally, we must specify the passive matrix Q.
This matrix provides, for each possible perceived
output word, the probability of interpreting thatword as each respective object. For example,
Qaa, mother denotes the probability of interpreting
perceived output word aa as the object mother.
Given P and ;, what is a reasonable choice oflistening matrix Q?
We will soon derive the optimal, deterministic
choice of Q. For now, however, we follow a reasonable rule of interpretation: a listener shouldinterpret perceived output word a as object i witha probability which equals the probability that,when trying to communicate object i, the perceived output would be a. In other words, we set
Q "Pr(output a " i transmitted). For example,?G
we set Qaa, mother equal to the chance of producing
output aa when trying to communicate mother.
In particular, this probability is given by(1!2e);ma,aa#e;mm,aa#e;pa,aa+0.05(1!2e)#0.00e#0.02e+0.05!0.09e. Following thisrule alone, however, the rows of the resulting
Q matrix do not necessarily sum to one. Thus, wenormalize each row to derive the following, nondeterministic Q-matrix:
Mother
aa

Food

L
P
Q ;
F(¸, ¸)"U ? b3U J @UG ?@
a3U J
G
Pmother,a

#
a3U J

#
a3U J

b3U J

Pfood,aQb, mother ;
?@

b3U J

Pfather,aQb, food ;
?@

b3U J

Qb, father ;?@+1.96!5.79e#8.68e.
Having derived an expression for the "tness of
the language ¸, we may now inspect its properties. The only free parameter is e, which isa measure of interpretive error. (By completely
specifying <, on the other hand, we have "xed theamount of transmission error.) We may only
allow e to vary in [0, 0.5] so that P remain
a stochastic matrix. Figure 3 shows the graph ofF(¸, ¸) for this range of e values.
As expected, the maximum "tness occurs whene equals zero*i.e. when there are no errors ininterpretation. In general, as we usually "nd in
linear programming problems, the maximal "tness always occurs when P and Q are binary,

Father

0.73!1.2e 0.05#0.85e 0.22#0.34e

am 0.09#0.73e 0.89!1.65e 0.03#0.92e
ap

0.09#0.73e 0.88!1.65e 0.03#0.92e

ma

0.73!1.2e 0.05#0.85e 0.22#0.34e

Q"mm 0.09#0.73e 0.88!1.65e 0.03#0.92e
mp 0.09#0.73e 0.88!1.65e 0.03#092e
pa

0.21#0.36e 0.01#0.96e

0.77!1.3e

pm 0.07#0.79e 0.68!1.04e 0.25#0.25e
pp

0.07#0.79e 0.68!1.04e 0.25#0.25e.
(3)

FIG. 3. Graph of the language "tness F(¸, ¸) obtained asa function of e. The parameter e measures the amount ofinterpretive error in the language. The "tness of the language ¸ is maximized when there is no chance for misinterpretation (e"0).

156

J. B. PLOTKIN AND M. A. NOWAK

deterministic matrices. Also notice that theminimum "tness occurs when e"1/3; in thissituation each speaker has an indiscriminate
association between objects and lexicon words.
6.6. IN THE CONTEXT OF INFORMATION THEORY

We now reconsider the example in the context
of information theory. The phoneme errormatrix < now plays the role of the channel
matrix. Similarly, we use the original lexicon as
the code-words. The encoder and decoder, however, must now be binary. Therefore, in a strict,information theoretic context, we must takee"0. In this context, we should also use deterministic, maximum likelihood decoding, as in the
proof of Shannon's theorem. Speci"cally, Q must
decode an output word a as that particularcodeword i which maximizes the conditional
probability Pr(output a " i transmitted). Recall
that in eqn (3) we de"ned Q "Pr(output a " i?Gtransmitted), and normalized each row. Therefore, the maximum likelihood decoder simply
replaces each row of the non-deterministic Q withzeroes, except for the largest entry in the row.
More explicitly, for each a3UJ, the deterministic,
maximum-likelihood decoder Q+* satis"es
Q+*"
?G





"

1 when a maximizes
Pr(output a " i transmitted)
0 otherwise.

(Notice, for example, that mp is decodeda food (mm) as opposed to mother (ma). This
makes sense given that p is phonetically closer tom than to a.)
When e"0 and when we use maximum-likelihood decoding, we calculate that F(¸, ¸)+2.35.
This maximum "tness is signi"cantly larger than
1.96, which was the "tness obtained via the nondeterministic encoder of eqn (3). In fact, as e varies, we can evaluate the "tnesses obtained via themaximum-likelihood vs. the non-deterministic
encoders. A graph of these "tnesses is shown in
Fig. 4.
Notice that it is always better (except whene"1/3) to use the Shannon-type decoder Q+*
than the non-deterministic matrix de"ned in
eqn (3). This is a graphic illustration of the optimality ensured by Shannon's theorem.
6.7. THE CAPACITY CALCULATIONIn this section, we compute the capacity of
the 3;3 phoneme error-matrix <. Recall that
Shannon's theorem only applies to channels with
C(<)'0.
First, we must state the precise de"nition of
capacity. Given a channel < and an input-source
I, we obtain a natural output stream J. The
capacity of the channel < is de"ned by
C(<)"sup [H(I)#H(J)!H(I, J)],

1 when a maximizes

b3UJ

I

P ;
G@ @?

0 otherwise.
In our particular example, when e"0 we havethe following maximum-likelihood decoder Q+*:
Mother Food Father

Q+* "

aa

1

0

0

am

0

1

0

ap

0

1

0

ma

1

0

0 .

mm

0

1

0

mp

0

1

0

pa

0

0

1

pm

0

1

0

pp

0

1

0

(4)
FIG. 4. Graph of the language "tness F(¸, ¸) obtained
via the non-deterministic decoder Q as opposed to the deterministic, maximum-likelihood decoder Q+*. A language isalways better served by the maximum-likelihood decoder.
Thus, we expect that languages should evolve towards maximum-likelihood decoding. ( - - - - ) Shannon decoder (Q+*);(**) non-deterministic decoder (Q).

157

LANGUAGE EVOLUTION AND INFORMATION THEORY

where H denotes the entropy of a source. The
entropy of a discrete source I with probability
distribution (p , 2 , p ) is de"ned as H(I)"K! K p log(p ). See Welsh (1988) for a descripGGG
tion of entropy.
In our particular example, a source I is determined by a discrete probability distribution(x, y, z), x#y#z"1, where x denotes the probability that the source will emit letter a, y denotes
the probability for m, and z for p. The output
stream J is calculated as follows; the probabilityof an a is x< #y< #z< , and similarly for
the other two letters. The stream (I, J) has ninepossible &&letters'': a followed by a, a followed bym, etc. These probabilities are given by x< ,
x< , etc.
Once the probability distributions for I, J,
and (I, J) have been expressed in terms of(x, y, z), we must maximize the function
H(I)#H(J)!H(I, J) over all input distributions for I. This maximization amounts tonothing more than a straightforward calculus
problem via Lagrange multipliers. The resulting
answer is given by
C(<)+0.7988,
which is obtained when (x, y, z)+(0.43, 0.19,0.38).
Thus, since C(<)'0, Shannon's theorem indeed applies to our explicit example. In particular, Shannon's theorem guarantees a sequenceof languages ¸ , n"1, 2, 3,2, each with a
LXwords of length l"n, with
lexicon of 2W L
exponentially increasing "tnesses.
6.8. EVOLUTION TOWARDS DETERMINISM

We can use evolutionary dynamics to test if thelanguage will evolve toward deterministic passive
matrices, as information theory predicts.
We ran a simple computer simulation to test
whether, when < and P are "xed, Q will evolve
towards Q+*, the deterministic, maximum-likelihood decoder. In particular, referring to our explicit example, we "x e"0 and specify P and< as above. We choose a population of 50
asexual, semelperous individuals. In the "rstgeneration, each individual starts with thenon-deterministic Q-matrix from eqn (3). In eachsuccessive generation, we calculate the payo!
obtained by each individual communicating withevery other one. Each individual then produces
progeny (each progeny with the same Q-matrix as
the parent) in proportion to its total payo! relative to the other individual's payo!s. We normalized so that there are 50 o!spring, and thus 50
individuals, in every generation. At each generation and for each o!spring, we stipulate a 0.4%
chance that the o!spring will be a &&mutant''.
A mutant o!spring possesses the same Q-matrix
as its parent, but with each entry perturbed bya random value in [!0.212, 0.212]. (By normalizing, we ensure that a mutant's resulting Q-matrix
has nonnegative values with rows summing toone.)
The result of this evolutionary simulation
is summarized in Fig. 5. We have graphed
the average payo! in the population at eachof 5000 generations. The average payo! starts
at 1.96, as derived in Section 6.5. Notice thatthe average payo! increases over time,
approaching the Shannon-limit of 2.35, derived
in Section 6.6.
We also report a typical Q-matrix found in the
population after 5000 generations. This Q-matrix
compares favorably with the matrix Q+* of
eqn (4):
Mother Food Father
aa

1

0

0

am

0.19

0.81

0

ap

0.08

0.92

0

ma

0.99

0

0.01

Q
" mm


0

1

0 .

mp

0.09

0.91

0

pa

0

0

1

pm

0.13

0.77

0

pp

0

0.99

0.01

As this simulation reveals, although the evolutionary dynamics of word-based language are158

J. B. PLOTKIN AND M. A. NOWAK

FIG. 5. Graph of the average payo! in a population ofindividuals during the course of simulated language evolution. The population begins with non-deterministic decoding and evolves towards maximum-likelihood decoding.
This evolution towards determinism is re#ected by the average payo! of the population, which ascends towards the
Shannon limit of 2.35. Thus, the long-term, complex dynamics of language evolution are predicted by information
theory. ( - - - - ) Shannon limit; (**) simulation.

complicated and noisy, we can still understandtheir long-term behavior via the bounds imposedby information theory.
7. Conclusions
We have compared models of language evolution with concepts from information theory. In
particular, there is a connection between Shannon's noisy coding theorem and our results onword formation. Shannon's theorem states that,for a given noisy channel, there exists a sequenceof codes with linearly increasing codeword
length such that the probability of transmission error decreases exponentially. Our
result on word formation states that, for a given
phonemic error matrix, the maximum "tness ofa language increases exponentially with word
length. We demonstrated that Shannon's error
probability is inversely proportional to our "tness function. Hence, the equivalence becomes
obvious.
Although the maximum "tness of a language
increases with word length, evolution will notlead to a run-away sequence of languages withlonger and longer words. Clearly, there are natural restraints on this tendency: as word length
increases, memorization di$culties increase andthe rate of communication decreases.
Shannon's theory requires a deterministic encoder and decoder (equivalent to binary P and

Q matrices in our notation). Any errors thus
result from noisy transmission, which is equivalent in our terms to acoustic errors during communication: the sender emits signal A, but thereceiver hears signal B. We believe that word
formation was the crucial evolutionary invention
to overcome this kind of transmission error.
Instead of increasing the number of phonemes
in a language, our ancestors invented a combinatorial signaling system. In this sense, word
formation compensates for errors in signaltransmission.
There are, however, other kinds of errors
which are not captured by Shannon's basicmodel. These are coordination errors between
the implementation of a signal by the sender andthe interpretation of a signal by the receiver. We
believe that these errors cannot be overcome byword formation per se, but that they instead
require a sophisticated organization of the mental lexicon and, importantly, the invention ofsyntax. As the size of the mental lexicon reaches
some memory capacity it becomes feasible torepresent every message by an individual word.
Instead, sentences comprised of individual words
are required. Hence, there should be an error
limit for words which is overcome by the useof sentences. This topic*the evolution of syntax*requires further investigation (Nowak et al.,2000).

REFERENCES
DRESS, A. & NOWAK, M. A. (2000) (in preparation).
GALLAGER, R. G. (1968). Information ¹heory and Reliable
Communication. New York: Wiley.
HAUSER, M. (1996). ¹he Evolution of Communication. Cambridge, MA: MIT Press.
HOFBAUER, J. & SIGMUND, K. (1998). Evolutionary Gamesand Population Dynamics. Cambridge: Cambridge University Press.
HURFORD, J., STUDDERT-KENNEDY, M. & KNIGHT, C.
(1998). Approaches to the Evolution of ¸anguage. Cambridge: Cambridge University Press.
MARLER, P. (1970). Birdsong and speech development:
could there be parallels? Am. Sci. 58, 669}673.
MILLER, G. (1991). ¹he Science of =ords. New York: Scienti"c American Library.
NOWAK, M. A. & KRAKAUER, D. C. (1999a). The
Evolution of Language. Proc. Nat. Acad. Sci. ;.S.A. 96,
8028.
NOWAK, M. A., PLOTKIN, J. B. & KRAKAUER, D. C. (1999a).
The Evolutionary Language Game. J. theor. Biol. 200,147}162.

LANGUAGE EVOLUTION AND INFORMATION THEORYNOWAK, M. A., KRAKAUER, D. C. & DRESS, A. (1999b). An
error-limit for the evolution of language. Proc. Roy. Soc.
¸ondon B 266, 2131}2136.
NOWAK, M. A., PLOTKIN, J. B. & JANSEN, V. A. A. (2000).
The evolution of syntactic communication. Nature 404,495}498.
PINKER, S. (1995). ¹he ¸anguage Instinct. New York: Penguin.
SHANNON, C. E. (1948). A Mathematical Theory of Communication. Bell System ¹echnical Journal 27, 379}423, 623}656.

159

SHANNON, C. E. & WEAVER, W. (1949). ¹he Mathematical¹heory of Communication. Illinois: University of Illinois
Press.
VAN DER LUBBE, J. (1988). Information ¹heory. Cambridge:
Cambridge University Press.
WELSH, D. (1988). Codes and Cryptography. Oxford University Press.
WOLFOWITZ, J. (1961). Coding theorems of information
theory. Berlin: Springer-Verlag.