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.

  • 0
    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.)2012-02-26
  • 0
    Yes, if there are two cherries, picking 2,3, or 4 cherries will end the game.2012-02-26
  • 0
    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?2012-02-26
  • 0
    In my solution below, I assume that nothing happens in this case.2012-02-26
  • 7
    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.2012-02-26
  • 0
    @Henning: I think OP is the one planning on stabbing his own eyes out.2012-02-26
  • 0
    I independently got the same result as DSM got in the answer now deleted: $1077219654336/40719238081\approx26.4548087121169$. However, when I do the same for $10$ cherries, I get $1179248/80915\approx14.573910894148181$, slightly different from Nate's result.2012-02-26
  • 0
    @Henning, Now I'm laughing. I don't know which is worse, my grammar or my understanding of game theory.2012-02-26

3 Answers 3

8

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.

  • 0
    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)?2012-02-26
  • 0
    @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.2012-02-26
  • 0
    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.2012-02-26
  • 0
    I've resolved the discrepancy between our results; see my answer.2012-02-27
6

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

3

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\;.$$