Of Bags and Balls

[Yoruichi-san]

Perpetuating the puzzle propagation:

There are 5 bags, of which one contains 4 blue balls, one contains 3 blue balls and 1 red ball, one contains 2 blue balls and 2 red balls, one contains 1 blue ball and 3 red balls, and the last contains 4 red balls. You do not know which bag has which distribution.

You will be allowed 10 draws, each from any bag of your choosing, and your goal is to draw as many of the same colored balls as possible.

What is your play (by which, I am assuming you're a probabilistic optimalist, like me )?

[bonanova]

Draw one ball from each bag to determine color. WOLOG it's blue.

Discard the bags that gave red balls.

Draw from a blue bag until a red ball is drawn.

Draw from another blue bag until a red ball is drawn.

...

Stop after the 10th ball is drawn.

This algorithm gives a minimum of 4 and a maximum of 8 balls of one color.

On average, 6.95...

[bonanova]

Puzzle seems to break into two parts: [1] pick a color [2] get as many of them as you can.

Template:

1. draw some balls and choose the majority color
   
2. draw from bags as long as you get that color then switch bags.
   

My first post suggested drawing one from each of the 5 bags.

The drawback is that you almost always get a 3-2 split: rarely 4-1.

So you almost always start out with 2 losing balls.

That approach gets you 6.95... of a color; not shabby, but not best.

I tried reducing the losers in step [1] to zero: draw a ball from 1 bag, and pick that color.

But that approach doesn't eliminate the bag with 4 losing colors, and gets you only 6.16... balls of one color.

A compromise is to draw a ball from each of 4 bags.

Half the time you get either a 3-1 or 4-0 split; in these cases you get 7.56... of one color.

So here's my algorithm:

Draw a ball from each of four bags.

1. If you get a 3-1 or 4-0 split:
   Disregard the fifth bag. This usually eliminates the bag with 4 losers.
   Draw balls from one of the four bags until you get the wrong color, then switch bags.
   Continue until 10 balls are drawn. Expectation: 7.56... balls of one color
   
   
2. If you get a 2-2 split, draw a ball from the 5th bag to break the tie.
   Disregard the two bags that gave the minority color. This always eliminates the bag with 4 losers.
   Draw balls from one of the three winning bags until you get the wrong color, then switch bags.
   Continue until 10 balls are drawn. Expectation: 6.95... balls of one color.
   

Overall expectation: 7.25... balls of one color.

[EventHorizon]

Draw one ball from each bag to determine color. WOLOG it's blue.

Discard the bags that gave red balls.

Draw from a blue bag until a red ball is drawn.

Draw from another blue bag until a red ball is drawn.

...

Stop after the 10th ball is drawn.

This algorithm gives a minimum of 4 and a maximum of 8 balls of one color.

On average, 6.95...

Just thought I'd point out that those 4's are actually 6's in a red disguise.

[bonanova]

Just thought I'd point out that those 4's are actually 6's in a red disguise.

I think I will resign as moderator, my brain is definitely calcifying.

Good catch.

Edit:

There is no change to three decimal places in the two chosen scenarios.

A slight increase of 0.08 in the third.

i.e. it almost never is 4.

Pick a ball from each of three bags.

If they are of the same color, ignore the other two bags and proceed as previously described.

If they are 2-1, draw a ball from a 4th bag and proceed as previously described.

This should boost the overall average.

I might compute it later.

[bonanova]

The simulation had a counting error

Describing the algorithm as it was simulated:

1. Draw a ball from each of three bags. If the split is 3-0, place those three bags first.
   
2. If the split is 2-1, draw a ball from a 4th bag.
   

• If the split is 3-1, place the three majority color bags first and the minority color bag last
  
• If the split is 2-2, draw a ball from the 5th bag. Place the three majority color bags first.
  

We now have drawn 3 [3-0], 4 [3-1] or 5 [3-2] balls, and used the result to order the bags for further drawing.

Starting with the first bag,

Draw balls until the bag is empty or a minority color ball is drawn. Move to next bag.

Continue until 10 balls are drawn.

Result: 6.89 balls of one color

If we initially draw 4 or 5 balls to order the bags, we get 6.82 balls of one color

If we initially draw 5 balls to order the bags, we bet 6.40 balls of one color.

[MikeD]

Just a though:

When taking from the first three bags if it:

3 - 0 we would ignore the forth bag.

but if

it 2 - 1 then we should swop the odd colour bag with the forth bag.

Then we take one from each again

if its 3-0 then disguard the last bad (would have be the forth)

if is 2-1 then disguard the bag with the wrong colour)

if its 1-2 then disguard the two bags with the wrong colour.

If we have one bag left by now, take the two remaining balls, and take one for each of the other two bag.

If we have two bags the take two from each bag.

