Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

From DeGroot 2.4.2, let $a_i$ be the conditional probability that the gambler wins all $k$ given gambler is at $i$.

$a_i = pa_{i+1} + (1 - p)a_{i-1} $

It's not clear from the text what steps are taken to solve for the general form $a_i$ (maybe Gaussian elimination). How do you solve the recurrence equation for $a_i$? If this can be found through the characteristic equation of a matrix $A$, then how do you construct $A$? As the problem is described, the first row has $a_0 = 0$, and last with $a_k = 1$.

share|improve this question
add comment

3 Answers 3

up vote 2 down vote accepted

We can rewrite the recurrence as $0=pa_{i+1} - a_i+(1-p)a_{i-1}$ and solve the characteristic equation $p\theta^{i+1}-\theta^i+(1-p)\theta^{i-1}=0.$ Ignoring $\theta=0$ we get $\theta=1,(1-p)/p.$ Thus, the probabilities satisfying the recurrence are of the form $a_i=c_1+c_2(\frac{1-p}{p})^i$ with $a_0=0$ and $a_k=1.$ Then we can solve the resulting system for $c_1,c_2.$ This link might help.


More explicitly: To find the roots of the characteristic equation of the recurrence, we solve $p\theta^2-\theta+(1-p)=0.$ We have two unique solutions $\theta_1=1,\theta_2=\frac{1-p}{p}.$ What the link tells us is that since these roots are distinct, the recurrence has general solution $a_i=c_1+c_2(\frac{1-p}{p})^i,$ where $c_1,c_2$ are constants. We can verify that $a_i=1^i=1$ is a solution, since $1=(p)(1)+(1-p)(1).$ Also, $$p(\frac{1-p}{p})^{i+1}+(1-p)(\frac{1-p}{p})^{i-1} = (\frac{1-p}{p})^i(1-p)+p(\frac{1-p}{p})^i=(\frac{1-p}{p})^i,$$ so indeed $(\frac{1-p}{p})^i$ is a solution.

Now, given $a_0=0$ and $a_k=1,$ we can solve for $c_1,c_2.$ First, $a_0 = 0$ implies $c_1+c_2(\frac{1-p}{p})^0=c_1+c_2=0$, or $c_1=-c_2.$ Second, $a_k=1$ implies $c_1-c_1(\frac{1-p}{p})^k=1,$ so $$c_1=\frac{1}{1-(\frac{1-p}{p})^k}=\frac{p^k}{p^k-(1-p)^k}.$$ We can see here that we should have $p\neq \frac{1}{2}.$

Thus, the solution should look something like: $$\frac{p^k}{p^k-(1-p)^k}-\frac{p^k}{p^k-(1-p)^k}(\frac{1}{1-p})^i.$$

I'm not sure I can help with a reference. To be honest, when I saw this in a class it was not well explained, and the text didn't help. Although maybe the wikipedia reference has something. Best of luck!

share|improve this answer
    
I am trying to follow your answer since my approach at this was with linear algebra, but my understanding of eigenvectors is not good.Please spell it out for me: I tried substituting the solution $(1 - p)/p$ into $a_i = pa_{i+1} + (1 - p)a_{i-1} $ and solve for $a_i$ but do not see how you go from there to $a_i=c_1+c_2(\frac{1-p}{p})^i$. I looked at the link, but don't quite get it yet. Suggestions on a good textbook would be appreciated. –  Not a NaN notha Aug 3 '12 at 21:00
1  
Thanks for the extensive answer, very helpful, and has led me to ask a new, related question. –  Not a NaN notha Aug 4 '12 at 15:31
add comment

This is best solved using generating functions. Let $f(x) = \sum_{k=0}^\infty a_k x^k$. Now multiply the recurrence equation with $x^k$ and perform the summation: $$ f(x) - a_0 = \sum_{k=1}^\infty a_k x^k = \sum_{k=1}^\infty (p a_{k+1} + (1-p) a_{k-1}) x^k = \frac{p}{x} \sum_{k=1}^\infty a_{k+1} x^{k+1} + (1-p) x \sum_{k=1}^\infty a_{k-1}) x^{k-1} = \frac{p}{x} \left( f(x) - a_0 - a_1 x\right) + (1-p) x f(x) $$ Now solve for $f(x)$: $$ f(x) = a_0 \frac{p-x}{(1-x)(1-(1-p)x)} + a_1 \frac{ p x}{(1-x)(1-(1-p)x)} \\ = \left(\frac{\left(a_1-a_0\right) p}{1-\frac{1-p}{p} x}+\frac{a_0 (1-p)-a_1 p}{ 1-x}\right) \frac{1}{1-2p} \\ = \frac{1}{1-2p} \sum_{n=0}^\infty \left( \left(a_1-a_0\right) \frac{(1-p)^n}{p^{n-1}} + \left(a_0 (1-p)-a_1 p\right) \right)x^n \\ = \sum_{n=0}^\infty \left( a_0 \frac{p^{n-1}(1-p) - (1-p)^{n}}{(1-2p) p^{n-1}} + a_1 \frac{(1-p)^n - p^n}{(1-2p)p^{n-1}} \right) x^n $$ where geometric series has been used. The case of $p =\frac{1}{2}$ requires taking a limit. Using L'Hospital's rule: $$ a_k\left(\frac{1}{2}\right) = a_1 n + a_0 (1-n) = a_0 + (a_1-a_0) n $$

share|improve this answer
add comment

Hint: Rewrite our recurrence as $$pa_i+(1-p)a_i=pa_{i+1}+(1-p)a_{i-1}.$$ A little manipulation changes this to $$p(a_{i+1}-a_i)=(1-p)(a_i-a_{i-1}).$$ If $p \ne 0$, this can be rewritten as $$a_{i+1}-a_i=\frac{1-p}{p}(a_i-a_{i-1}).$$ Let $b_i=a_i-a_{i-1}$. Then the $b_i$ satisfy the simple recurrence $$b_{i+1}=\frac{1-p}{p}b_i.$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.