There's a tube of yellow and orange sweets, and you prefer the yellow ones. There's an equal number of each and they're distributed randomly. It is a very long tube and it's transparent so you can see all the colours coming up. When you visit the tube, you can take as many sweets as you want, but it has to be at least one and you can only take them in the order that they're in - you can't skip any. If you go away and come back, loads of other people would have visited the tube in the meantime so everything is reset. If you play optimally, what proportion of your sweets would be yellow? And what is the optimum strategy?
I don't know the answer to this by the way.
Cherry-picking question
Moderator: Michael Wallace
-
- Post-apocalypse
- Posts: 13331
- Joined: Mon Jan 21, 2008 10:37 pm
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Cherry-picking question
I'll look at this properly later, but at first glance it seems similar to the secretary problem.
-
- Enthusiast
- Posts: 265
- Joined: Wed Sep 09, 2009 3:18 pm
Re: Cherry-picking question
Although it has some similarities to the secretary problem, the way Gev has phrased it seems to imply that you have perfect information, i.e. you'd never have to make a decision without knowing what is coming next. Assuming that the tube is not infinitely long (as you could surely then just wait for whatever proportion you want) and that you are under some time pressure for your decision, a good strategy would be to ignore the first sweet (you have to take it anyway), then:
i) if the next sweet is yellow, keep taking yellow sweets until the next orange sweet
ii) if the next sweet is orange, walk away in disgust
This is of course assuming that you play the game over and over again. I reckon you get 1.5 yellows to 0.5 oranges on average (see below). Maybe not optimal, but I think optimality may depend on interpretation of the question...
PROOF: Ignoring the first sweet, chance of exactly one yellow in a row is 1/2 (chance of yellow)*1/2 (chance of orange)=1/4, chance of two yellows is 1/2*1/2 (two yellows) *1/2 (orange)=1/8, three yellows is 1/2*1/2*1/2*1/2=1/16. Assuming the number of sweets is very large, your expected number of yellow sweets is 1*1/4+2*1/8+3*1/16+....=1. As the first sweet is 50:50, on each trip I would expect to pick 0.5 oranges and 0.5+1=1.5 yellows
i) if the next sweet is yellow, keep taking yellow sweets until the next orange sweet
ii) if the next sweet is orange, walk away in disgust
This is of course assuming that you play the game over and over again. I reckon you get 1.5 yellows to 0.5 oranges on average (see below). Maybe not optimal, but I think optimality may depend on interpretation of the question...
PROOF: Ignoring the first sweet, chance of exactly one yellow in a row is 1/2 (chance of yellow)*1/2 (chance of orange)=1/4, chance of two yellows is 1/2*1/2 (two yellows) *1/2 (orange)=1/8, three yellows is 1/2*1/2*1/2*1/2=1/16. Assuming the number of sweets is very large, your expected number of yellow sweets is 1*1/4+2*1/8+3*1/16+....=1. As the first sweet is 50:50, on each trip I would expect to pick 0.5 oranges and 0.5+1=1.5 yellows
-
- Post-apocalypse
- Posts: 13331
- Joined: Mon Jan 21, 2008 10:37 pm
Re: Cherry-picking question
Some good thinking, but I'm not sure I'd always walk away at the first orange. If it went yellow, orange, yellow*10, I'd definitely take all 12. Regarding interpretation, maybe it would have a more definite answer if there was a set end point. So you have to take 100 overall, with as many visits to the tube as you like (well, it would be no more than 100). Although having said that, there should be an optimum strategy to maximise your long-term mean yellow percentage over the long term I would have thought, with no definite end point.
-
- Enthusiast
- Posts: 265
- Joined: Wed Sep 09, 2009 3:18 pm
Re: Cherry-picking question
Sure - I can see that there is no way mine is optimal, but I think you do need some sort of cap, otherwise you could just keep looking ahead to see if you can improve ad infinitum - then it may start to look more like a variant of the secretary problem. To follow on from your idea of obviously taking the x yellows after the orange, (I think) you would do this if it gave you a better ratio than 3:1 (which is what you get with my original method)
EDIT: So on that note, if you can only take 100 sweets then I think the idea of taking an amount that "beats" 3:1 by as much as possible on any particular go is a better strategy than before (assuming you can see up to x sweets ahead, when you have x sweets remaining of your cap) - if you can't beat 3:1 then you walk away at the first orange. The 3:1 ratio would apply for any total cap and any residual amount as well, i.e. if you have taken 76 sweets, you would expect to average 3:1 for the remaining 24 sweets. Still not convinced this is optimal though...
EDIT: So on that note, if you can only take 100 sweets then I think the idea of taking an amount that "beats" 3:1 by as much as possible on any particular go is a better strategy than before (assuming you can see up to x sweets ahead, when you have x sweets remaining of your cap) - if you can't beat 3:1 then you walk away at the first orange. The 3:1 ratio would apply for any total cap and any residual amount as well, i.e. if you have taken 76 sweets, you would expect to average 3:1 for the remaining 24 sweets. Still not convinced this is optimal though...
-
- Kiloposter
- Posts: 1786
- Joined: Sat Oct 23, 2010 3:21 pm
- Location: Dublin
Re: Cherry-picking question
Just take all the sweets and give the orange ones away or eat them anyway. They're sweets, they can't be that bad.
- Jon O'Neill
- Ginger Ninja
- Posts: 4552
- Joined: Tue Jan 22, 2008 12:45 am
- Location: London, UK