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.