Gerrymandering urns (redux)

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}. - our p(x,y) won't have a local maximum at the gerry-mandering solution, as the non-integer "solutions" (\epsilon, 0) give \[ p(\epsilon, 0) = \frac 12 + \frac 12 \cdot\frac{50-\epsilon}{100 - \epsilon} \to \frac 34 > p(1, 0), \quad \epsilon \to 0 The problem is, that calculus will in general not find the integer maximum, you can't cut the balls in parts. – martini Oct 24 '12 at 7:47 Indeed. I was going to edit the question to only allow integer solutions. The calculus bit is in no way meant to distract from the fact that I have no idea how to solve this kind of question, and it is probably a red herring. :) – fg nu Oct 24 '12 at 7:49 In the second derivative, the first denominator should be -x^*. – joriki Oct 24 '12 at 11:39 @joriki Edited, thanks. – fg nu Oct 24 '12 at 11:43 3 Answers 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. - 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}$.

-
Thanks for your answer Christian. Both your answers were useful (and correct), but Joriki got in ahead of you based on timestamp. :) –  fg nu Nov 22 '12 at 7:56

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.

-
"take advantage of serial correlation " -- you can't because you are explicitly told that sampling from the jars it at random in the statement of the problem -- "Then you pick a jar at random and pick a ball at random.". If certain balls in a jar had a higher probability of being picked, that would no longer be random sampling. In answer to your second question, although I heard this question elsewhere, if this did come up in an interview, I'd rather a candidate that thought about the given situation and did not try to shift the goalposts. –  fg nu Oct 25 '12 at 2:17
Imagine a practical situation in which two schemes were carried out. Scheme A) was pure gerrymandering. Scheme B) was gerrymandering plus pouring the blue balls in an urn first then the red on top. Which scheme do you think people would pick more red balls under if told to pick a jar at random and then a ball at random? I know which I'd put money on. –  conjectures Oct 25 '12 at 20:11