Maximize Magic Beans: Solve the 2 Bag Challenge!

[scalpmaster]

You have 2 bags of beans containing 10 beans each. In each bag, there 3 magic beans. How do you maximize the number of magic beans selected if you are allowed to pick 10 beans out of the 20 altogether? You can mix them if you want and do anything you want but cannot draw one at a time from each bag.
I.e. If you do not mix the bags and just pick anyone bag, you know you will get a minimum of 3 magic beans out of 10 but can you achieve more?
This is not a homework.

 

[scalpmaster]

This portfolio managment problem is related to picking the best 3 performing stocks from 2 different sectors. The problem is you won't know which 6 will perform best until end of the year but you are allowed to pick 10 from 20 and you want the portfolio to include as close to all 6 best as possible. Is there a way to optimize the selection process?
i.e. You can't draw one at a time to see if it is normal or not and then pick another from the other bag because you will only know whether it is a good stock at the end of the year.

 

[Stephen Tashi]

Are we allowed to use a "sequential decision process"? For example, on the first draw, pick a bean from bag A, if it is magic then draw the second bean from bag B. If not, draw the second bean from bag A. To define this strategy we would have to define what to do for the third, fourth... tenth draw and consider all possible sequences of results.

We also should define what "optimize" means. The optimum strategy for maximizing the expected number of beans drawn might have a high variance. As you pointed out, we can guarantee getting 3 beans (with zero variance) by picking all ten draws from one bag.

 

[scalpmaster]

Are we allowed to use a "sequential decision process"? For example, on the first draw, pick a bean from bag A, if it is magic then draw the second bean from bag B. If not, draw the second bean from bag A. To define this strategy we would have to define what to do for the third, fourth... tenth draw and consider all possible sequences of results.

We also should define what "optimize" means. The optimum strategy for maximizing the expected number of beans drawn might have a high variance. As you pointed out, we can guarantee getting 3 beans (with zero variance) by picking all ten draws from one bag.

No, you can't pick one at a time from each bag because you won't know its magic/good stock until end of the year. You have to select 10 stocks simultaneously out of 20 and optimize the selection process to trap if possible all 6 best performing stocks out of 10.

 

[Stephen Tashi]

OK, I understand that. This still leaves open the question of what "optimize" means.

 

[scalpmaster]

OK, I understand that. This still leaves open the question of what "optimize" means.

lower variance.

 

[Stephen Tashi]

lower variance.

Really? Or do you mean that if two strategies give the same expected number of magic beans then the one with lower variance is defined as better?

Or are we assuming that the expected number of magic beans produced by any imaginable strategy is 3?

 

[scalpmaster]

Really? Or do you mean that if two strategies give the same expected number of magic beans then the one with lower variance is defined as better?Or are we assuming that the expected number of magic beans produced by any imaginable strategy is 3?

Lower variance would be better for 2 strategies with the same expected no. but higher expected no. is given precedence over variance. i.e. If the method can give expected no. of 6, then the variance can be as high as it can be.

 

[Stephen Tashi]

If we believe he web, the mean of a hypergeometric distribution of magic beans is $n \frac{k}{N}$ where
$n$ is the number of draws
$k$ is the number of magic beans in the bag
$N$ is the total number of beans in the bag.

If we only consider strategies where you draw X beans from bag A and 10-X beans from bag B, the mean payoff of that strategy is
$X \frac{3}{10} + (10-X)\frac{3}{10} = 10\frac{3}{10} = 3$

Mixing all the beans in one bag and drawing 10 gives an expected payoff of
$10 \frac{6}{20} = 3$

Perhaps you have already worked this out. Have you looked at the formula for the variance of the hypergeometric distribution?

( Of course, one can think of more complicated strategies. Rigorously proving that 3 is the max payoff that can be attained using any imaginable strategy seems a formidable challenge. )

 

[scalpmaster]

Is this analysis correct?

Bag 1 P(x) = 3/10 Bag 2 P(x) = 3/10

You have 10/10 (100 %) chances to pick 3 beans if you just focus on 1 bag...

If you focus on 2 bags combined then you have P(x) = 6/20 = 3/10.

However, your prob. of picking the magic beans drops from 100 % to 50% or 10/20 chances of actually getting the beans or 1/2...

Then your prob. of picking the magic beans combined with your chances at picking the magic beans drop significantly...

P(A*B) = 1/2*3/10 = 3/20

If you try to pick out of both bags you only have a 15 % chance of picking three beans while if you just pick from 1 bag you have a 100 % chance of picking three beans.

 

[scalpmaster]

Have you looked at the formula for the variance of the hypergeometric distribution?

No, please tell me more on how to analyse the variance? Or more specifically, can you increase the variance and thus maybe increase the expected payoff?

 

[Dickfore]

If you pick from the first bag and you do not get a magic bean, then the probability of getting a magic bean from the first bag increases to $\frac{3}{9}$, while from the second bag remains $\frac{3}{10}$. Therefore, you should keep drawing from the first bag.

