$F(x) = .5 F(x+1) + .5F(x-1)$.. How to solve

Question

I saw this in an mit open courseware video for approximating the probability of Reaching one value versus another in a coin flip game.

For example, if $f(10) = 1$ and $f(-5)=0$ what is $f(0)$ (you earn a dollar on each coin flip of heads, lose a dollar on tails. Game is over at $10$ dollars won or $5$ dollars lost. What is probability of winning?)

In other words, if $f(a)=1$ and $f(-b)=0$, the solution is $b/a+b$. However, I don't understand how he arrived at that. I can do recurrence relations, but this one is infinitely recursive when I write it out. Any tips?

Answer 1

Note that $f(x+1)-f(x)=f(x)-f(x-1)$

Then

$f(a)-f(a-1)=k$

$f(a-1)-f(a-2)=k$

$...$

$f(-b+1)-f(-b)=k$

Add them up,

$f(a)-f(-b)=(a+b)k=1\implies k=\large{1\over a+b}\implies f(0)=f(-b)+k\cdot b=0+\large{b\over a+b}$

Answer 2

Multiply by $2$ and rewrite it as $f(n+1)=2f(n)-f(n-1)$. This homogeneous linear recurrence with constant coefficients has the characteristic equation $x^2=2x-1$, i.e., $x^2-2x+1=0$, which is $(x-1)^2=0$. Since both roots are $1$, by a standard theorem the general solution to the recurrence is

$$f(n)=A(1)^n+Bn(1)^n=A+Bn\;,\tag{1}$$

where $A$ and $B$ depend on the initial values, or in fact on any pair of values.

Suppose that $f(a)=1$ and $f(-b)=0$, where $a,b>0$. Then $(1)$ says that $A+Ba=1$ and $A-Bb=0$, and we have a system of two linear equations in the unknowns $A$ and $B$. Multiply the first by $b$ and the second by $a$ and add, and you find that $A(a+b)=b$, so $A=\frac{b}{a+b}$. Substitute that into the second equation to find that

$$B=\frac{A}b=\frac1{a+b}\;.$$

Thus,

$$f(n)=\frac{b}{a+b}+\frac{n}{a+b}=\frac{n+b}{a+b}\;,$$

and

$$f(0)=\frac{b}{a+b}\;.$$

Added: For a more elementary analysis, notice that original recurrence can be written

$$f(n)=\frac{f(n+1)+f(n-1)}2\;,$$

meaning that each term of the sequence is the arithmetic mean of the neighboring terms. This is possible precisely when the gaps between adjacent terms are equal:

$$f(n+1)-f(n)=f(n)-f(n-1)\;.$$

That in turn says that the sequence must be an arithmetic sequence, so it must satisfy $f(n)=A+Bn$ for some constants $A$ and $B$. Now you can use the known values of $f(a)$ and $f(-b)$ to find $A$ and $B$ just as I did above.

Answer 3

For reasonable $n$, we have $f(n+1)=2f(n)-f(n-1)$. Now we compute.

Let $f(-4)=k$. Then $f(-3)=2f(-4)-f(-5)=2k$. But $f(-2)=2f(-3)-f(-4)=3k$. But $f(-1)=2f(-2)-f(-3)=4k$. But $f(0)=2f(-1)-f(-2)=5k$.

And so on. We get $f(1)=6k$, $f(2)=7k$, and so on up to $f(10)=15k$.

This is equal to $1$, so $k=\frac{1}{15}$. But $f(0)=5k=\frac{5}{15}$.