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.



Estimating the size of the remainder in a random partition
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$. 