If, on the other hand, you selected a magic bean from the first try, then the probability for getting a magic bean from the first bag is $\frac{2}{9}$. When compared with $\frac{3}{10}$, you get:
$$2 \times 10 = 20, 3 \times 9 = 27, 20 < 27 \Rightarrow \frac{2}{9} < \frac{3}{10}$$
so you should switch the drawing from the second bag.

You should continue with a similar analysis in the remaining 9 turns.

 

[Stephen Tashi]

Is this analysis correct?

No, because you are computing probabilities base on random selection "with replacement". Also, if you want to do a mathematical analysis of "expected value" you need to use the mathematical definition of expected value. This definition involves more than a single probability.


Following the formula given in the wikipedia article: http://en.wikipedia.org/wiki/Hypergeometric_distribution

Let

$N$ = total number of beans in the bag
$n$ = number drawn, $0 < n \leq N$
$k$ = number of magic beans in the bag, $0 \leq k \leq N$
$V =$ variance of the number of magic beans drawn

Then
$V = n \frac{k}{N} \frac{N-k}{n} \frac{N - n}{N -1}$

If we draw independently from two different bags the variance of the total number of magic beans drawn is the sum of the variances of the numbers that are drawn from each of the bags.

Suppose we make n draws from bag A and 10-n draws from bag B.
Then the total variance is $V = n \frac{3}{10} \frac{7}{n} \frac{10-n}{9} + (10-n)\frac{3}{10}\frac{7}{10-n}\frac{10-(10-n)}{9}$

The variance from drawing 10 beans from a bag of 20 that contains 6 magic beans is
$V = 10 \frac{6}{20}\frac{14}{10}\frac{10}{19}$

 

[scalpmaster]

The variance from drawing 10 beans from a bag of 20 that contains 6 magic beans is
$V = 10 \frac{6}{20}\frac{14}{10}\frac{10}{19}$

Thanks. So the variance is a fixed number and can't be increased?

 

[Stephen Tashi]

Thanks. So the variance is a fixed number and can't be increased?

Fixed with respect to what? Yes, for one jar, it's fixed if we are given the number of beans in the jar, the number of magic beans in the jar and the number of draws.

If you look at the formula for the variance for drawing for two jars, it changes if you change n.

 

[bpet]

Aside: is Prob(6 found) maximized by taking 5 from each bag?

 

[D H]

If you pick from the first bag and you do not get a magic bean, ...

That is an illegal scheme per the rules of this problem. As I take it, the only allowed scheme is to pick some number n between 0 and 10 inclusive, then randomly draw n beans from bag A, 10-n beans from bag B all without looking. If this is correct, any allowed scheme will have an expected value of 3. So the question boils down to ...

OK, I understand that. This still leaves open the question of what "optimize" means.

We have one answer to this question, the OP's answer,

lower variance.

Other than your say-so, scalpmaster, (and it is your problem, so your say-so does have some weight), what makes this "optimal"? You are implicitly assuming a risk averse point of view. Given that all options have the same expected value, the option that maximizes the variance may well be seen as "optimal" to someone who is risk tolerant.

 

[scalpmaster]

Other than your say-so, scalpmaster, (and it is your problem, so your say-so does have some weight), what makes this "optimal"? You are implicitly assuming a risk averse point of view. Given that all options have the same expected value, the option that maximizes the variance may well be seen as "optimal" to someone who is risk tolerant.

So, how would You maximize the variance for one who is risk tolerant?

 

[Stephen Tashi]

As I take it, the only allowed scheme is to pick some number n between 0 and 10 inclusive, then randomly draw n beans from bag A, 10-n beans from bag B all without looking.

D H,

I have a more liberal interpretation. My interpretation would allow "crazy" strategies like "Pick 3 beans from bag A and 4 beans from bag B and put them in a third bag C. Draw your ten beans by picking 4 beans from bag A, 4 beans from bag B and 2 beans from bag C." Intuitively, no amount of remixing of the beans will improve the expected value, but I am very curious how one would rigorously prove that.

scalpmaster,

To maximize the variance of the two-bag strategy described above, use the formula for V and pick the value of n that makes V largest. I leave the arithmetic to you

 

[D H]

Following the formula given in the wikipedia article: http://en.wikipedia.org/wiki/Hypergeometric_distribution

Let

$N$ = total number of beans in the bag
$n$ = number drawn, $0 < n \leq N$
$k$ = number of magic beans in the bag, $0 \leq k \leq N$
$V =$ variance of the number of magic beans drawn

Then
$V = n \frac{k}{N} \frac{N-k}{n} \frac{N - n}{N -1}$

That second fraction on the right should be $\frac{N-k}{N}$ rather than $\frac{N-k}{n}$, resulting in

$$V = n \frac k N \frac {N-k} N \frac {N-n} {N-1}$$

If you draw nothing (n=0), the odds of winning are 0, with zero variance ("if you don't play you can't win"). The corrected formula yields a variance of zero for n=0 and for n=N.

Suppose we make n draws from bag A and 10-n draws from bag B.
Then the total variance is $V = n \frac{3}{10} \frac{7}{n} \frac{10-n}{9} + (10-n)\frac{3}{10}\frac{7}{10-n}\frac{10-(10-n)}{9}$

