3

I have the following recurrence relation: $$x_0=1 \\ x_n=p x_{n+1} + q x_{n-1} \text{ for }n=1,2,3,...$$

where $0<p=1-q<1$ and $0 \leq x_n \leq 1$.

Edit: Sorry for the lack of context. But I didn't realized that this was needed. In the end, I'm only interested in the minimal solution $x=(x_0,x_1,...)$.

I'm already doing math for some time, but I can't remember ever having to solve a recurrence relation, so I would like to learn a little bit more about this.

Of course, I would appreciate if someone can give a full solution to this one, but I'm also glad if someone can learn me some kind of method to solve recurrence relation like this (or some link where this is explained).

Kasper
  • 13,528
  • Grab some combi book that explains it.You must also know that there are multiple ways of solving recurrences. – rah4927 Oct 13 '14 at 16:22
  • This appears to be ill-defined since $x_1$ isn't included. (One way to remove ambiguity is to interpret the $n=0$ case of the recurrence as $x_0=px_1$.) At present, each value of $x_1$ will define a different solution. – Semiclassical Oct 13 '14 at 16:37
  • @Semiclassical $x_0=1$ and $x_1=px_2+q$ – Kasper Oct 13 '14 at 17:11
  • Can you clarify the origin of this problem? That may clarify the issue with the value of $x_1$. – Semiclassical Oct 13 '14 at 17:11
  • @Kasper: Which means that $x_2$ is defined up to $x_1$, and that propogates to all $x_{n>1}$. There isn't a unique solution unless $x_1$ is somehow prescribed. – Semiclassical Oct 13 '14 at 17:12
  • @Semiclassical I think there is no unique solution indeed, but is that a problem ? I forgot to mention that $x_n \in [0,1]$. – Kasper Oct 13 '14 at 17:17
  • Depends on the meaning of $x_n$, really. If you're simply trying to characterize the solutions, it's fine just to get solutions relative to $x_1$. But if this is coming out of some sort of model---such as each $n$ being a site receiving contributions from its neighbors---then the lack of a specific solution is a lot more questionable. – Semiclassical Oct 13 '14 at 17:27
  • @Semiclassical The model here is the chance $x_n$ to get bankrupt if you begin with a stock of $n$ dollar. And have a change $p$ of winning a dollar, and chance $q$ of loosing a dollar. – Kasper Oct 13 '14 at 17:37
  • Let us continue this discussion in chat. – Semiclassical Oct 13 '14 at 17:39

4 Answers4

8

Since $q=1-p$, we have $$x_n=px_{n+1}+(1-p)x_{n-1}$$ $$\iff x_{n+1}-x_n=\frac{1-p}{p}(x_n-x_{n-1}).$$ Hence, if we let $y_n=x_n-x_{n-1}$, we have $$y_{n+1}=\frac{1-p}{p}y_n.$$ Since we have $$y_n=\left(\frac{1-p}{p}\right)^{n-1}y_1\iff x_n-x_{n-1}=\left(\frac{1-p}{p}\right)^{n-1}(x_1-1),$$ we have for $n\ge 1$, $$x_n=x_0+(x_1-1)\sum_{i=0}^{n-1}\left(\frac{1-p}{p}\right)^{i}=1+(x_1-1)\cdot \frac{\left(\frac{1-p}{p}\right)^n-1}{\frac{1-p}{p}-1}.$$ This holds for $n=0$.

Case 1 : If $x_1=1$, then $x_i=1$ for all $i$.

Case 2 : If $x_1\lt 1$, then $\{x_n\}$ is a strictly decreasing sequence. If $p=\frac 12$, then $x_n=1+n(x_1-1)$. Hence, $0\le x_n\le 1\iff 0\le n\le\frac{1}{1-x_1}$. Hence, the minimum $x_n$ is attained when $n=\left\lfloor 1/(1-x_1)\right\rfloor$. If $p\not=\frac 12$, then the minimum $x_n$ is attained when $$n=\left\lfloor\log_{\left(\frac{1-p}{p}\right)}\left(\frac{\frac{1-p}{p}-1}{1-x_1}+1\right)\right\rfloor.$$

