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.

  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Dec 20 '18 at 17:07
  • $\begingroup$ 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. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.