Calculating the average of a possibly infinite "compound" length

Question

Sorry for the ambiguous title, I couldn't find a good word to describe my problem.

So here is my problem:

You are a player, and you have a dice.

You have N number of throws available then you can't throw any more.

However, every time you get a 6 in a throw. You get M more throws available.

Example: N = 5 M = 1

1st throw: 1 (remains 4 throws)

2nd throw: 2 (remains 3 throws)

3rd throw: 3 (remains 2 throws)

4th throw: 6 (remains 2 throws)

5th throw: 4 (remains 1 throws)

6th throw: 6 (remains 1 throws)

7th throw: 1 (remains 0 throws, STOP)

As you can see, it's theoretically possible to get infinite number of throws. Also you can see why I said "compound", because every time you get extra throws, within those extra throws you can get again more extra throws and so on, which is why it can be infinite.

Now how do I calculate the average number of throws you can get based on the three inputs:

Initial throws available = N

Awarded throws when outcome is X = M

Probability of getting X in one throw = 1/6 (in this case of a dice)

---

One note however:

I can already solve this using Markov Chains but I want an answer using Algebra or something other than Markov Chains (I know it exists because someone showed me before but I cannot remember any more how he did it, should have taken notes)

---

For the interested, here is how I do it using Markov Chains:

By constructing a transition matrix, where the "state" is the number of throws remaining. Of course, you can have infinite number of throws so you should only make the matrix big enough to provide a good approximation.

Now, you can get the chance of stopping within X number of throws by checking the matrix power X number of throws, row N (initial state) and column 0 (end state: stop). Since we can calculate the chance of stopping within X number of throws, we can get the chance of stopping exactly after X number of throws by calculating for X and X-1 then doing

(chance of stopping within X - chance of stopping within (X-1)) = Chance of stopping exactly after X throws

You can then do this for X = N .... Infinity

Then you can sum the product of the two arrays of probabilities of stopping and X number of throws and you get the average number of throws that the player gets before stopping.

Thanks, Space Monkey.

Answer 1

Fix $m$ and let $f(n)$ be the expected time until the end of the game starting with $n$ throws.

First observe that $$f(a+b) = f(a) + f(b).$$

To see this, play the game starting with $a$ throws and then directly afterwards play the game starting with $b$ throws. This is the same as starting with $a+b$ throws, the second game starts the first time you have only $b$ throws remaining.

So we may conclude that $f(n) = nf(1)$.

Now for $n=1$ the game finishes after $1$ if we throw anything other than a six. The expected number of throws given we throw a six is $1+f(m)$.

So we have $$\begin{align} f(1) &= 1 + \frac 16 f(m) \\ &= 1+\frac m6 f(1) \end{align}$$

Therefore $$f(n) = \frac {6n}{6-m}.$$