Test Your Intuition (18): How many balls will be left when only one color remains?

(Thanks to Itai Benjamini and Ronen Eldan.) Test (quickly) your intuition:  You have a box with n red balls and n blue balls. You take out balls one by one at random until left only with balls of the same colour. How many balls will be left (as a function of n)?

1) Roughly  εn for some ε>0.

2) Roughly \sqrt n?

3) Roughly log n?

4) Roughly a constant?

About these ads
This entry was posted in Probability, Test your intuition. Bookmark the permalink.

25 Responses to Test Your Intuition (18): How many balls will be left when only one color remains?

  1. Anthony says:

    roughly 4?

  2. Imre Polik says:

    I’d say a constant.

  3. taips says:

    1) I’d understand “roughly” as pertaining to the Mean or Median. My guess is either sqrt or log, but I don’t know which.

  4. Ross Snider says:

    2, I’m thinking of random walks.

  5. jgf1123 says:

    Roughly constant. In particular, roughly 2. Play the process backwards.

  6. Roughly constant. Similar to coupon collectors problem or a 1-d random walk?

  7. This reminds me of a homework problem from one of Moni Naor’s classes: you play a game with a randomly shuffled deck of cards. In each step, you can either take out the next card and look at it or stop (and you automatically stop when there is only a single card left in the deck). If the color of the next card is red you win $1 and otherwise you lose $1. What is the highest expected reward you can get (using any strategy)? Of course you can stop immediately and then the expectation is 0, but can you do better?

    • Reshef Meir says:

      It seems to have something to do with Catalan numbers. Suppose the deck has 2n cards.
      Consider the following strategy: pool cards until you are holding more blacks than reds (meaning that the next card is more likely to be red). Then stop.
      - if you stop before the last card, you win w.p. of at least n/(2n-1)
      - if complete the deck you lose (since the last card is black).
      - we can think of black and red cards as moving right and up on a grid, respectively.
      - having at least as many reds as blacks corresponds to remaining below the diagonal.
      - the probability of reaching the end (and lose) is C(n) / (2n choose n) = 1/(n+1)
      Thus the expected value is
      (-1) 1/(n+1) + (+1) n/(n+1) n/(2n-1) –> 1/2 as n tends to infinity. (about 0.454 for n=26)

      If the deck is large you can probably wait for a better before stopping,

      • Austin says:

        In your expected value computation, you’re missing the case where you get a -1 payout by guessing (wrong) before the end of the deck is reached. When you include this, the expected payout should become zero.

    • Grant says:

      Nice problem. Did not expect that answer (assuming I did not mess up). I used induction, but there must be a more intuitive way.

      • You can solve by induction, and the answer is 0 either way. But the very elegant way Moni proved it for us (which I find very related to the way this post should be answered) is the following:

        Consider the following game: you play a game with a randomly shuffled deck of cards. In each step, you can either take out the next card and look at it or stop (and you automatically stop when there is only a single card left in the deck). Now one opens *the last card in the deck* (rather than the next card). If the color is red you win $1 and otherwise you lose $1. Note that in this case, the strategy of the player makes no difference – your reward is always determined by the color of the last card. So here the payoff is clearly 0. On the other hand, one can convince himselve rather easily that the payoff in both games (for each specific strategy) is the same. Simply, conditioned on all of the cards you already saw, the color of the next card and the color of the last card have the same probability distribution. And thus the payoff for the original game is 0 too.

  8. Andy D says:

    Nice. :)

    How about this: you are given a box that is one of two kinds, each with 50% odds:

    A) n blue balls, n red balls;

    B) the maker flipped an independent coin to determine the color of each of the 2n balls.

    Let t be a fixed value. You draw t balls without replacement and try to guess which of the two types you were given. What does your success probability p look like as a function of t? E.g., roughly when do you hit p > .99?

  9. placeoflight says:

    This problem has absolutely nothing to do with intuition, but rather abstract reasoning.

  10. Austin says:

    Another vote for a constant (which is 2 in the limit). I find it easier to think about the question, “How many balls of a single color will you draw at the beginning before the first ball of the other color appears?” But this is symmetrically equivalent to the original question.

  11. Leonard Schulman says:

    Omer, I learned the same great game from Abhiram Ranade years ago. It is a nice way of skirting the martingale stopping theorem.

  12. Ivan Ip says:

    I actually plot the distribution from n=1 to 500…….. the average number of balls left fits EXACTLY as the square root of n……..

  13. anonymous says:

    if my code runs correctly, it suggests that that number of balls left obeys a geometrical distribution with the parameter p equal to one half (thus not depending on n).

  14. Steve Rodondo says:

    Constant because as we draw balls we expect to have the same number of balls of each color. So we would have the same ending whether we start with n red and n blue or n/2 red and n/2 blue.

  15. hull says:

    It is not a constant, it is not log n;
    Roughly \sqrt n?

    public static void main(String[] args) {
    int testCount = 100;
    int boxSize = 10000;
    Random rand = new Random();
    for(int i=0; i<testCount; i++){
    int size = rand.nextInt(boxSize) + 1; //random number in [1,..,boxSize]
    int red = size, blue = size, left;
    while(true){
    if(rand.nextInt()%2 == 0){
    red–;
    }else{
    blue–;
    }
    if(red == 0){
    left = blue;
    break;
    }
    if(blue == 0){
    left = red;
    break;
    }
    }
    System.out.println(
    "test " + i + " N=" + size + " left=" + left +
    " SQRT(N)=" + (int)Math.sqrt(size) +
    " LOG(N)=" + (int)(Math.log(size)/Math.log(2)));
    }
    }

    • Your code seems to assume that your random number mod 2 says whether the ball is red or blue, in which case your sqrt(n) is correct. But that would be for a problem like “flip coins until you have either n heads or n tails. What is the expected value of |heads – tails| at that time?”

      If you change your code to pick a random integer from 1 through red+blue, and to decrement red if the random integer is <= red, you should see the result staying near 2 even as the number of balls increases. A way to see that is that if the number of, say, red balls gets down to 1 when the number of blue is still big, the chances of getting that last red ball is pretty low, so you tend to get rid of a bunch of blue ones before finally getting that last red one.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s