I am watching Stochastic Processes I by MIT OpenCourseWare on YouTube. A simple random walk is considered: we start from $0$, and at each timestamp, we take a unit step up or down the number line with $50$% probability.
We consider two thresholds: $B$ and $-A$ such that $A,B>0$:
We define $f(k)$ to be the probabilility of hitting threshold $B$ before hitting $A$, when starting from position $k$. We would like to know, what is the probability of hitting $B$ before hitting $A$ when starting from $0$. Hence we after $f(0)$.
When we are at position $k$, we either go up or down with probability $\frac{1}{2}$ (as always). If we go up, we hit $B$ before hitting $A$ with $f(k+1)$ probability. If we go down, we hit $B$ first with $f(k-1)$ probability. We have a recurrence relation:
$$f(k)=\frac{1}{2}f(k+1)+\frac{1}{2}f(k-1)$$
Furthermore, we also know that: $$f(B)=1$$ and $$f(A)=0$$
The lecturer claims that from these alone, we can arrive to the conclusion that
$$f(0)=\frac{A}{A+B}$$
How can I arrive at this result?
I am aware of the thread Reaching a level before another for a random walk, but I specifically would like to use the recurrence relation mentioned above.
We have a system of equations
$$\begin{align} f(-A) &= 0 \\ f(k) &= \frac{1}{2}f(k+1)+\frac{1}{2}f(k-1) \quad \forall k \in \{-A+1,\dots,B\} \\ f(B) &= 1 \end{align}$$
Which are $A+B+1$ linear equations for $A+B+1$ variables. These form a linear system of rank $A+B+1$, so their solution is unique. There are several ways to solve it. You can use a brute-force method and solve this matrix equation:
$$\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & \cdots & 0 \\ \frac{1}{2} & -1 & \frac{1}{2} & 0 & 0 & \cdots & 0 \\ 0 & \frac{1}{2} & -1 & \frac{1}{2} & 0 & \cdots & 0 \\ & & & \ddots & & & \\ 0 & \cdots & 0 & \frac{1}{2} & -1 & \frac{1}{2} & 0 \\ 0 & \cdots & 0 & 0 & \frac{1}{2} & -1 & \frac{1}{2} \\ 0 & \cdots & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} f(-A) \\ f(-A+1) \\ \vdots \\ f(-1) \\ f(0) \\ f(1) \\ \vdots \\ f(B-1) \\ f(B) \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ \vdots \\ 0 \\ 0 \\ 1 \end{bmatrix}$$
However there is a smarter way. Notice that each equation says that $f(k)$ is the average of the two values besides it:
$$f(k) = \frac{f(k+1)+f(k-1)}{2}$$
There is a simple function where this holds, namely a linear function. And since the solution of the system of equations is unique, once we find a solution, that will be the only solution. And a linear function that goes through $(-A,0)$ and $(B,1)$ satisfies all our criterias:
Namely it clearly satisfies the first and last equations $f(-A)=0$ and $f(B)=1$ by construction, and it also satisfies the central $A+B-1$ equations, because the value of a linear function at $k$ is the average of its value at $k-1$ and $k+1$.
So we just need to find $f$, then calculate $f(0)$. Since $f$ is linear, its formula is:
$$f(x)=ax+b$$
We know that
$$ \begin{align} \text{I. }f(-A)&=0 \\ \text{II. }f(B)&=1 \end{align}$$
Substituting
$$ \begin{align} \text{I. }f(-A)&=-aA+b=0 \\ \text{II. }f(B)&=aB+b=1 \end{align}$$
Which we can solve for $a,b$:
$$\begin{align} aA&\stackrel{\text{I.}}{=}b \\ aB+aA&\stackrel{\text{II.}}{=}1 \\ a(B+A)&=1 \\ a&=\frac{1}{A+B} \\ b&\stackrel{\text{I.}}{=}\frac{A}{A+B} \end{align}$$
So
$$f(0)=0a+b=b=\frac{A}{A+B} \quad \square$$