mathlove
  • 139,939
  • This has a small problem with initial values: Is $y_0=x_0=1$? (This is an issue with how the problem is stated, to be sure, rather than with this approach.) – Semiclassical Oct 13 '14 at 17:00
  • @Semiclassical: $y_n$ is defined only for $n\ge 1$. – mathlove Oct 13 '14 at 17:01
  • That doesn't really help, since then one can ask about $y_1=x_1-x_0$ and then the lack of definition of $x_1$ comes into play. – Semiclassical Oct 13 '14 at 17:03
  • @Semiclassical: Oh, now I understand what you mean. So, I think $x_1$ has to be defined in the question. – mathlove Oct 13 '14 at 17:04
  • 1
    Right. Taking $y_0=x_0$ would amount to $$y_1=\frac{1-p}{p}y_0=\frac{1-p}{p}=x_1-x_0\implies x_1=\frac{1-p}{p}+1=\frac{1}{p}\implies x_1=p x_0$$ which is the suggestion I offered in the comments above. That'd be a natural initial value, but right now it's just not defined. – Semiclassical Oct 13 '14 at 17:09
  • @Kasper : I added a bit. Take a look. – mathlove Oct 14 '14 at 10:46
2

For fun, here is a solution based upon generating functions. Let $X(t)=\sum_{n=1}x_n t^n$ where $t$ is a formal variable. Since $x_n$ satisfies the relation $x_n=p x_{n+1} + q x_{n-1}$ for $n\geq 1$, we have

\begin{align} X(t) &=1+\sum_{n=1}^\infty x_n t^n\\ &=1+p \sum_{n=1}^\infty x_{n+1} t^n+q \sum_{n=1}^\infty x_{n-1} t^n\\ &=1+pt^{-1}\left(X(t)-1-x_1 t\right)+q tX(t)\\ \implies X(t)&=\frac{p(1+x_1 t)-t}{p-t+q t^2}\\ &=\frac{1}{1-t}\left(1+\frac{pt(x_1-1)}{p-qt}\right)\\ &=\frac{1}{1-t}+\frac{p(x_1-1)}{p-q}\left(\frac{1}{1-t}-\frac{p}{p-qt}\right) \end{align}

Expanding these geometric series and identifying coefficients term-by-term, we have

$$\boxed{\displaystyle x_n=\frac{p x_1-q}{p-q}+\frac{p(1-x_1)}{p-q}\left(\frac{q}{p}\right)^{n}}$$

That power of $q/p$ is perhaps concerning, since if $q>p$ then it would appear that $x_n$ must necessarily grow larger than one eventually. But it should be noted that $q>p$ hardly makes sense in this context, since that would mean one is more likely to keep increasing in wealth rather than go bankrupt. (The boundary case of $p=q=1/2$ is also exceptional, and I won't consider it here.)

So I'll assume $q<p$. Then $x_n\to \dfrac{px_1-q}{p-q}$ as $n\to \infty$. But this is a bit strange: If I make my initial wealth larger and larger, then the probability of bankruptcy should converge to precisely zero. From this we deduce that $x_1=q/p$, and therefore $\boxed{x_n=\left(\dfrac{q}{p}\right)^{n}}$ is the final result. (This has the side benefit of rendering $X(t)=\dfrac{p}{p-qt}$.)

Semiclassical
  • 15,842
1

Whenever you have a linear, homogenous recurrence relation with constant coefficients, the solution will be a linear combination of solutions of the form $x_n=r^n$. This can be proved by showing these are solutions, then thinking of solutions as a vector space to show all solutions are of this form, etc.

If you take this fact on faith, then you can see what values of $r$ are possible by substituting $r^n$ for $x_n$ in your recurrence: $$ r^n=pr^{n+1}+qr^{n-1}, $$ or $$ pr^2-r+q=0 $$ Solving this for $r$, you will see there are two roots, $r_1,r_2$. The general solution is then $$ x_n = c_1r_1^n+c_2r_2^n $$ for some constants $c_1,c_2$. Typically, these constants are found using the given base cases for the recurrence; in your example, plugging in $n=0$ above tells you $x_0=1=c_1+c_2$. If you had another base case, say, $x_1=\frac12$, or something, this would give you another equation you could use to solve for $c_1,c_2$.

Mike Earnest
  • 75,930
  • 1
    Caveat Emptor: There's actually a special case that happens when you get a double root, i.e. when you find $r_1=r_2$. Then the solution will be $$x_n=c_1r_1^n+c_2nr_1^n.$$ – Mike Earnest Oct 13 '14 at 16:37
0

Hint. Try first to get elementary solutions of the form $$ x_n=r^n \tag1$$ for real numbers $r$.

Let's plug $(1)$ in $$x_0=1 \\ x_n=p x_{n+1} + q x_{n-1}$$ we get $$r^n=p \:r^{n+1} + q \:r^{n-1},\quad n\geq1$$ $$r^{n-1}(p \:r^2 - r+ q)=0 ,\quad n\geq1$$ If you solve this $$p \:r^2 - r+ q=0 $$ Then we have to prove that we have got all solutions in that way ...

I hope this can help.

Stefan Banach
  • 1