# Calculating the average of a possibly infinite "compound" length

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.

• Can't see any "numbers" solution, but doing it with Markov chains isn't that hard, though. Jun 12 '13 at 16:28
• @haemhweg I can't see a reason for your comment.... nah, I'm joking man, thanks for trying :) I know there is a method because I saw it before but I can't remember it and it was quite difficult to understand (to me at least). Jun 12 '13 at 17:08
• I mean this is a problem where using Markov chains would be natural. Jun 12 '13 at 17:10
• @haemhweg Check the answer, mate Jun 12 '13 at 17:25

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}.$$

• Perfect, mate !! Jun 12 '13 at 17:25
• May I ask you how did you approach this? did you solve similar problems before? I can follow the steps and it all makes sense and fine, but how did you actually think of this way? Jun 12 '13 at 17:32
• It's a special type of Markov chain called a random walk. I happen to know a lot about random walks.
– Tim
Jun 12 '13 at 17:59
• So the typical solution is to use Markov chains? Jun 13 '13 at 9:09
• I would say martingales[1] would be the key tool for this answer. Obviously I didn't talk about them explicitly because it would be overkill for a simple game like yours. But the idea behind the answer comes from experience working in that sort of area. [1]: en.wikipedia.org/wiki/Martingale_%28probability_theory%29
– Tim
Jun 13 '13 at 9:41