Painting $n$ balls from $2n$ balls red, and guessing which ball is red, game

Question

The game

Lucy has $2n$ distinct white colored balls numbered $1$ through $2n$. Lucy picks $n$ different balls in any way Lucy likes, and paint them red. Lucy then giftwrap all the balls so that it is impossible to tell its color without opening its wrapping. Lucy does this before offering any of the balls to Alice.

Alice would like to get one of the red balls. Alice doesn't know which balls are painted red. Lucy will offer Alice the balls one by one, starting from ball $1$, until ball $2n$. Upon being offered each ball, Alice may either take the ball or pass it. If Alice takes the ball, Alice open the wrapping. If it is red, Alice takes it and the game ends -- otherwise, Alice will continue to be offered the remaining balls (unless all balls has been offered). If Alice pass the ball, the ball remains wrapped and thus Alice does not know the color of the ball, and Alice will continue to be offered the remaining balls. Note that it is possible for Alice not to get any red ball -- for example, if Alice choose not to take any ball.

Alice's goal is to

1. Obtain a red ball with probability at least $1 - 1/n$ (that is, it is okay for her not to get a red ball as long as this probability does not exceed $1/n$), and
2. Minimize the expected number of balls Alice take.

Lucy's goal is the complete opposite of Alice, that is:

1. If it is possible for her to make Alice unable to obtain a red ball with probability at least $1 - 1 / n$, she will do so.
2. Otherwise, maximize the number of balls Alice take in average (that is, the expected number of balls Alice take).

Question

What is the optimal strategy for Alice? What is the expected number of balls that Alice would take in the optimal case?

Example

When $n = 2$, Alice's goal is to obtain a ball with probability at least $1/2$. Here's an example strategy, which is provably optimal:

Decide which one of the four balls to open at random, and open that and only that ball. Clearly the probability that the opened ball is red is $1/2$, and the expected number of balls opened is $1$.

My work

Let $X$ be the expected number of balls Alice would take if both players play optimally.

Upper bound on X

I can proof a $O(\log n)$ upper bound on $X$ by letting Alice select $\log_2 n$ balls at random to open. The probability of Alice not finding any red ball is at most $2^{-\log_2 n} = 1/n$. Lucy would then paint the last $n$ balls red, and we have $X = O(\log n)$.

Lower bound on X

Edit: As domotorp pointed in chat, the proof in the pdf below for my lower bound is wrong because I wrongly use the assumption that E(x) and E(y) were independent. I don't see any immediate fix to the proof, so I will try to work on this again.

I proven a $\Omega(\log \log n)$ lower bound on $X$ in this pdf. I used a different terminology in the pdf: instead of having $2n$ balls, $n$ colored red, we have $2n$ bins, $n$ of which has ball inside.

Motivation

In the distributed systems settings, a rather common approach to guarantee that an algorithm is fault tolerant is by utilizing a bound on the number of possible failures. One of my supervisor's paper's algorithm works by utilizing a cheap algorithm that runs very fast if the number of failures is very small. To accommodate for larger number of failures, he decides to run this multiple times -- if with high probability (at least $1 - 1/n$) one of these runs have very few errors, then this algorithm will be much faster than the previously known one. At the moment, the paper utilize the $O(\log n)$ upperbound, but we wondered whether this bound is optimal.

A very nice implication is that if a strategy with expectation lower than $O(\log n)$ is found for this game, then the algorithm's complexity in the paper will decrease correspondingly. However, I strongly believe that it is more probably to prove $\Omega(\log n)$ rather than $o(\log n)$.

Answer 1

Here is a sketch of an argument by my colleague Jim Roche of an $\Omega(\log n/\log \log n)$ lower bound. The basic idea is that Lucy chooses randomly between two strategies, one of which puts all the red balls early (thereby forcing Alice to open some number of the early boxes), and the other of which puts a lot of the red balls late (thereby forcing Alice to open some number of the late boxes).

Specifically, with probability 1/2, Lucy distributes the $n$ red balls randomly among the first $n(1 + 1/\log_2 n)$ boxes. With probability 1/2, she distributes $n/\log_2 n$ red balls randomly among the first $n(1 + 1/\log_2 n)$ boxes, and puts the remaining red balls at the very end. We now give a lower bound on how many boxes Alice expects to open under any randomized strategy that succeeds with probability at least $1-1/n$.

The argument that follows is slightly imprecise because it treats the probabilities that the boxes contain red balls as independent, whereas they are actually dependent since Lucy is constrained to paint exactly $n$ balls red. However, the error terms are negligible, and the argument is clearer if we ignore the dependencies.

For any constant $C$, define $P_C$ to be the probability that Alice chooses at most $(C\ln n)/\ln\log_2 n$ of the first $n(1+1/\log_2 n)$ boxes. Then we must have $${1\over n} \ge \Pr\{\hbox{Alice fails}\} \ge {P_C\over 2} \left({1\over\log_2 n} \right)^{(C\ln n)/\ln\log_2 n}, $$ so $$P_C \le {2\over n}\exp (C\ln n) = 2n^{C-1}. $$ In particular, for $C=1/2$, the probability that Alice chooses at most $(\ln n)/2\ln \log_2 n $ of the first $n(1+1/\log_2 n)$ boxes is at least $2/\sqrt n$. Therefore, with probability 1 as $n\to\infty$, Alice must examine at least $(\ln n)/ 2 \ln \log_2 n$ of the first $n(1+1/\log_2 n)$ boxes.

