Consider the setup where one has $N$ urns indexed as $1, 2, \dots N$. At time $t$, an urn is chosen uniformly at random. Let the index of the selected urn at time $t$ be $i_t$. If the chosen urn contains less than $s$ balls, then I drop a ball in all the urns with index $\leq i_t$. If $X_t$ is the indicator variable that denotes whether I had to drop a ball at time $t$ (i.e. the urn $i_t$ had less than $s$ balls), then I am interested in finding $\displaystyle \mathbb{E}\left[ \sum_{t = 1}^{\infty} X_t \right]$. More specifically, I am looking for tight lower bounds on the same.
So far, I have been able to solve the simple case of $s = 1$. This can be casted a simple recursion. If $G(N)$ denotes the required sum for $N$ urns then we have the recursion given as $\displaystyle G(N) = 1 + \frac{1}{N} \sum_{k = 1}^N G(N - k) $ with $G(0) = 0$. This simply follows from the fact that if in the first trial the $k^{\text{th}}$ urn is selected then the problem essentially boils down to original one with $N - k$ urns giving us the required recursion. This recursion has a very nice closed form expression as $G(N)$ is essentially the $N^{\text{th}}$ harmonic number. Now for the case of $s = 2$, I used the same approach of forming a recursion. However, this time the recursion is more involved as it is function of two variables, the number of urns that have one balls and the number of urns that don't have any ball. I couldn't find any simple way to solve that recursion except for numerically computing it using a program.
I was wondering if there is some simpler way to solve this problem for the case of general $s$ or simpler way to evaluate the recursion. Intuitively speaking, I feel the value the should be very close to $sG(N)$ (slightly lower than that) but I am unable to prove the same. Any leads or references would be appreciated! Thanks!
An urn contributes to the sum each time it is chosen out of the first $s$ times that it or any higher urn is chosen. The $j$-th urn from the top (with index $N-j+1$) has probability $\frac 1j$ to be chosen in each of these $s$ choices, so we expect it to contribute $\frac sj$. Thus the expected value of the sum is
$$ \sum_{j=1}^N\frac sj=sH_N\;. $$