8
$\begingroup$

I'm playing this game with children and I'm ready to stab my eyes with an ice pick. It seems like it never ends, but I know I expect it to end. What is my expected number of spins to remove all the fruit from the tree?

Goal: To remove 14 cherries from tree by executing one of following seven directions at random per turn.

 1. Remove 1 cherry.
 2. Remove 2 cherries.
 3. Remove 3 cherries.
 4. Remove 4 cherries.
 5. Return 1 cherry to tree.
 6. Return 2 cherries to tree.
 7. Return all your cherries to tree.

Once I realized I have a 1/7 chance each turn of playing this game in perpetuity, I started reaching for the kitchen drawer.

$\endgroup$
8
  • $\begingroup$ Suppose there are 2 cherries on the tree. Does the game end if you roll a 3 or a 4? (ie, if you're asked to remove more cherries than there are left.) $\endgroup$
    – Brett Frankel
    Feb 26, 2012 at 3:32
  • $\begingroup$ Yes, if there are two cherries, picking 2,3, or 4 cherries will end the game. $\endgroup$
    – zundarz
    Feb 26, 2012 at 3:35
  • $\begingroup$ Also, if all 14 cherries are on the tree and you roll a 5, does the tree now have 15 cherries or does nothing happen? $\endgroup$
    – Brett Frankel
    Feb 26, 2012 at 3:36
  • $\begingroup$ In my solution below, I assume that nothing happens in this case. $\endgroup$
    – Brett Frankel
    Feb 26, 2012 at 3:46
  • 7
    $\begingroup$ Um, if there are children threatening you with ice picks, then the statistical properties of some game probably shouldn't be on top of your priority list. $\endgroup$
    – hmakholm left over Monica
    Feb 26, 2012 at 3:48

3 Answers 3

Reset to default
8
$\begingroup$

I actually spent some time about a year ago doing some computations for a variant of this game, sold as Hi-Ho Cherry-O. It's identical to your game, except with 10 cherries instead of 14. (I learned about it from a colleague with a 4-year-old daughter.)

The computation is a nice example of some simple Markov chain techniques, which produce linear equations of the sort in Brett Frankel's answer. I considered the cases of 1 to 4 players, which are amenable to computer solution.

Another interesting feature is that since the players take turns, the first player has a slight advantage.

Here are the results I got for 10 cherries. If you are really interested, I can try and reconstruct my code and run the 14 cherry case.

1 player game:

Expected length: 15.8019792994073 rounds

2 player game:

Expected number of rounds: 9.58554137805221
P(player 1 wins) = 0.518720469382215
P(player 2 wins) = 0.481279530617784
Expected number of turns = 18.6523622867222

3 player game:

Expected number of rounds: 7.49668096168849
P(player 1 wins) =  0.357756582790784
P(player 2 wins) =  0.332728455615310
P(player 3 wins) =  0.309514961593905
Expected number of turns: 21.4418012638686

4 player game:

Expected number of rounds: 6.44149249272987
P(player 1 wins) =  0.276928283784381
P(player 2 wins) =  0.258099951775544
P(player 3 wins) =  0.240610168544412
P(player 4 wins) =  0.224361595895655
Expected number of turns: 24.1783750474708

Edit: I should also mention some previous work by Jeffrey Humpherys.

$\endgroup$
4
  • $\begingroup$ I get $1179248/80915\approx14.573910894148181$ for $10$ cherries, yet the same as DSM for $14$ cherries. Are you sure you used exactly the same rules (especially when there aren't enough cherries to remove or to return)? $\endgroup$
    – joriki
    Feb 26, 2012 at 5:22
  • $\begingroup$ @joriki: DSM's answer is now deleted, but I believe the rule I used is that when there aren't enough cherries, you add or remove as many as possible. E.g. if you have only one cherry in your bucket and spin a 6, you return that one cherry to your tree. Again, I unfortunately only saved pieces of my code, so I can't check it, but perhaps if I have some time in the near future I'll reconstruct it. $\endgroup$
    – Nate Eldredge
    Feb 26, 2012 at 14:16
  • $\begingroup$ Nate E.: The game is Hi-Ho-Cherry-Oh. It seems like 14 cherries!! After I removed the ice-picks from my eyes, I recounted and there are just 10 cherries. $\endgroup$
    – zundarz
    Feb 26, 2012 at 14:26
  • $\begingroup$ I've resolved the discrepancy between our results; see my answer. $\endgroup$
    – joriki
    Feb 27, 2012 at 12:35
6
$\begingroup$

You can solve via a series of 14 linear equations: Let $E_n$ be the expected number of turns remaining until the game is over when there are currently $n$ cherries on the tree. For example, $$E_1=\frac{4}{7}1+\frac{1}{7}(1+E_2)+\frac{1}{7}(1+E_3)+\frac{1}{7}(1+E_{14})$$

$$E_{14}=\frac{1}{7}(1+E_{13})+\frac{1}{7}(1+E_{12})+\frac{1}{7}(1+E_{11})+\frac{1}{7}(1+E_{10})+\frac{3}{7}(1+E_{14})$$

By the time you finish writing down all 14 equations and solving, the game may well be over. (Then again, I expect the answer will be quite large).

$\endgroup$
3
$\begingroup$

I've found the reason for the discrepancy between Nate's answer and my results (which agree with DSM's). In the version of the game that Nate linked to, the dog and the bird both require you to return $2$ cherries to the tree, whereas in the present version 5. says one cherry and only 6. says two cherries. If I change my code to the linked version my result for the expected number of turns is in agreement with Nate's. For the present version, I get

$$\frac{1179248}{80915}\approx14.5739\;.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .