How can you solve this simple looking recurrence relation in two variables?
$f(a,b) = 1 + \frac{a f(a+1,b+1) + (x-a)f(a+1,b)}{x}$
The function $f$ is defined for non-negative integer values $a$ and $b$ in the range specified below.
The boundary conditions for the first and second variable are given by fixed integer values $x$ and $y$ which define the problem instance as follows:
$f(x,b) = y-b$
$f(a,y) = 0$
We know $0 < y < x$, $1 \leq a \leq x$ and $0 \leq b \leq y$ and I am trying to compute $f(1,0)$. Note that $f(1,0)$ should be a function of $x$ and $y$ only.
$$ f(a,b) = 1 + \frac{a f(a+1,b+1) + (x-a)f(a+1,b)}{x},\qquad f(x,b)=y-b, f(a,y)=0 . $$ Maybe think of this as a random walk. We have times $a=1, a=2, \dots$. We begin at point $0$. At time $a$, we either move right by one step (with probability $a/x$) or remain where we are (with probability $1-a/x$). Thus, at time $1$ we are fairly likely to stay put, unlikely to move. But as time passes, we become more likely to move, less likely to stay put. Until at time $a=x$ (and after) we are certain to move. The question is: how long does it take to reach point $y$? The expected time is our solution $f(1,0)$.