(I am rushing here, hope i didnt make a mistake, i haven't worked out the results yet, but i think this would be the best play.)

I will get back later, to look more closerly at it.

[phil1882]

i did the worst strategy i could think of and still got a decent result.

pick from the same bag untill ether the bag runs out or you have the same number of red/blue.

wash rinse repeat.

this gives me roughly 6.3 on average. although short of bonanova's solution by a fair amount, roughly 10%, i'm surpized it did as well as this.

[bushindo]

Perpetuating the puzzle propagation:

There are 5 bags, of which one contains 4 blue balls, one contains 3 blue balls and 1 red ball, one contains 2 blue balls and 2 red balls, one contains 1 blue ball and 3 red balls, and the last contains 4 red balls. You do not know which bag has which distribution.

You will be allowed 10 draws, each from any bag of your choosing, and your goal is to draw as many of the same colored balls as possible.

What is your play (by which, I am assuming you're a probabilistic optimalist, like me )?

Here's a play,

We first need to develop some notations to represent any state of the game. Let B_i represent bag i, where i goes from 1 to 5. Let c_i represent the color on the i-th draw, and let m_i contain information about which bag was chosen on the i-th draw. For instance, if we choose bag 2 on turn 1 and it turned out that we got a blue ball, then c₁ = Blue and m₁ = B₂. The state of the game at turn i can be represented by

C_i = [ c_i, …, c₂, c₁ ]

M_i = [ m_i, …, m₂, m₁ ]

What we need to do next is to develop a function for evaluating the chance of drawing a particular color from bag j at turn i given the game state C_i and M_i. That is, we want the probability function

P( B_j = color | C_i, M_i )

For example, at the beginning of the game, P( B_j = Blue | C₀, M₀ ) is obviously equal to 1/2 for all bags. If we choose bag 1 on the first turn and got a Blue, then

P( B₁ = Blue | C₁ = {Blue}, M₁ = {B₁} ) = 0.6666667

P( B_j = Blue | C₁ = {Blue}, M₂ = {B₁} ) = 0.4375 for j = 2, 3, 4, 5

So, let's assume we have the probability function for now (see the end for derivation), the algorithm is as follows

1) At the first turn, obviously just pick any random bag.

2) At turn i, we look at the drawn colors so far, and we want to pick the color = mode(C_i), i.e., the color that has appeared most often. We evaluate the probability function above for each bag and the most frequent color. That is, we evaluate

P( B_j = mode(C_i) | C_i, M_i ) for j = 1, 2, …, 5

3) Pick the bag that has the highest probability of drawing the most frequent color. Repeat until the end of the game.

**********************************************

Computation of P( B_j = color | C_i, M_i )

So, let's talk about the computation of the probability function. The main idea is as follows, we have 120 possible permutations of the 5 bags. We will simply keep track of a probability estimate of each of those 120 states, and update the likelihood of each permutations when we get new information. The following is going to be done in pseudo code,

Let A be a 120x5 matrix of permutations, where the bags are labelled from 1 to 5. For instance, the first 3 permutations may be represented as

	 [,1] [,2] [,3] [,4] [,5]

[1,] 1 2 3 4 5

[2,] 1 2 3 5 4

[3,] 1 2 4 3 5

Let P_i be a 120x1 vector of the probability of the permutations at time i. For instance, at the beginning of the game, it is easy to see that P₀ is a constant vector with each element being equal to 1/120 (all permutations are equally likely). Let R_i be a 120x5 matrix of the number of Red balls within each bag and within each permutation at turn i, and let B_i be a 120x5 matrix of the number of Blue balls. For instance, at the beginning of the game, the first 3 rows of R₀ and B₀ corresponding to the 3 permutations of A above are

Red matrix


	 [,1] [,2] [,3] [,4] [,5]

[1,] 0 1 2 3 4

[2,] 0 1 2 4 3

[3,] 0 1 3 2 4

Blue matrix


	 [,1] [,2] [,3] [,4] [,5]

[1,] 4 3 2 1 0

[2,] 4 3 2 0 1

[3,] 4 3 1 2 0

At turn i, without loss of generality let's assume that c_i = Blue, we can update the parameters P_i, R_i, and B_i as follows,

T = P_i-1 * B_i-1[ , m_i ]/ ( B_i-1[ , m_i ] + R_i-1[ , m_i ] )

P_i = T/sum(T)

Note that the above vector multiplications and division are done element-wise. We then need to update the R_i-1 and B_i-1 matrix to reflect the fact that we took out one blue ball

R_i[ , m_i ] = R_i-1[ , m_i ]

B_i[ , m_i ] = B_i-1[ , m_i ] - 1

If we get negative values in B_i, we'll have to set those to 0.

Finally, the probability function can be computed as

P( B_j = Blue | C_i, M_i ) = sum( P_i * B[ , m_i ]/ ( B[ , m_i ] + R[ , m_i ] ) ).

The case for Red color being drawn can be computed analogously.