7

Chain Letters That Never End

7.1 THE PROBLEM

Just to be sure you don’t think I am claiming computer simulation is a complete substitution for theory, here’s an example of a random process that would be nontrivial to simulate, and we’ll count ourselves lucky to have a theoretical solution. Suppose somebody decides to create a chain letter, and starts things off by sending a copy of it to C people. Each of those C people is asked to then send off C copies of their own, and so on. With probability p, any person who receives such a letter decides to ignore it. What is the probability that this chain letter eventually disappears? There is no guarantee that it will, after all, and simulating a process that potentially has no termination point presents some practical difficulties! Fortunately, there is a very nice way to attack this problem analytically.

7.2 THEORETICAL ANALYSIS

How does our chain letter die? For that to happen, each of the original C recipients can be thought of as starting a sub-chain letter sequence that eventually terminates with probability E (for extinction). There are just two ways such a sub-chain letter sequence can terminate: (1) with probability p the original recipient simply doesn’t send his C copies, and (2) with probability 1 − p he does send his C copies, and then later all the resulting C sub-sub-chain letter sequences initiated by those copies eventually terminate (which happens with probability E^C). Thus, we arrive at the following C-order algebraic equation for E:

E = p + (1 − p) E^C.

Once we select a value for C, we can solve this equation for the extinction probability for a sub-chain, E, over and over, as we let p vary from 0 to 1. The value of E^C as p varies gives us the probability we are after, the probability that all of the sub-chains started by the original recipients terminate. The complementary probability, 1 − E^C, is the probability that the chain letter goes on forever.

The equation has the obvious solution E = 1 for any value of C (and all p), but for interesting values of C (say, 2 to 5), there are other solutions as well (they include those that are negative, greater than 1, or complex, and so none can be a valid probability), and so we are faced with a fairly substantial number-crunching task. Fortunately, modern computer software is up to the job (I used MATLAB^®’s powerful command solve), and Figures 7.2.1 through 7.2.4 show the probability E^C versus p for C = 2, 3, 4, and 5, respectively. For the case of p = 1/2 (each recipient flips a fair coin to decide whether to send his C copies or to forget it), we have, for example, E³ = 0.2361 and E⁴ = 0.0874. Adding just one additional copy (from C = 3 to C = 4) greatly reduces (by nearly a factor of 3) the probability the chain letter will eventually terminate.

Figure 7.2.1. The probability E^C versus p for C = 2.

Figures 7.2.2. The probability E^C versus p for C = 3.

Figures 7.2.3. The probability E^C versus p for C = 4.

Figures 7.2.4. The probability E^C versus p for C = 5.