# Estimating the size of the remainder in a random partition

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.

• It seems obvious that your quantity decays exactly like $(1-x_{f(j)})$, where (given a sequence $y_j$) $f(j)$ returns the index $i$ which is greatest so that $x_i$ is larger than all $y_k$ chosen for $k$ at most $j$, and the probability that this happens is $(x_f(j))^j$. Really you should ask what the likely $j$ is that $y_j \gt x_1$, which should be an elementary calculation. I (and perhaps others) may be misunderstanding what you are after, in which case rephrasing your question might help. Gerhard "Stretch Your Muscle Of Clarification" Paseman, 2018.12.20. – Gerhard Paseman Dec 20 '18 at 17:07
• I see now that I misunderstood. $J$ is not an initial interval $[0,x_{f(j)}]$ of the unit interval , but often is a proper subset of this initial interval. In which case, the sub problem of determining when two y's land in the same $I_k$ is of interest in solving this problem. Gerhard "Sorry For Misreading The Problem" Paseman, 2018.12.20. – Gerhard Paseman Dec 20 '18 at 17:22

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$$.