Gerrymandering urns (redux)

Question

This is a rehash of this question (and probably the intent of this, and several other similar questions), but I'd like:

• a more detailed answer that builds from the simplest cases to potentially higher order applications and more references to explanations, if possible.
• a proof of the optimality of the so-called gerrymandering solution.

So here is a complete statement of the problem:

Suppose that you are given 50 each of red and blue balls, and two urns. You place the red and blue balls in the urns (so that each is nonempty, and all the balls are allocated to some urn). Then you pick a jar at random and pick a ball at random. The objective is to distribute the red and blue balls in each of the urns so that the probability of picking a red ball is maximized.

The so-called gerrymandering solution is given after the break below, and I am wondering if there is a systematic way of arriving at this solution, other than guesswork.

---

Attempt 1

My first thought was to use calculus on this problem, so that if I denote the jars A and B, and denote the tuple $(x, y)$ as the number of red and blue balls in jar A. The the solution $(x^*, y^*)$ is the solution to the first-order conditions. (This is probably a red herring, since only nonnegative integer solutions are valid.)

$$ \begin{alignat}{2} &&p(x, y) &= \frac{1}{2}\left(\dfrac{x}{x+y}+ \dfrac{50-x}{100-x-y}\right) \\[1em] &&\left. \dfrac{\partial p(x, y)}{\partial x}\right|_{(x,y)=(x^*, y^*)} &= 0 \\[1em] &\implies\quad&\dfrac{2x^*+y^*}{(x^*+y^*)^2}-\dfrac{150-2x^*-y^*}{(100-x^*-y^*)^2} &=0 \\[1em] &&\left. \dfrac{\partial p(x, y)}{\partial y}\right|_{(x,y)=(x^*, y^*)} &= 0 \\[1em] &\implies\quad& \dfrac{-x^*}{(x^*+y^*)^2} +\dfrac{50-x^*}{(100-x^*-y^*)^2} &= 0 \end{alignat} $$

This involves finding the solution of cubic equations (which I am sure can be done, with the help of CAS, but it is not obvious that this yields the gerrymandering solution (does it?)). Is this the right way to think about the problem? What is?

---

Attempt 2

Note however that the objective function is closed-form, so can easily be graphed, and then the solution becomes clear.

---

The gerrymandering solution

You place one red ball and no blue balls in one urn and all the other balls in the other urn. This leads to the probability of picking a red ball $>\tfrac{1}{2}$.

Answer 1

It's absolutely possible to solve this using calculus; in fact that's how I would solve it. With a problem like this, it's important to make use of the symmetries to simplify the calculations. Your formulation of the problem is asymmetric both with respect to the two urns and with respect to the two colours. You can see from your plot that there's a lot more symmetry in the problem than is apparent from your equations.

To make use of the symmetry, let $r$ be the number of red balls beyond the average of $25$ in the first urn, let $b$ be the number of blue balls beyond the average of $25$ in the first urn, and calculate the difference between the probability of drawing a red ball and the average probability $1/2$:

$$ \begin{align} & \frac12\left(\frac{25+x}{25+x+25+y}+\frac{25-x}{25-x+25-y}\right)-\frac12 \\ =&\frac12\left(\frac{(25+x)(50-x-y)+(25-x)(50+x+y)}{(50-x-y)(50+x+y)}-1\right) \\ =&\frac12\left(\frac{50^2-2x(x+y)}{50^2-(x+y)^2}-1\right) \\ =&\frac12\frac{(y-x)(y+x)}{50^2-(y+x)^2}\;, \end{align} $$

Now switch to independent variables $s=y+x$ and $d=y-x$ to obtain

$$ \frac12\frac{sd}{50^2-s^2}\;. $$

It's now almost immediate that the only stationary point is at $s=d=0$, and this is clearly not a maximum. Thus the maximum of the continuous problem must be at the boundary. Since the result is positive iff $s$ and $d$ have the same sign and in that case increases monotonically with the magnitude of either, the maximum of the discrete problem must also be at the boundary. If we arbitrarily choose the common sign of $s$ and $d$ to be positive, the maximal value of $d$ given $s$ is $50-s$, so the maximum along the boundary is the maximum of

$$ \frac12\frac{s(50-s)}{50^2-s^2}=\frac12\frac s{50+s}\;, $$

and this is clearly maximized for maximal $s$. The maximal value of $s$ consistent with the constraints is $49$, so the solution is $s=49$, $d=1$, or $x=24$, $y=25$.

Answer 2

Assume that we decide to put $50-r$ balls into urn $A$ and $50+r$ balls into urn $B$ where $r$ is between $0$ and $49$ inclusive. Furthermore we decide to put $s$ red balls into urn $A$ and $50-s$ red balls into urn $B$. The number of blue balls in urn $A$ will then be $50-r-s$, and the number of blue balls in urn $B$ will then be $r+s$. Since all four numbers of balls have to be nonnegative we obtain the conditions $$s\geq0, \quad s\leq 50-r,\quad s\leq 50,\quad s\geq -r\ .$$ As $r\geq0$ these conditions are fulfilled iff $0\leq s\leq 50-r$.

The probability $P$ to draw a red ball computes to $$P={1\over2}\ {s\over 50-r}+{1\over2}\ {50-s\over 50+r}\ .$$ Keep $r$ fixed for the moment. Increasing $s$ by one produces a $$\Delta P={1\over2}\Bigl({1\over 50-r}-{1\over 50+r}\Bigr)>0\ .$$ In order to maximize $P$ we should therefore give $s$ the maximal allowed value $50-r$. The resulting value of $P$ is then $$P={1\over2}\ {50-r\over 50-r}+{1\over2}\ {50-(50-r)\over 50+r}={1\over2}+{1\over2}\Bigl(1-{50\over 50+r}\Bigr)\ .$$ This is maximal when $r$ is maximal, i.e., if $r=49$, and this leads to $s=1$.

Therefore the optimal way to distribute the balls is putting one red ball into urn $A$ and all the other balls into urn $B$. The resulting probability $P$ of drawing a red ball is then about ${3\over4}$.

Answer 3

I've seen this mentioned in the context of job interview questions before.

The Gerrymandering solution was seen as correct.

There are probably other options, depending on how cheeky you're feeling.

For example:

If the urns are narrow, take advantage of serial correlation and tip the blue balls in first then the red on top. The probability of picking red is now significantly closer to one. Hey, they never said the contents would be randomly permuted?! So am I meant to put them in and then permute them myself rather than just pick randomly from the available (all or largely red) balls? I mean, my hand's made of meat, so I'd actually have to move them round by some sort of algorithm... and what's the seed? Oh, I picked that too, right?

OK, OK, maybe that's cheating... but do you want a candidate who thinks about stuff like serial correlation or someone who thinks everything is independent?! Blah, etc.