11

The Problem of the n-Liars

11.1 THE PROBLEM

Imagine that we have n people, each of whom tells the truth with probability p when making a statement. That is, if p = 1 a person never lies (always tells the truth) and if p = 0 a person always lies. Each of the n people either lies or tells the truth independent of the others. Now, suppose we line up these n people in a row, shoulder to shoulder, from left to right. Starting at the leftmost person, you whisper either “yes” or “no” into his ear, and then that person turns his head and whispers what he heard into the ear of the person next to him. That is, he repeats what he heard unless he lies and so whispers “yes” when he actually heard “no,” or whispers “no” when he actually heard “yes.” This process continues until the rightmost person hears his neighbor whisper one of the two words into his ear; he then speaks out loud either “yes” or “no”. What is the probability Q(n) that the word you originally whispered is the word spoken?

Evaluate your answer for the case of n = 41, with p = 0.99. What happens as n → ∞?

11.2 THEORETICAL ANALYSIS

In the introduction (I.8), we calculated the probability P(n) of getting an even number of heads in n flips of a coin, with p as the probability of heads on each independent flip:

When we did the coin-flipping analysis, it probably seemed to be essentially just an amusing exercise. Now you can see it is actually a doubly amusing exercise! Here’s how that earlier analysis applies to this new question.

For a yes to emerge at the end of the chain of liars when it was started with a yes (or for a no to emerge when no started the chain), an even number of lies must have occurred (lies cancel in pairs). This is equivalent to an even number of tails in the coin-flipping problem as each (tails and lies) occurs with probability 1 − p. Now, if n is even, then getting an even number of tails is the same as getting an even number of heads, and so Q(n) = P(n). That is,

But if n is odd, then getting an even number of tails is the same as getting an odd number of heads, which occurs with probability 1 − P(n). So

We can write these two Q(n) expressions as a single one, valid for even and odd n, as

since (−1)ⁿ = +1 or −1 for n even or odd, respectively. Thus, we at last have, for any n,

For p = 0.99 and n = 41 liars, this probability is 0.718393. Also,

for all 0 < p < 1. As the number of liars increases, which word finally emerges at the end of the process is a toss-up for any value of p other than p = 0 or p = 1. If p = 1 (everybody always tells the truth), then obviously Q(n) = 1, while if p = 0 (everybody always lies), then Q(n) = 1 or 0, depending on whether n is even or odd, respectively.

11.3 COMPUTER SIMULATION

The idea behind a computer simulation of the chain of n liars is very straightforward. The code simply counts the number of lies from start to finish, and after the entire chain has been simulated, this count is checked for “evenness.” If it is even, then the word that emerges at the end of the chain is the word that started the chain. The brief code liar.m does the job, simulating ten million chains of liars, and when run for n = 41 and p = 0.99 its estimate was Q(41) = 0.7184214, impressively close to the theoretical value.