Exercise :
Every time you visit a certain restaurant, you choose randomly one of its $N$ dishes. What is the expected number of visits you have to make to the restaurant until you taste all of its dishes ?
Attempt / Question :
Picking randomly one of its $N$ dishes, obviously means that you have $1/N$ chance of picking every dish. Now, each time you visit the restaurant and you pick a different dish than all the others, the probability of picking a different dish again becomes smaller, as $1/(N-n)$, where $n$ is the number of different dishes you've picked.
Now, I know that expected time (hitting time) problems of such can be solved by modelling your process into a Boundary Value Problem (BVP) of the form (which will give an answer to the expected time $\mathbb{E}[T_A | X_0 = x] = \mathbb{E}_x[T_A]$) :
$$\begin{cases} Lg(x) = -1, x \notin A \\ g(x) = 0, x \in A\end{cases}$$
if $A \subset \mathbb{X}$ and $T_A = \inf\{k \geq 0 : X_k \in A\}$ the time of the first arrival at $A$.
On this particular problem, though, I find myself stuck on trying to model it into an boundary value problem.
I would really appreciate any explanation on how to proceed.
Let $f(n)$ be the expected time to sample the remaining $n$ dishes, given that you have sampled $N-n$ dishes already. We are interested in calculating $f(N)$.
It is easy to see that $f$ satisfies the recursion
\begin{align*} f(n) &= \frac{N-n}{N}[f(n)+1] + \frac{n}{N}[f(n-1)+1] \\ &= 1 + \frac{N-n}{N}f(n) + \frac{n}{N}f(n-1). \end{align*}
We also have the boundary condition $f(0)=0$. We can simplify the equation above to find
$$f(n) = \frac{N}{n} + f(n-1).$$
This gives us that
$$ f(n) = \sum_{k=1}^{n}\frac{N}{k}, $$
so that
$$ f(N)= \sum_{k=1}^N \frac{N}{k}. $$