Subscribe
Subscribe
MY AMERICAN SCIENTIST
LOG IN! REGISTER!
SEARCH
 
Logo IMG
HOME > PAST ISSUE > May-June 2005 > Article Detail

COMPUTING SCIENCE

Rumours and Errours

Brian Hayes

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.








comments powered by Disqus
 

EMAIL TO A FRIEND :

Subscribe to American Scientist