Gambling puzzle

A math friend of mine showed me this strange gambling puzzle. There is a button in a casino and every time you press it you can win either $1$ or $0$ dollars. The probability of winning $1$ dollar depends on how many times you have pressed it so far. If you press it for the $x$-th time you have probability $x/M$ of winning a dollar. If $x$ gets to $M$ or greater then you just win a dollar every time.

How many button presses do you expect to have to press to win $N$ dollars?

Solution 1:

Caution: This answer is WRONG. But I leave it here since my mistake may help to understand the question correctly. See edit in the last.

Suppose you play $L$ times. If $L > M$ then you will get $$ \begin{align*} E(L) &= \frac{1}{M} + \frac{2}{M} + \cdots + \frac{M}{M} + 1 + \cdots + 1 \\ &= \frac{1}{2}(M + 1) + (L - M) \end{align*}$$ dollars. Otherwise you will get $$ \begin{align*} E(L) &= \frac{1}{M} + \frac{2}{M} + \cdots + \frac{L}{M} \\ &= \frac{1}{2M}L(L + 1) \end{align*}$$ dollars. Hence, all you need to do is solve $E(L) = N$ for $L$: the answer would be $$L = \begin{cases} N + \frac{M - 1}{2} \qquad \left(N > \frac{1 + M}{2}\right) \\ \frac{-1 + \sqrt{1 + 8MN}}{2} \qquad \left(N \leq \frac{1 + M}{2}\right). \end{cases}$$

Edit I: Thanks to Steven Stadnicki, I realize I was completely wrong. Even in case $N > M$, the expected value is $$ N \frac{M!}{M^M} + \sum_{k = 1}^{M - 1} (N + k) \frac{M!}{M^M} \sum_{0 < n_1 < \cdots < n_k < M} \prod_{i = 1}^k \frac{M - n_i}{n_i} $$ but I cannot get its simpler form.

Edit II: I conduct a computational experiment and get the average values for $10^4$ trials to guess the expected value $E(M, N)$ as follow. $$\begin{array}{l|lllll} M \backslash N & 1 & 2 & 3 & 4 & 5 \\ \hline \\ 1 & 1 & 2 & 3 & 4 & 5 \\ 2 & 1.5 & 2.5 & 3.5 & 4.5 & 5.5 \\ 3 & 1.9 & 3.0 & 4.0 & 5.0 & 6.0 \\ 4 & 2.2 & 3.5 & 4.5 & 5.5 & 6.5 \\ 5 & 2.5 & 3.9 & 5.0 & 6.0 & 7.0 \end{array}$$

Solution 2:

In the case of $N \geq M$....

Let $W$ be the winnings after the first $M$ plays. Let $L$ be the number of plays required to win $N$ dollars.

Then $L = M + (N - W)$.

Thus we can compute

$$ E(L) = M + N - E(W) = M + N - \sum_{i=1}^M \frac{i}{M} = \frac{1}{2}M + N - \frac{1}{2} $$

that is, on average, it takes $\frac{1}{2} M + N - \frac{1}{2}$ plays to win $N$ dollars.