0

Let $R(n)$ returns an integer in the range $0,1,...,nāˆ’1$ with uniform probability. Note that this is not a true function in the mathematical sense, as inputting the same number a second time will not necessarily yield the same result. The random number generator only works for $n > 1$. Starting from a googol, $x_0 = 10^{100}$, consider the sequence $x_i = R(x_{iāˆ’1})$. Eventually the sequence terminates when $x_s = 0$ for some $s$ and no further generation is possible. What is $E[s]$?

Intuition: $R(x_i)$ generates a midpoint on average and imagine a number line cut in half. Hence, $E[s]$ is equivalent to the number of cuts until we're left with nothing but $0$ (in some sense).

So, $E[R(n)] = \frac{n-1}{2}$ for $n \geq 1$.

$E[R(10^{100})] = \frac{10^{100}-1}{2} = \frac{1}{2}\cdot10^{100}-\frac{1}{2}$

$E[R(\frac{10^{100}-1}{2})] = \frac{1}{2^2}\cdot10^{100} - \frac{1}{2^2}$

In general, we want to find $k$ such that

$\frac{1}{2^k}10^{100} - \frac{1}{2^k} = 1$. Solving for $k$ , I get $k = \log_2{(10^{100}-1)} = E[s]$. Is this the right approach?

Ted
  • 365
  • I changed it to log base 2. ā€“ Ted Jan 12 '20 at 20:58
  • In the question I linked to as a duplicate (which, interestingly, suggests the same incorrect solution with $\log_2$), the chosen number and all lower ones are removed from future draws. You're removing the chosen number and all higher ones, but it's basically the same problem (you can relabel the balls with the numbers reversed). See also Dynamic urn problem, which is the same problem except that the chosen number itself isn't removed from future draws. The answers there provide some further perspectives on the solution. ā€“ joriki Jan 12 '20 at 22:22

0 Answers0