In Anirban DasGupta’s latest puzzle, we’re looking at a delicate and fascinating phenomenon pervasive in mathematics and probability: phase transition. A system’s evolution is being driven or influenced by some underlying force or parameter, and when that parameter just crosses a suitable critical boundary or threshold, the system undergoes a rapid transition. We propose a problem that can be rhetorically framed as whether we should put any trust in a unanimous assertion made independently by a large number of pathological liars. On the one hand, you may argue that if just one of them is telling the truth, then the assertion must be true. But you may also argue that chronic liars should never be trusted. It will turn out that in an appropriate mathematical formulation, there is a phase transition in the problem, and we will ask you to discover that phase transition. Here is the exact statement of the problem.

A club consists of $m$ members, and on any given instance, each member tells the truth with probability $p$ and lies with probability $1-p$; we will take $p$ to be very small, but not zero. The club members are assumed to act independently. Suppose that these $m$ members are taken to planet $X$, and on arrival, each member is given a choice of $n$ distinct color names, such as red, blue, green, etc. Each member looks at Earth from planet $X$, and one by one each of them announces that Earth looks purple, one of the colors on their color list.

a) Suppose $m=n=20$. Calculate the probability that indeed Earth looks purple from planet $X$ if each club member said so, for $p=.05$ and for $p=.04$; assume that the true color is one of the $n$ on the list with equal probability.

b) Suppose $\frac{1}{p}=n–\alpha \log n,m=\gamma n$, where $\alpha \ge 0,\gamma >0$. Denote the probability that from planet X, Earth really does look purple if each of the $m$ members says so by $\alpha \ge 0,\gamma >0$. Find the limit of $u(\alpha ,\gamma ,n)$ as $n\to \mathrm{\infty }$ for given $\alpha$ and given $\gamma$.

Remember to look for a phase transition.

Solution to Puzzle 25

The solution to the previous puzzle is here.