First time questioner here. I'm working on a problem from a recreational math website, but trying to understand an easier version first. Most such problems are discrete, and the continuous nature of this one is confusing me.
The simpler problem: we start with the range $[0,1]$. Pick a random number uniformly from that range, and remove everything above your pick. Do that repeatedly, picking a random number from the range that's left, until the remaining range drops below some fraction $1/x$. What's the average number of picks required?
Consider a sequence of rvs $X_1, X_2, \dots$, where $X_1 \sim U(0,1)$ and $X_i \sim U(0,X_{i-1})$ for $i \ge 2$. We want to know the expected number of steps it will take until an $X_n$ is picked below some fraction $1/x$. That is, given $1 \gt X_1 \gt X_2 \gt \dots \gt X_{n-1} \gt \frac 1 x \gt X_n$, what's the expected value of $n$?
I know the closed form for this simpler problem, thanks to Monte Carlo simulations. Playing around with various $x$ and running for billions of simulations, the counts for each possible $n$ are easy to pick out in closed form, and shows (with Wolfram Alpha's help) that $$\mathbb{E}[n] = \sum_{n=1}^\infty n \frac{(\log x)^{n-1}} {(n-1)! x} = \log x + 1$$
So $P(n = 1) = \frac 1 x$, which is obvious. $P(n = 2) = \frac {\log x} x$, which I think I can get as follows. The PDF for $X_2$ is $1/{X_1}$, so the CDF is $P(X_2 \lt t) = t/X_1$. I want to know $P(X_2 \lt \frac 1 x)$, so I need to integrate that over the range of possible $X_1$:
$$P(X_2 < 1/x < X_1) = \int_{1/x}^1 \frac{dX_1}{x X_1} = \frac{\log x} x$$
But now, how do I get that $P(X_3 < 1/x < X_2 < X_1 < 1) = (\log x)^2/(2x)$? I suspect I need a double integral on $dX_2\ dX_1$, but what? The way the log appears in $\mathbb{E}[n]$ makes it look like the $\log x$ gets introduced via one of the integration bounds, but that can't be right, can it?
My last college stats class was 40 years ago, and my knowledge since then is mostly driven by solving these website questions. So that knowledge is really spotty. The fact that $\mathbb{E}[n]$ looks like a power series suggests this has to do with moment generating functions, I guess, but I'm really out of my depths there.
I've actually "solved" the full problem by using a discrete analogue, starting with $4\cdot 10^{10}$ stones and finding $\mathbb{E}[n]$ to reduce that to 1/40th the original count. That used logic related to 2025645, where harmonic numbers are in play. But that took too long and was off by 8 in the required 10th decimal place. A fast answer that doesn't involve guessing the final digits needs a continuous method, which is eluding me.
Best Answer
Let $E(x)$ denote the expected number of steps required to obtain a number less than $1/x$.
If $X_1 < 1/x$, then the process is complete; this occurs with probability $1/x$. Otherwise, $X_1 > 1/x$, and suppose $X_1 = y$. We are now choosing $X_2, X_3, \cdots$ from the interval $[0,y]$ and want to know the number of steps required to obtain a result less than $1/x$; since this is simply a "scaled version" of the original process, it will take $E(xy)$ additional steps on average.
Thus, $E(x)$ satisfies the integral equation $$E(x) = \frac{1}{x} + \int_{1/x}^{1} (1+ E(xy))\, dy =1+ \frac{1}{x} \int_{1}^{x} E(y)\, dy$$ Differentiating this gives $E(x) + xE'(x) = 1+ E(x)$, so $$E'(x) = 1/x \implies E(x) = \ln(x) + C$$ Using the initial value $E(1) = 1$, we conclude $E(x) = \ln(x) + 1$.