COMPUTING SCIENCE

# Rumours and Errours

The confessional essay is not a popular genre in mathematics and the sciences; few of us wish to dwell on our mistakes or call attention to them. An inspiring exception is Donald E. Knuth of Stanford University. During a decade's labor on the TeX typesetting system, he kept a meticulous log of all his errors, and then he published the list with a detailed commentary.

I have long admired Knuth's act of public bravery, and this column is my attempt to follow his example. I took courage from the thought that if there is any realm of life in which I might hope to surpass Don Knuth, it's in making mistakes; but, alas, I've fallen short even in this dubious department. Knuth's published error log runs to more than 900 entries, whereas here I am going to confess to only a paltry handful of mistakes. Then again, Knuth needed 10 years' work on a major software project to accumulate his budget of errors, but I was able to commit some really serious howlers in a program of a dozen lines.

Knuth remarks that keeping an error log not only helped in debugging the program but also "helped me to get to know myself." I would like to think that I too have acquired some self-knowledge from the experience of confronting my own fallibility. And it would be gratifying to suggest that by telling my story I might save others from making the same mistakes—but I don't quite believe that, and I'm not even sure it would be a good idea.

Start Spreading the News

The story begins with a loose end from my column on the Lambert
*W* function in the March-April issue of *American
Scientist*. I had been looking for a paper with the curious
title "Rumours with general initial conditions," by Selma
Belen and C. E. M. Pearce of the University of Adelaide, published
in *The ANZIAM Journal,* which is also known as *The
Australia and New Zealand Industrial and Applied Mathematics
Journal*. By the time I found the paper, my column had already
gone to press. This was a disappointment, because Belen and Pearce
describe an illuminating application of the *W* function in a
context that I found interesting in its own right. Here is how they begin:

The stochastic theory of rumours, with interacting subpopulations of ignorants, spreaders and stiflers, began with the seminal paper of Daley and Kendall. The most striking result in the area—that if there is one spreader initially, then the proportion of the population never to hear the rumour converges almost surely to a proportion 0.203188 of the population size as the latter tends to infinity—was first signalled in that article. This result occurs also in the variant stochastic model of Maki and Thompson, although a typographic error has resulted in the value 0.238 being cited in a number of consequent papers.

I was intrigued and a little puzzled to learn that a rumor would die
out while "almost surely" leaving a fifth of the people
untouched. Why wouldn't it reach everyone eventually? And that
number 0.203188, with its formidable six decimal places of
precision—where did *that* come from?

I read on far enough to get the details of the models. The premise,
I discovered, is that rumor-mongering is fun only if *you*
know the rumor and your audience doesn't; there's no thrill in
passing on stale news. In terms of the three subpopulations, people
remain spreaders of a rumor as long as they continue to meet
ignorants who are eager to receive it; after that, the spreaders
become stiflers, who still know the rumor but have lost interest in
propagating it.

The Daley-Kendall and Maki-Thompson models simplify and formalize this social process. Both models assume a thoroughly mixed population, so that people encounter each other at random, with uniform probability. Another simplifying assumption is that people always meet two-by-two, never in larger groups. The pairwise interactions are governed by a rigid set of rules:

•Whenever a spreader meets an ignorant, the ignorant becomes a spreader, while the original spreader continues spreading.

•When a spreader meets a stifler, the spreader becomes a stifler.

•In the case where two spreaders meet, the models differ. In the Daley-Kendall version, both spreaders become stiflers. The Maki-Thompson rules convert only one spreader into a stifler; the other continues spreading.

•All other interactions (ignorant-ignorant, ignorant-stifler, stifler-stifler) have no effect on either party.

The rules begin to explain why rumors are self-limiting in these models. Initially, spreaders are recruited from the large reservoir of ignorants, and the rumor ripples through part of the population. But as the spreaders proliferate, they start running into one another and thereby become stiflers. Because the progression from ignorant to spreader to stifler is irreversible, it's clear the rumor must eventually die out, as all spreaders wind up as stiflers in the end. What's not so obvious is why the last spreader should disappear before the supply of ignorants is exhausted, or why the permanently clueless fraction is equal to 0.203188 of the original population.

