Optimizing a probability for marbles in two buckets

Question

There are 25 red marbles and 25 blue marbles divided between two buckets. You

1. select a bucket uniformly at random
2. select a marble from that bucket uniformly at random

Find initial arrangements of marbles into the buckets in order to maximize $\mathbb P(\text{marble picked is red})$.
Source (this problem also appears as Question 4.22 in Heard on the Street, however the author's solution is mere handwaving).

Label the buckets and let $R_1$, $B_1$ denote respectively the number of red and blue marbles in Bucket 1. The probability under consideration is $$\frac 12 \Big(\frac{R_1}{R_1 + B_1} + \frac{25-R_1}{50-R_1 - B_1} \Big).$$

The subsequent optimization problem is to maximize this quantity under the constraints that $R_1\in \{0,\ldots, 25\}$, $B_1\in \{0,\ldots, 25\}$.

My question is: What's the most efficient way of solving this maximization problem using only pen and paper (e.g. during an interview) ?

The Mathematica command

Maximize[{1/2*(r/(r + b) + (25 - r)/(50 - r - b)), 
  Element[r | b, Integers] && 0 <= r <= 25, 0 <= b <= 25}, {r, b}]

yields a unique solution $R_1=1$, $B_1=0$, with optimal probability $\approx 0.74$.

Relaxing the integer constraints I think there should be a way using Lagrange multipliers. Is there a more efficient way ?

I'm also open to more clever solutions that do not involve solving such an optimization problem.

Answer 1

In the extreme case where bucket 1 contains 25 red and 25 blue, the probability of picking a red is $\frac 12$. In the other extreme case where bucket 1 is empty, this probability is also $\frac 12$.

Let $f(r,b)= \frac{r}{r + b} + \frac{25-r}{50-r - b}$. Assuming $(r,b)\notin \{(0,0),(25,25)\}$, $f(r,b)$ is twice the probability under scrutiny. The sum $S:=r+b$ occurs twice in the expression of $f$; we are interested in the case where $0<S<50$.

When $S=25$, note that $f(r,b) = 1$ and the probability is $\frac 12$.

If $b>0$, note that $f(r+1, b-1) - f(r, b) = \frac{50-2S}{S(50-S)}$. Hence swapping a blue ball for a red ball in bucket $1$ increases strictly the probability as long as $S<25$.

Assume now that $0<S<25$. Optimality dictates $b=0$, hence $r>0$ and $f(r,b) = 1+\frac{25-r}{50-r} = 2-\frac{25}{50-r}$, which decreases strictly with $r$, and is thus maximal for $r=1$. Note that $f(1,0) \frac{73}{98}\approx 0.745 > \frac 12$ .

Assume finally that $25<S<50$. Exchanging the roles of buckets 1 and 2, we're back to the previous case.

Having $1$ red and $0$ blue in bucket $1$ is therefore optimal. The maximal probability is $\frac{73}{98}\approx 0.745$.

Answer 2

You either have probability of exactly $1/2$ to get red from any bucket, or you have probability greater than $1/2$ from one, and less from other (or you left one bucket empty and broke the problem, but lets assume we can't do that).

Best probability greater than $1/2$ you can get is of course $1$. Best probability lower than $1/2$ you can get is $\frac{24}{49}$ - there will be at least one more blue marble than red marbles, and it's best to have exactly one more if possible. After that, it's best to have as many marbles in this bucket as possible, and $49$ is max ($50$ means we already are at $1/2$ probability).

And we can achieve both simultaneously. So, any solution different from yours is either $1/2$ split (which is worse), or has both lucky bucket not better than your lucky bucket, and unlucky bucket not better than your unlucky bucket - thus isn't better than yours.