What is expected number of turns to play this children's game?

Question

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.

Answer 1

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.

Answer 2

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

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