Estimating the size of the remainder in a random partition

Question

Pick a sequence of real numbers $x_i$ as follows. Put $x_0=1$. If $x_i$ is chosen, then pick $x_{i+1}\in[0, x_i]$ according to the uniform distribution. Obviously we have $x_i\rightarrow 0$ with probability 1. Put $I_i=[x_i, x_{i-1}]$.

Next we pick $n$ random numbers $y_1, \ldots, y_n$ in $[0, 1]$ independently with respect to the uniform distribution. Let $J$ be the union of all $I_i$, for which there exists some $y_j$ with $y_j\in I_i$. Again it is obvious that $|J|\rightarrow 1$ as $n\rightarrow\infty$ with probability 1. My question is how quickly does $1-|J|$ decay? I would expect that the distribution of $1-|J|$ is not very concentrated, so I am interested both in an estimate for the expected value as for median and extreme values.

The above problem occurs quite naturally in the analysis of algorithms, so I would expect that this problem has been addressed by someone. Several random structures have parts of sizes following the distribution of the $x_i$, and picking $y_i$ corresponds to picking random points in a random structure and studying the component containing this point. The question is then how much of the whole structure has been left unexplored.

Answer 1

Here is a heuristic that I am sure can be made rigorous. The $x_i$'s can be written recursively as $x_{i+1}=U_{i+1}x_i$, where the $U_i$ are independent Unif[0,1] random variables. In particular, $x_n=U_n\cdots U_1$, so that $\log x_n=\log U_n+\ldots+\log U_1$. By the strong law of large numbers, $(1/n)\log x_n\to \int_0^1\log t\,dt=-1$, so that $x_n\approx e^{-n}$. (More precisely, the ratio between $x_n$ and $e^{-n}$ is sub-exponential, and is typically something like $e^{\pm\sqrt n}$).

At a heuristic level, the intervals are decreasing in length exponentially to 0. Since the sum of a geometric series is very close to its largest term, the uncovered part of the interval after $n$ $y$'s have been selected is essentially of the order of the length of the smallest numbered $I_i$ that has yet to be hit. The length of this interval is of the order of $x_i$. But: hitting $I_i$ is morally equivalent to hitting $\bigcup_{j\ge i}I_j$, so the fraction of the interval that has yet to be hit after $n$ $y$'s have been chosen is approximately $\max\{x_i\colon x_i<\min_{k=1}^n y_k\}$. But this is approximately just $\min_{k=1}^n y_k$ which is something like $1/n$.