15
$\begingroup$

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)$.

$\endgroup$
  • 1
    $\begingroup$ Maybe you can change terminology a bit: There are $2n$ distinct (numbered) items. Lucy paints half of them red. Alice wants to find a red object. Usually, a box can contain arbitrary many balls, but for 0 or 1 balls only, it is easier to use color as a marker. $\endgroup$ – Per Alexandersson Oct 22 '14 at 13:04
  • $\begingroup$ Good point. I've edited it and the answer below. $\endgroup$ – Irvan Oct 22 '14 at 14:23
  • $\begingroup$ Can you clarify if this is correct? You want a strategy for Alice such that, for every permutation of the boxes, $\Pr[$find a red$] \geq 1-1/n$. $\endgroup$ – usul Oct 22 '14 at 17:02
  • $\begingroup$ That's a necessary condition, but not sufficient. In addition to the condition, we also want the strategy to minimize the expected number of balls taken. So, if we use Yao's principle, $E[\text{performance}]$ would be the expected number of balls taken, subject to the condition you mentioned. $\endgroup$ – Irvan Oct 23 '14 at 4:37
  • 1
    $\begingroup$ @domotorp: On first comment: Yes, the balls are numbered -- ball number $i$ will be the $i$-th ball offered to Alice. However, she has to decide the colors of all balls before Alice is offered any ball (so she cannot change her strategy depending on whether or not Alice takes the first ball, for example). It can be assumed that they pick their strategies independently -- in particular for it to be a Nash equilibrium, no matter which strategy Alice decides to execute, the expected number of balls opened would still be the same. $\endgroup$ – Irvan Oct 26 '14 at 14:16
8
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Beautiful answer! I've been trying to compute whether the corresponding Alice strategy is $o(\log n)$: open $\log n / \log \log n$ boxes amongst the first $n(1 + 1/\log n)$ boxes, and open $\log n$ on the remaining boxes (since we the expected boxes we have to open in the worst case have to be $\Omega(\log n)$). This boils down to whether it is possible to generate a scenario in which (1) the probability that Alice goes to the remaining boxes is constant and (2) we placed a constant fraction of the red balls amongst the first set of boxes. This seems unlikely. $\endgroup$ – Irvan Nov 1 '14 at 8:45
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Note: I changed the terminology. Instead of boxes containing balls, now we have $2n$ balls, $n$ are colored red. I don't think the solution of this form is a nash equilibrium. If Lucy paints the balls completely at random, then the expected number of balls Alice take would be $O(1)$ (sum of geometric series with parameter $1 / 2$). On the other hand, if Lucy know Alice takes $\log_2 n$ items at random, then instead of painting the balls arbitrarily, she would paint the last $n$ balls instead. I think this implies that the expectation and $k$ may be different. $\endgroup$ – Irvan Oct 22 '14 at 14:29
  • $\begingroup$ @Irvan: I fixed your edits. I see that now that my solution is for the different problem where Alice can choose the order of looking at the boxes she selected. So I withdraw the solution. Incidentally the powers of 2 you talk about are not exactly that; it is sampling with replacement. I assume you are speaking approximately. $\endgroup$ – Brendan McKay Oct 22 '14 at 15:10
  • $\begingroup$ It was supposed to be an upper bound, not exactly. I've fixed that. $\endgroup$ – Irvan Oct 22 '14 at 15:17
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But $k$ is not equal to the expected number of boxes opened, right? I mean, if Lucy decides to distribute the balls uniformly, then even if we set $k = n$ (which means, we open every box), then the expected number of boxes opened would be $O(1)$. The main difficulty I've encountered while trying to solve this problem is to find a distribution that guarantees that the expected number of boxes opened by Alice is large conditioned that Alice would like to succeed with probability at least $1/n$. $\endgroup$ – Irvan Oct 23 '14 at 4:31
  • $\begingroup$ You're right, I was treating $k$ as the maximum number of boxes, not the expected. $\endgroup$ – usul Oct 23 '14 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.