# Expected number of attempts to reach $0$

Let $N$ be a natural number. We uniformly choose a random number between $1$ and $N$ (both inclusive) and subtract it from $N$. If we repeat this on the new number obtained, what is the expected number of trials needed to reach $0$?

The crux is that the limits of random distribution change depending on the previous number. How can we handle this?

Edit: Random number in range [1, N] i.e. you have N choices for the random number, each one having the same probability of 1/N (uniform distribution).
Then after subtracting, the resultant number obtained becomes new N. So, N is not constant. N is changing according to the previous random number.

A more practical version: you have N chocolates and you eat some random number (as described above) each day. After how many days will the chocolates get over?

As a follow-up to the discrete case, what if the uniform distribution is continuous?

• What is the average value they take? $\frac{N+0}{2}$, so you subtract that from $N$ and repeat. – Zelos Malum Nov 22 '16 at 11:05
• @ZelosMalum It is not obvious that average number of tries is the same as average number of average subtractions (it's wrong, actually: for $N=1$ answer is $2$, for $N=2$ answer is ${5 \over 2}$ while average subtraction is $1$). – Abstraction Nov 22 '16 at 11:15
• What if the next draw exceeds the remainder ? – Yves Daoust Nov 22 '16 at 11:40
• "Between $0$ and $N$": inclusive ? – Yves Daoust Nov 22 '16 at 11:42
• I assume that all the random numbers chosen are in the interval [1,N], and you do not change the interval to be [1, new number] as the sentence "repeat this on the new number obtained". If so then your question is equivalent to this problem : math.stackexchange.com/questions/1977628/… and the answer is (asymptotically) $e$ – Thanassis Nov 22 '16 at 12:18

Let $z(N)$ be your expected number of subtractions. Then $z(1) = 1$ and $$z(n+1) = 1 + {1 \over n+1} \left(0 + z(1) + \dots + z(n)\right)$$ From here, for $n > 1$: \begin{align}z(n+1) &= 1 + {1 \over n+1}\left(z(1) + \dots + z(n)\right) \\ (n+1)z(n+1) &= z(1) + \dots + z(n-1) + z(n) + n+1 \\ (n+1)z(n+1) &= nz(n) + z(n) + 1 \\ z(n+1) &= z(n) + {1 \over n+1} \\ z(n) &= 1 + {1 \over 2} + \dots + {1 \over n} = H_n\end{align} where $H_n$ is $n$-th harmonic number.
• Why does $z(1)=2$ ? – Yves Daoust Nov 22 '16 at 11:45
• @YvesDaoust When $N=1$ you pick from $\{0,1\}$ uniformly; so the count of tries from there until the end has a geometric distribution with expected value $2$. – Graham Kemp Nov 22 '16 at 12:05
• @Thanassis Changed the answer. Interesting how difference between $[0,N]$ and $[1,N]$ intervals is constant while first corresponds to situation with no upper bound for a number of steps... – Abstraction Nov 22 '16 at 13:21
• I like your solution, but I am not sure how you get from the second line to the third line (i.e., how do you get $nz(n)$ from $z(1)+z(2)+...+z(n-1)$) – Thanassis Nov 22 '16 at 14:32