2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What is the average value they take? $\frac{N+0}{2}$, so you subtract that from $N$ and repeat. $\endgroup$ – Zelos Malum Nov 22 '16 at 11:05
  • $\begingroup$ @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$). $\endgroup$ – Abstraction Nov 22 '16 at 11:15
  • $\begingroup$ What if the next draw exceeds the remainder ? $\endgroup$ – Yves Daoust Nov 22 '16 at 11:40
  • $\begingroup$ "Between $0$ and $N$": inclusive ? $\endgroup$ – Yves Daoust Nov 22 '16 at 11:42
  • 1
    $\begingroup$ 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$ $\endgroup$ – Thanassis Nov 22 '16 at 12:18
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why does $z(1)=2$ ? $\endgroup$ – Yves Daoust Nov 22 '16 at 11:45
  • $\begingroup$ @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$. $\endgroup$ – Graham Kemp Nov 22 '16 at 12:05
  • 1
    $\begingroup$ It seems (from later comments) that the OP meant that the interval is [1,N] and not [0,N]. So z(1) should be 1. Also shouldn't z(2) be 1.5 instead of 2? $\endgroup$ – Thanassis Nov 22 '16 at 12:34
  • $\begingroup$ @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... $\endgroup$ – Abstraction Nov 22 '16 at 13:21
  • $\begingroup$ 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)$) $\endgroup$ – Thanassis Nov 22 '16 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.