# Magic beans problem

1. Sep 25, 2011

### 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 any one 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.

Last edited: Sep 25, 2011
2. Sep 25, 2011

### 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.

3. Sep 25, 2011

### 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.

4. Sep 25, 2011

### scalpmaster

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.

5. Sep 25, 2011

### Stephen Tashi

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

6. Sep 25, 2011

### scalpmaster

lower variance.

7. Sep 25, 2011

### Stephen Tashi

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?

8. Sep 25, 2011

### scalpmaster

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.

9. Sep 25, 2011

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

10. Sep 25, 2011

### 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.

11. Sep 25, 2011

### scalpmaster

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?

Last edited: Sep 25, 2011
12. Sep 25, 2011

### 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.

13. Sep 25, 2011

### Stephen Tashi

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}$

14. Sep 25, 2011

### scalpmaster

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

15. Sep 25, 2011

### Stephen Tashi

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.

16. Sep 26, 2011

### bpet

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

17. Sep 26, 2011

### D H

Staff Emeritus
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 ...

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.

18. Sep 26, 2011

### scalpmaster

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

19. Sep 26, 2011

### Stephen Tashi

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

20. Sep 26, 2011

### D H

Staff Emeritus
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.

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

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