Find him guilty

A court is comprised of an odd number N = 2 k + 1 N=2k+1 of judges. After each case, the judges vote "guilty" or "not guilty." If a majority vote "not guilty," the accused is set free. If a majority vote "guilty," the accused is imprisoned--unless the "guilty" vote is unanimous, in which case the accused is set free!

The judges cast their votes simultaneously and there is no communication or collusion allowed among the judges at any point. Suppose that a criminal comes before the court who is obviously guilty and a danger to society. What should the judges do?

Clearly, each judge should employ a mixed strategy : pick a number p p between 0 0 and 1 , 1, and vote "guilty" with probability p p and "not guilty" with probability 1 p . 1-p. Here the judges want to pick a value for p p that maximizes the chance of imprisoning the criminal. Call that value p N . p_N. For example, you might want to check that p 3 = 2 3 , p_3 = \frac23, with the criminal being imprisoned 4 9 \frac49 of the time.

What happens when N N gets large? That is, what is lim k p 2 k + 1 ? \displaystyle \lim_{k\to\infty} p_{2k+1}?


Source: the Secret Blogging Seminar


The answer is 0.8.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Patrick Corn
Sep 21, 2017

As in the problem, let N = 2 k + 1. N=2k+1. Let p = p N p = p_N just for ease of notation. The probability that the criminal is found guilty is i = k + 1 2 k ( N i ) p i ( 1 p ) N i . \sum_{i=k+1}^{2k} \binom{N}{i} p^i (1-p)^{N-i}. Let's take the derivative of this with respect to p p and set it equal to 0. 0. This gives 0 = i = k + 1 2 k ( N i ) ( i p i 1 ( 1 p ) N i ( N i ) p i ( 1 p ) N i 1 ) . 0 = \sum_{i=k+1}^{2k} \binom{N}{i} \left(ip^{i-1}(1-p)^{N-i} - (N-i)p^i (1-p)^{N-i-1}\right). Break this into two sums: 0 = i = k + 1 2 k i ( N i ) p i 1 ( 1 p ) N i i = k + 1 2 k ( N i ) ( N i ) p i ( 1 p ) N i 1 . 0 = \sum_{i=k+1}^{2k} i \binom{N}{i} p^{i-1}(1-p)^{N-i} - \sum_{i=k+1}^{2k} (N-i) \binom{N}{i} p^i (1-p)^{N-i-1}. Change the index on the first one: 0 = j = k 2 k 1 ( j + 1 ) ( N j + 1 ) p j ( 1 p ) N j 1 i = k + 1 2 k ( N i ) ( N i ) p i ( 1 p ) N i 1 . 0 = \sum_{j=k}^{2k-1} (j+1)\binom{N}{j+1} p^j(1-p)^{N-j-1} - \sum_{i=k+1}^{2k} (N-i) \binom{N}{i} p^i (1-p)^{N-i-1}. Now change the j j back to an i i and recombine, remembering to take out the terms at the edge: 0 = ( k + 1 ) ( N k + 1 ) p k ( 1 p ) k N p 2 k + i = k + 1 2 k 1 ( ( i + 1 ) ( N i + 1 ) ( N i ) ( N i ) ) p i ( 1 p ) N i 1 . 0 = (k+1)\binom{N}{k+1} p^k(1-p)^k - N p^{2k} + \sum_{i=k+1}^{2k-1} \left( (i+1) \binom{N}{i+1} - (N-i)\binom{N}{i} \right) p^i (1-p)^{N-i-1}. Magically, the quantity ( i + 1 ) ( N i + 1 ) ( N i ) ( N i ) (i+1)\binom{N}{i+1} - (N-i)\binom{N}{i} equals N ! i ! ( N i 1 ) ! N ! i ! ( N i 1 ) ! = 0 , \frac{N!}{i!(N-i-1)!} - \frac{N!}{i!(N-i-1)!} = 0, so that whole sum on the right goes away. We're left with N p 2 k = ( k + 1 ) ( N k + 1 ) p k ( 1 p ) k ( p 1 p ) k = k + 1 N ( N k + 1 ) ( p 1 p ) k = ( N 1 k ) = ( 2 k k ) p 1 p = ( 2 k k ) 1 / k . \begin{aligned} Np^{2k} &= (k+1)\binom{N}{k+1} p^k(1-p)^k \\ \left( \frac{p}{1-p} \right)^k &= \frac{k+1}{N} \binom{N}{k+1} \\ \left( \frac{p}{1-p} \right)^k &= \binom{N-1}{k} = \binom{2k}{k} \\ \frac{p}{1-p} &= \binom{2k}{k}^{1/k}. \end{aligned}

Now we're ready to use Stirling's approximation applied to central binomial coefficients , which says that ( 2 k k ) 4 k π k . \binom{2k}{k} \sim \frac{4^k}{\sqrt{\pi k}}. So p 1 p 4 ( π k ) 1 / 2 k , \frac{p}{1-p} \sim \frac4{(\pi k)^{1/2k}}, which approaches 4 4 as k . k \to \infty. Then p 1 p 4 \frac{p}{1-p} \to 4 gives p 4/5 . p \to \fbox{4/5}.

(Bonus: you might wonder if there is a natural explanation for the magic cancellation above, where the middle terms of the two sums are the same. Try to find it!)

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...