# what's the generalized approach to this infinite state markov chain problem

Say, a bag has 10 balls, in which 9 are red, 1 is black.

Each red ball is worth 1 point, each black is worth 4 points.

I have 8 picks from the bag to start with (the bag refills itself after each pick: returns to 9 red 1 black), once I get a black ball, I will get 8 additional picks, and go on.

Ultimately I would like to calculate the expected total points.

So, for example

1st pick    red     7 picks remaining
2nd pick    black   6 + 8 = 14 picks remaining
...

One way to solve the problem:

Assume the expected number of red balls is A, black balls is B. $A/B=9$ and $8+8*B=A+B$ So $A = 36,B = 4$

But I am looking for a more formal/generalized way (maybe markov/matrix or wald equation or stopping time) to this kind of problem.

-
"The bag refills..." means it returns to being 9 red and one black? –  Thomas Andrews Oct 19 '12 at 21:17
@ThomasAndrews yes it does –  colinfang Oct 19 '12 at 21:20
Is it even true with probability $1$ that you will eventually end this game? That's not at all clear to me. –  Thomas Andrews Oct 19 '12 at 21:24
If it is not true, then the expected value is infinite. It might be infinite even if the game will end with probability 1, as in the St Petersburg paradox: en.wikipedia.org/wiki/St._Petersburg_paradox –  Thomas Andrews Oct 19 '12 at 21:26
Also, when the game ends, if you have $A$ red balls and $B$ black balls, then $A+B$ is the total number of draws, but that is $8+10(B-1)$, so $A+B=8+10(B-1)$ so $A/B = 9-\frac{2}{B}<9$ –  Thomas Andrews Oct 19 '12 at 21:33

Generalised: you have probability $p$ of picking a red ball and $1-p$ of a black ball, and $n$ picks. If you a black ball, you get an extra $n$ picks.
So if $r$ is the expected number of red balls picked and $b$ the expected number of black balls then you can calculate the expectation from one pick (including the values from the possibility of getting an extra set of picks), which you can multiply by $n$: $$r = n(p + (1-p)r),$$ $$b= n(1-p)(1+b),$$ so $$r=\frac{np}{1-n(1-p)},$$ $$b = \frac{n(1-p)}{1-n(1-p)}.$$
For $p=0.9$ and $n=8$ this gives $r=36$ and $b=4$, as you calculated.
If $n \ge \frac{1}{1-p}$ then the denominators are not positive and the expectations are in fact infinite.
Red balls are $\frac{r}{b}=\frac{p}{1-p}$ times as likely as black balls ($9$ times in your example) and this carries through to the expectations. If $B$ is the actual number of black balls then you will have $R=(n-1)B+n$ red balls: while $\frac{R}{B}$ may be less than $\frac{p}{1-p}B$ for small $B \lt b$, it will be more than $\frac{p}{1-p}$ for large $B \gt b$ so long as the expectations are finite.