Top banner
MY AMERICAN SCIENTIST
LOG IN! REGISTER!
SEARCH
 
RSS
Logo

COMPUTING SCIENCE

Rumours and Errours

Brian Hayes

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

Figure 1. The birth and death of a rumor...Click to Enlarge Image

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):

repeat

    choose X at random from among the spreaders in the population;

    choose Y at random from the entire population;

    if Y is an ignorant

       then make Y a spreader

    else if Y is a spreader

       then make both X and Y stiflers

    else if Y is a stifler

       then make X a stifler

until there 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.

Figure 2. The dynamics of rumors...Click to Enlarge Image

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....

Figure 3. The longevity of a rumor...Click to Enlarge Image

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.)

Figure 4. Matrix of all possible events...Click to Enlarge Image

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, WeW .)

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 :


Bottom Banner