Pious penal probability puzzle

Secret Blogging Seminar 2018-03-12

Here is a fun problem, with a great story and a surprising answer.

According to the Talmud, in order for the Sanhedrin to sentence a man to death, the majority of them must agree to it. However

R. Kahana said: If the Sanhedrin unanimously find [the accused] guilty, he is acquitted. (Babylonian Talmud, Tractate Sanhedrin, Folio 17a)

Scott Alexander has a devious mind and considers how he would respond to this rule as a criminal:

[F]irst I’d invite a bunch of trustworthy people over as eyewitnesses, then I’d cover all available surfaces of the crime scene with fingerprints and bodily fluids, and finally I’d make sure to videotape myself doing the deed and publish the video on YouTube.

So, suppose you were on a panel of $N$ judges, all of whom had seen overwhelming evidence of the accused’s guilt, and wanted to make sure that a majority of you would vote to convict, but not all of you. And suppose you cannot communicate. With what probability $p$ would you vote to convict?

Test your intuition by guessing an answer now, then click below:

My gut instincts were that (1) we should choose $p$ really close to $1$ , probably approaching $1$ as $N \to \infty$ and (2) there is no way this question would have a precise round answer. As you will see, I was quite wrong.

Tumblr user lambdaphagy is smarter than I was and wrote a program. Here are his or her results:

As you can see, it appears that $p$ is not approaching $1$ , or even coming close to it, but is somewhere near $0.8$ . Can we explain this?

Heuristic solution

We want to avoid two events: unanimity, and a majority vote to acquit. The probability of unanimity is $p^N$ .

The probability of a majority vote to acquit is $\sum_{k=0}^{\lfloor N/2 \rfloor} \binom{N}{k} p^k(1-p)^{N-k}$ . Assuming that $p>0.5$ , and it certainly should be, almost all of the contribution to that sum will come from terms where $k \approx N/2$ . In that case, $\binom{N}{k} \approx 2^N/\sqrt{N}$ . And we’ll roughly care about $\sqrt{N}$ such terms. So the odds of acquittal are roughly $\sqrt{N} \tfrac{2^N}{\sqrt{N}} p^{N/2} (1-p)^{N/2} = \sqrt{4p(1-p)}^N$ .

So we roughly want $p^N+\sqrt{4p(1-p)}^N$ to be as small as possible. For $N$ large, one of the two terms will be much larger than the other, so it is the same to ask that $\max(p, \sqrt{4p(1-p)})^N$ be as small as possible.

Here is a plot of $\max(p, \sqrt{4 p(1-p)})$ :

maxPlot Ignore the part with $p$ below $1/2$ ; that’s clearly wrong and our approximation that $\sum_{k=0}^{\lfloor N/2 \rfloor} \binom{N}{k} p^k(1-p)^{N-k}$ is dominated by $k \approx N/2$ won’t be good there. Over the range $p>1/2$ , the minimum is where $p=\sqrt{4p (1-p)}$ .

Let’s do some algebra: $p = \sqrt{4p(1-p)}$ , $p^2= 4 p(1-p)$ , $p = 4(1-p)$ (since $p=0$ is clearly wrong), $p = 4/5$ . Holy cow, $4/5$ is actually right!

Lessons learned

First of all, actually do some computations.

Secondly, I was wrongly thinking that failing by acquittal would be much more important than failing by unanimity. I think I was mislead because one of them occurs for $N/2$ values of $k$ and the other only occurs for one value. I should have realized two things (1) the bell curve is tightly peaked, so it is really only the $k$ very close to $N/2$ which matter and (2) exponentials are far more powerful than the ratio between $N$ or $\sqrt{N}$ and $1$ anyway.

Rigorous computation

Finally, for the skeptics, here is an actual proof. Assuming $p>1/2$ , we have $\displaystyle{ \sum_{k=0}^{\lfloor N/2 \rfloor} \binom{N}{k} p^k(1-p)^{N-k} \leq \sum_{k=0}^{\lfloor N/2 \rfloor} \binom{N}{k} p^{N/2} (1-p)^{N/2} \leq 2^N p^{N/2} (1-p)^{N/2}}.$ The main step is to replace each $p^k(1-p)^{N-k}$ by the largest it can be.

But also, $\displaystyle{ \sum_{k=0}^{\lfloor N/2 \rfloor} \binom{N}{k} p^k(1-p)^{N-k} \geq \binom{N}{\lfloor N/2 \rfloor} p^{\lfloor N/2 \rfloor} (1-p)^{\lceil N/2 \rceil} \geq \frac{1}{N+1} \sqrt{\frac{1-p}{p}} \ 2^N p^{N/2} (1-p)^{N/2}} .$ Here we have lower bounded the sum by one of its terms, and then used the easy bound $\binom{N}{\lfloor N/2 \rfloor} \geq \frac{1}{N+1} 2^N$ since it is the largest of the $N+1$ entries in a row of Pascal’s triangle which sums to $2^N$ .

So the odds of failure are bounded between $\tfrac{1}{N+1} \sqrt{\frac{1-p}{p}} \sqrt{4p(1-p)}^N+p^N$ and $\sqrt{4p(1-p)}^N+p^N$ . We further use the convenient trick of replacing a $+$ with a $\max$ , up to bounded error to get that the odds of failure are bounded between $\max \left( \tfrac{1}{N+1} \sqrt{\frac{1-p}{p}} \sqrt{4p(1-p)}^N, p^N \right)$ and $2 \max \left( \sqrt{4p(1-p)}^N, p^N \right)$ .

Now, let $p$ be a probability greater than $1/2$ other than $4/5$ . We claim that choosing conviction probability $4/5$ will be better than $p$ for $N$ large. Indeed, the $p$ -strategy will fail with odds at least $\max \left( \tfrac{1}{N+1} \sqrt{\frac{1-p}{p}} \sqrt{4p(1-p)}^N, p^N \right)$ , and the $4/5$ strategy will fail with odds at most $2 \cdot (4/5)^N$ . Since $\max(p, \sqrt{4p(1-p)}) > 4/5$ , one of the two exponentials in the first case is larger than $4/5$ , and the $p$ -strategy is more likely to fail, as claimed.

Of course, for a Sanhedrin of $23$ members, $2 (4/5)^{23} \approx 0.011$ , so our upper bound predicts only a one percent probability of failure. More accurately computations give $0.005$ . So the whole conversation deals with the overly detailed analysis of an unlikely consequence of a bizarre hypothetical event. Fortunately, this is not a problem in the study of Talmud!