Corrected: $V = n \frac 3{10} \frac 7{10} \frac{10-n} 9 +<br /> (10-n) \frac 3{10} \frac 7{10} \frac {10-(10-n)} 9$

The variance from drawing 10 beans from a bag of 20 that contains 6 magic beans is
$V = 10 \frac{6}{20}\frac{14}{10}\frac{10}{19}$

Corrected: $V = 10\frac{6}{20}\frac{14}{20}\frac{10}{19}$

 

[D H]

D H,

I have a more liberal interpretation. My interpretation would allow "crazy" strategies like "Pick 3 beans from bag A and 4 beans from bag B and put them in a third bag C. Draw your ten beans by picking 4 beans from bag A, 4 beans from bag B and 2 beans from bag C." Intuitively, no amount of remixing of the beans will improve the expected value, but I am very curious how one would rigorously prove that.

Point taken. I too cannot see how this will change the expected value given that bags A and B have identical contents, but I too cannot see how to prove this rigorously.

I can see that these crazy strategies will change the variance compared to a simpler approach (e.g., choose n from bag A, 10-n from bag B).

 

[AlephZero]

Point taken. I too cannot see how this will change the expected value given that bags A and B have identical contents, but I too cannot see how to prove this rigorously.

The probability that each bean is magic remains constant at 0.3, independent of anything that you do with that particular bean.

So if you select 10 different beans, the expected number of magic beans is 3, whatever crazy strategy you use to select them.

 

[scalpmaster]

So if you select 10 different beans, the expected number of magic beans is 3, whatever crazy strategy you use to select them.

Expected no. remains 3 but if max variance can occasionally increase the no. of magic bean selected to be 5 or 6, that's good enough.

Consider the case of a 44no.s (6+1balls) lottery. If we split it into 2 sets of 22no.s, covering all no.s, and employ 4of4, 5of5 or 5of6 wheeling systems and create variance large enough to occasionally trap 5+1 no.s or more in either side of the sets, we stand a chance to win top 3 prizes.

All the possible outcome scenerios of 2 fully hedged wheels covering all no.s.

(3,4) , (4,3) , (5,2) , (2,5) , (6,1) , (1,6) , (7,1) , (1,7)

If variance swings are large enough, there is no escape, we will win top prizes. So the key question is how to create large swings to either side?

.i.e. In stock portfolio management, we want low variance, the beta, for any given expected no.,the alpha. However, for lottery fully hedged system, we want Maximum variance.

 

[D H]

The probability that each bean is magic remains constant at 0.3, independent of anything that you do with that particular bean.

You can look at a particular bean and alter your selection based on that, and that certainly can change the expected outcome (but that is cheating).

Changing the selection strategy most certainly does change the variance. So naively, why not the expected value?

I do agree with yours and Stephen Tashi's non-rigorous (i.e., intuitive) reasoning that the expected value has to be three for any valid selection strategy. However, trusting one's intuition when it comes to probability is oftentimes a losing proposition. In any case, my take on what Stephen Tashi meant by "rigorously" is to prove that every valid selection strategy will result in a probability distribution that has an expected value of three.

 

[AlephZero]

You can look at a particular bean and alter your selection based on that, and that certainly can change the expected outcome (but that is cheating).

That's the key point of my reasoning. Possibly you could make the assertion appear more rigorous by wrapping it in the language of Bayesian probability theory. The "rules" exclude doing anything that changes the a-posteriori probability of a bean being magic.

Changing the selection strategy most certainly does change the variance. So naively, why not the expected value?

Hmm.. I'm not sure if I'm too naive, or not naive enough, to feel there "ought" to be a connection between the expected value and the variance. But I don't.

 

[scalpmaster]

Aside: is Prob(6 found) maximized by taking 5 from each bag?

Does n=5 maximizes probability(6 found)? Not sure, but someone else responded this way:

Consider one bag:

Pick 10: 3 magic beans
Pick 9: 2 or 3 beans
Pick 8: 1, 2 or 3 beans
Pick 7: 0,1,2, or 3 beans
Pick 6: 0,1,2, or 3 beans
Pick 5: 0,1,2, or 3 beans
Pick 4: 0,1,2 or 3 beans
Pick 3:0,1,2, or 3 beans
Pick 2: 0,1,2 beans
Pick 1:0,1 beans
Pick 0: 0 beans

The expectation is maximum for the following combinations (of 2bags) :

7 and 3
6 and 4
5 and 5

in this case the expectation is:

0,1,2,3,4,5,6

These are the combinations that can offer you the maximum 6 magic beans at the risk of getting 0 beans.

If you want to play safe, you pick 10 from one bag but you have only 3 beans.
If risk aversion is not to have less than 2 magic beans then you have the following combinations:

10,0
9,1

If 1 is minimum then:

10,0
9,1
8,2

So the answer should depend on the constraint of minimum number of magic beans.
This is a boundary value constraint problem. Otherwise, it is incomplete.