But remember that with probability 1/2, Lucy places only $n/\log_2 n$ red balls among the first $n(1+1/\log_2 n)$ boxes. If she does so, then the probability that Alice's first $(\ln n)/2 \ln \log_2 n$ looks uncovers a red ball is upper-bounded by the union bound $$\left({\ln n\over 2\ln\log_2 n}\right)\left({1\over \log_2 n}\right),$$ which approaches zero as $n\to\infty$. Therefore, with probability at least $1/2 -\epsilon$, Alice must examine at least $(1/2 - \epsilon)(\ln n)/\ln \log_2 n$ boxes. This establishes the $\Omega(\log n/\log \log n)$ bound.

Answer 2

Here is a $\Omega(\log n)$ bound for $X$ if Alice follows a very restricted strategy. I think this shows well why this might be the bound and the difficulty of the problem.

Suppose Alice decides for every ball $i$ whether she takes it or not with probability $p_i$ independently (if she has not yet found a red ball earlier). If $i\le j$, then $p_i\le p_j$, otherwise Lucy could swap the $i$th and $j$th ball and increase $X$. Denote by $t$ the largest $i$ for which $p_i< \frac{\log n}{100n}$. Lucy will put the red balls to the first $\min(t,n)$ bins and the last $n-\min(t,n)$. It is very likely that during the first $t$ steps Alice won't find any red balls. If $t> n$, then Alice's chance of failure is more than $1/n$. If $t\le n$, then Alice will (whp) ask $\Omega(\log n)$ white balls in the next $n$ steps.

Unfortunately this argument only works for this very special version, but maybe some parts of it are useful for the general case too.

Answer 3

Consider solutions of this type: Choose a set $X$ of $k$ balls according to some probability distribution $F$ on the set of all $\binom{2n}{k}$ $k$-sets. Then as the balls are presented, look at those which which are in $X$, stopping if any is red.

Now, for any position $Z$ of the $n$ balls, let $P(Z,F)$ be the probability that at least one of the $k$-balls is red. The problem (or something like the problem ;) is to find an $F$ that maximises the minimum of $P(Z,F)$ over all $Z$.

I claim that the maximum is achieved if $F$ is the uniform distribution $F_U$. Because: for any fixed $F$ the average of $P(Z,F)$ over all $Z$ is equal to $P(Z,F_U)$, by symmetry (randomizing which balls to take does the same job as randomizing which balls to paint, and $P(Z,F_U)$ is independent of $Z$). Therefore, either $P(Z,F)=P(Z,F_U)$ for all $Z$ or else some $Z$ has $P(Z,F)\lt P(Z,F_U)$.

So, for each $k$, the best way to select $k$ balls is uniformly at random. One can now do the calculation to arrive at the optimum $k$ (around $\log_2 n$).

The next question is whether all strategies have this general form. One could consider a sequence of choices that change during the play. However, since the play stops immediately a red ball is discovered, one can just imagine the play in advance and decide which choices will be made when the time comes to make them. So it is the same as choosing positions in advance. I'm not sure if this part of the argument is rigorous.

WITHDRAWN: See the comments.

Answer 4

Edit: I make the mistake below of proving a lower bound on the maximum number of boxes Alice must open, not the expected number. So this does not answer the question.

.

I think this sort of thing is often argued with Yao's principle (which is really just von Neumann's minimax):

$$ \max_{\text{randomized algorithm}} \min_{\text{sequence}} \mathbf{E}[\text{performance}] \leq \min_{\text{distribution on sequences}} \max_{\text{deterministic algorithm}} \mathbf{E}[\text{performance}] .$$

It is a two-player game between Alice, who chooses the (randomized) algorithm, and Lucy, who chooses the input sequence. In this case $\mathbf{E}[$performance$]$ is the probability that Alice finds a red ball.

To apply it, we just need to upper-bound the right-hand side. We do that by, not actually taking the minimum over all possible distributions on sequences, but just finding one distribution on sequences that is bad for all deterministic algorithms that Alice could employ.

So here's the idea. First, suppose that an algorithm can only open $o(\log n)$ boxes. Now, if we just find a single distribution on input sequences such that every deterministic algorithm has $\Pr[$find red$] < 1-1/n$, then we are done: The minimum on the right-hand-side is certainly less than $1-1/n$, since we have found an example where it is less than $1-1/n$. Then Yao's principle says that any randomized strategy of Alice performs worse than $1-1/n$ on its worst-case input distribution. (That is, on the worst-case strategy of Lucy.)

So concretely, I think we can apply it here by letting Lucy choose the distribution of sending the boxes in uniformly random order. Then for any deterministic algorithm of Alice's that opens $k$ boxes, the probability that none are red is

$$ \left(1-\frac{k}{2n}\right) \left(1-\frac{k}{2n-1}\right) \cdots \left(1-\frac{k}{n+1}\right) . ~~~~~~~~~~~~~ (1) $$ Why is this? Fix the $k$ boxes Alice will open (remember we are only worried about deterministic Alices). Now imagine Lucy randomly choosing the locations of the red balls one by one. The first has $2n$ choices, so a probability $1-k/2n$ that is does not choose one of our $k$ boxes. The second has $2n-1$ choices, conditioned on the choice of the first, so a probability $1-k/(2n-1)$ that it does not choose one of our $k$ boxes. And so on for the $n$ red balls. The important thing is that we can't assume that each of the $k$ boxes independently has a red ball with probability $1/2$, since they aren't independent (if one box doesn't, the others are more likely to). I think you might make this mistake in your statement of the upper bound, but if so I'm sure it's easily fixed.

Anyway, I don't know immediately how to argue that (1) is at least $1/n$ when $k < o(\log n)$, but it should be true, since (1) is at least

$$ \left(1-\frac{k}{n}\right)^n \approx e^{-k}.$$

(The approximation has the inequality going the wrong way, so we don't immediately get the proof.)

Edit. If there is anything unclear, please let me know. I probably did a poor job explaining, but this is a primary technique for lower bounds for online/randomized algorithms and I think it gives what you want pretty simply.