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....
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.
» Post Comment