The rumor models are closely related to well-known models of epidemic disease, where the three subpopulations are usually labeled susceptibles, infectives and removed cases. But there's a difference between rumors and epidemics. In the rumor models, it's not only the disease that's contagious but also the cure, since both spreading and stifling are communicable traits.

The Rumor Mill

I was curious to see the rumor models in action, and so I wrote a little program. I set up a population of 1,000 individuals, each of whom could be an ignorant, a spreader or a stifler. Initially there was just one spreader and all the rest were ignorants. At the heart of the program was the following procedure, meant to implement the Daley-Kendall model (the one in which pairs of spreaders annihilate each other):

repeatchoose

Xat random from among the spreaders in the population;choose

Yat random from the entire population;

ifYis an ignorant

thenmakeYa spreader

else ifYis a spreader

thenmake bothXandYstiflers

else ifYis a stifler

thenmakeXa stifler

untilthere are no more spreaders

When all the spreaders are gone, nothing more can change, so the
program ends and reports the fraction of the population still
oblivious of the rumor. This fraction, designated *θ*,
should be 0.203188. But the result from my program, averaged over a
few thousand runs, was 0.28 or 0.29—a considerable discrepancy.

At this point, let me pause to say that my big boo-boo had already been committed. Before reading on, you might want to try debugging my algorithm, or even write a program of your own.

Typos and Thinkos

Computer programming teaches humility, or at least that's my experience. In principle, the discrepancy I observed might have pointed to an error in the published result, but that wasn't my first hypothesis. I checked my own code, fully expecting to find some careless mistake—running through a loop one time too few or too many, failing to update a variable, miscalculating an array index. Nothing leapt out at me. The problem, I began to suspect, was not a typo but a thinko.

I did know of one soft spot in the program. The individuals
*X* and *Y* were chosen in such a way that they could
both turn out to be the same person, suggesting the strange
spectacle of spreading a rumor to oneself. ("Pssst. Have I
heard about...?") When I went to fix this oddity, I discovered
another bug. A variable named *spreader-count* was
incremented or decremented on each passage through the loop,
according to the outcome of the encounter; when this variable
reached zero, the program ended. After each spreader-spreader
interaction, I decreased *spreader-count* by 2—with
potentially disastrous results if *X* and *Y* were
identical. This was a serious flaw, which needed to be repaired;
however, the change had no discernible effect on the value of
*θ*, which remained stuck at 0.285.

I had another thought. Belen and Pearce were careful to state that their result holds only when the population size tends to infinity. Perhaps my discrepancy would go away in a larger sample. I tried a range of populations, with these results:

population θ10 0.354 100 0.296 1,000 0.286 10,000 0.285 100,000 0.285

The trend was in the right direction—a smaller proportion of
residual ignorants as population increased—but the curve
seemed to flatten out beyond 1,000, and θ looked unlikely ever
to reach 0.203. Even so, it seemed worthwhile to test still larger
populations, but for that I would need a faster program. I wrote a
new and simpler version, dispensing with the array of individuals
and merely keeping track of the number of persons in each of the
three categories. With this strategy I was able to test populations
up to 100 million. The value of *θ* remained steady at 0.285.

Looking at the distribution of *θ* values from single
runs of the program (rather than averages over many runs) suggested
another idea. Most of the results were clustered between
*θ*=0.25 and *θ*=0.35, but there were a
few outliers—runs in which 99 percent of the population never
heard the rumor. I could see what must be going on. Suppose on the
very first interaction *X* spreads the rumor to *Y*,
and then in the second round the random selection happens to settle
on *X* and *Y* again. The rumor dies in infancy,
having reached only two people. Could it be that excluding these
outliers would bring the average value of θ down to 0.203? I
gave it a try; the answer was no.

Mea Culpa

I was stumped. I had reached the point in a debugging session where you begin to doubt your random-number generator, or even your compiler. As it happens, Knuth found a few compiler bugs during his work on TeX, but for me that road has always led nowhere.

For lack of a better idea, I decided to look at the other scheme of
rumor propagation, the Maki-Thompson model. As indicated above, this
model differs from the Daley-Kendall one in that an encounter
between two spreaders converts just one of them into a stifler.
Modifying my program took only a second. When I ran it, the answer
came back *θ*=0.203. Now I was not just stumped but
also thoroughly confused.

Here's where confession becomes a test of character. There was a
moment—it came in the dark of the night—when I allowed
myself to entertain the notion that maybe *I* was right after
all, and the rest of the world had a screw loose. I looked back at
the opening paragraph of the paper by Belen and Pearce. I realized
that I could make sense of it all, and reconcile their numbers with
mine, merely by assuming that the Australian authors had everything
umop-episdn. The number 0.203, which they identified as the result
of the Daley-Kendall model, really belonged with Maki-Thompson. As
for 0.238, which they called a typographical error—well, yes,
that's just what it was, a transposition of 0.283, which seemed
close enough to 0.285, the value of *θ* I calculated
for Daley-Kendall....

By morning this madness had abated, but the impasse remained. I knew I could probably settle the matter by going back to the library and looking up the sources cited by Belen and Pearce, but that seemed less than sporting. I could have tried to prove the correctness of one result or the other, but if I can't trust myself to write a correct program, how can I be trusted to write a correct proof? Then there's the experimental method: I might have assembled a thousand volunteers, carefully instructed them on the Daley-Kendall rules, and set a rumor loose in their midst.

In the end, what I tried was yet another computer simulation. I decided to write a program that would mimic a real experiment as closely as possible, reproducing all the basic events of the underlying model with no shortcuts or optimizations. The image I had in mind was a crowd of people milling about like molecules in a gas, bumping into each other at random and passing on rumors during these chance collisions. This was the system I wanted to simulate.

My first program, with its explicit representation of each member of
the population, was already fairly close to the goal. But I had made
one refinement for the sake of computational efficiency. Because
interactions in which neither party is a spreader could never affect
the fate of a rumor, it seemed wasteful to include them; I avoided
that waste by always choosing a spreader as the first party to an
encounter. This seemed a totally harmless bit of streamlining, but
now I went back and removed it. In the third version of the program,
I selected two individuals at random from the entire population,
checked to make sure they were not actually the same person, and
then allowed them to interact according to the Daley-Kendall rules.
It seemed a futile exercise, which would surely yield exactly the
same result as the other programs, only slower. To my astonishment,
the new program reported *θ*=0.203.

My Bad

If you have already figured out where my reasoning went astray, I offer my congratulations. My own belated enlightenment came when I finally drew the matrix of all nine possible encounters of ignorants, spreaders and stiflers. As shown in Figure 4, this diagram can serve as more than just an enumeration of possible outcomes; it encodes the entire structure and operation of the model. If we make the widths of the columns and rows proportional to the sizes of the three subpopulations, then the area of each of the nine boxes gives the probability of the corresponding two-person encounter. Choosing two participants at random is equivalent to choosing a point at random within the diagram; the outcome of the interaction is then decided by which of the nine boxes the chosen point lies within. (I am again glossing over the issue of spreading a rumor to oneself; it's a minor correction.)

To understand where I went wrong, it's enough to analyze the simplest case, where the three subpopulations are of equal size and all nine kinds of encounters have the same probability, namely 1/9. The boxes at the four corners of the diagram correspond to events that do not involve a spreader and that change no one's status. Two other boxes describe ignorant-spreader encounters, which therefore have a total probability of 2/9. Two more boxes correspond to spreader-stifler meetings, so those events also occur with probability 2/9. But there is only one box representing spreader-spreader interactions, which accordingly must be assigned a probability of 1/9. The key point is that ignorant-spreader and spreader-stifler events are each twice as likely as spreader-spreader meetings.

Now consider what happens in my first program for the Daley-Kendall model. By always choosing a spreader first, I confined all events to the middle row of the matrix, and the three boxes in this row were selected with equal probability. As a result, spreader-spreader interactions were twice as frequent as they should have been, and the rumor was extinguished prematurely.

From the point of view of probability theory, the error is an elementary one of failing to count cases properly. Perhaps a professional programmer would cite a different root cause: I had violated the old adage, "Don't start optimizing your program until you've finished writing it."

Back to the Stacks

Not all of my confusion was cleared up by the discovery of this error. In particular, the algorithm that I now knew to be incorrect for the Daley-Kendall model still seemed to give the right answer for the Maki-Thompson rules. To make sense of this situation, I finally went back to the library to find out what the original authors had said.

Daley and Kendall are Daryl J. Daley, now of the Australian National
University, and David G. Kendall, a distinguished statistician and
probabilist at the University of Cambridge. Their paper, published
in 1965, is a model of lucid exposition, which would have spared me
all my stumbling in the dark—and for that reason I'm glad I
didn't see it sooner. The correct calculation of probabilities is
stated very clearly (there's a factor of 1/2 in the expression for
the spreader-spreader interaction). Furthermore, the origin of the
mysteriously precise number 0.203188 is made plain. Those six digits
come not from a discrete-event simulation like the ones I had
designed but from a continuous, differential-equation version of the
model. The number *θ* is a solution of the equation:

*θ* *e* ^{2(1-} ^{
θ)} = 1.

(This equation brings us back almost to the Lambert *W*
function, *We ^{W}
* .)

Maki and Thompson are Daniel P. Maki and Maynard Thompson of Indiana
University, who discussed rumors in a 1973 textbook,
*Mathematical Models and Applications*. They described
the rumor-passing process in terms of telephone calls, and they
limited their attention to calls placed by spreaders; because of
this asymmetry, only the middle row of the matrix in Figure 4 enters
into the calculation, and my first program was in fact a correct
implementation of their model. (At least I got *something*
right.) It is almost a coincidence that Maki and Thompson arrive at
the same value of *θ* as Daley and Kendall: Their
spreader-spreader interactions are twice as likely but have only
half the effect.

The paper by Belen and Pearce that launched me on this adventure
also deserves a further comment. The phrase "general initial
conditions" in their title refers to rumors initiated not by a
single spreader but by many. One might guess that with enough
spreaders, the rumor must surely permeate the entire society, but
Belen and Pearce show otherwise. Measuring the fraction of those
originally ignorant who remain ignorant when the rumor has finished,
they find that this fraction actually increases along with the
number of initial spreaders, tending to a maximum of 1/*e*,
or about 0.368. In other words, as more people spread the news, more
people fail to hear it. The reason is simply that the multitude of
spreaders quickly stifle one another.

By now the mathematics of rumors has acquired a vast literature. Variant models track competing rumors and counter-rumors or allow people to meet more than two at a time. Still more models study the progress of rumors through networks or lattices rather than structureless mixed populations. I have not yet had a chance to make any errors in exploring these systems.

Gnothi Seauton

Mistakes bring the gift of self-knowledge—a gift that is not always welcome. Looking back on this episode, I could summarize it as follows: I wrote a program that gave a wrong answer, and then I fiddled and fudged until I finally got the output I wanted, and then I stopped. This is not a protocol to be recommended. What's most troubling is the uncomfortable thought that if the textbook answer had not been given to me at the outset, I would surely have been content with the result of my first, fallacious, program.

Still, for most of us, the only way we'll never err is if we never try. My fellow-columnist Henry Petroski has written eloquently about the necessary role of error and failure in all worthy undertakings; as he says, falling down is part of growing up. And if we are going to make mistakes, it seems salutary to bring them out in the open and discuss their causes. Staring them in the face makes them seem a little less mortifying.

Only a little, though. A confession of this kind is not followed by absolution. And instead of "Go and err no more," Knuth quotes Piet Hein's advice: "Err and err and err again but less and less and less." I take my own motto from the novelist and playwright Samuel Beckett: "Fail again. Fail better."

© Brian Hayes

EMAIL TO A FRIEND :