# Union of random intervals with total length equal to infinity

Let $a_1,a_2,\dots$ be a sequence of positive numbers less than $1$, such that $$\sum_{n=1}^\infty a_i= \infty,$$ and $S^1 = \mathbb{R}/\mathbb{Z}$.

Suppose $I_1,I_2,\dots$ be random intervals with respective lengths $a_1,a_2, \dots$in $S^1$ such that the distribution of the centers of $I_n$ (for every $n$) are uniform and independent.

It can be shown that with probability $1$, $I = \cup_{n=1}^\infty I_n$ is a full measure subset of $S^1$. Is it true that "With probability $1$, $I = S^1$"? If this is not always true, does there exist a good characterization of the sequences $\{ a_n\}_{n=1}^{\infty}$ with this property?

Edit. A more precise question: "What happens in the special case $a_n = \frac1n$?"

## 3 Answers

This is a refinement of Iosif Pinelis's answer, so we shall be somewhat brief. For a punchline, jump to the "Added" section below.

We claim that if $a_n>c/n$ holds some $c>1$ and for all $n\geq n_0$, then $P(I=S^1)=1$. To see this, fix a large integer $N$ and any interval $J$ of length $1/N$. Then, $$P(J\not\subseteq I)\leq\prod_{n_0\leq n<cN}\left(1-\left(\frac{c}{n}-\frac{1}{N}\right)\right)<\exp\left(\sum_{n_0\leq n<cN}\left(\frac{1}{N}-\frac{c}{n}\right)\right)=O_c(N^{-c}).$$ As $S^1$ is a union of $N$ intervals of length $1/N$, $$P(I\neq S^1)=O_c(N^{1-c}).$$ The right hand side tends to zero as $N\to\infty$, hence $P(I\neq S^1)=0$ as claimed.

Added. Using Google I found out that Shepp (1971) aswered the question completely (see here). In particular, $P(I=S^1)=1$ holds when $a_n\geq 1/n$ for all $n\geq n_0$.

• Nice improvement. As for Shepp, it's very hard to compete with him anyway, but especially in a tight time frame. :-) Aug 14, 2018 at 17:40

$\newcommand{\ep}{\varepsilon}$

Without loss of generality (wlog), $a_1\ge a_2\ge\cdots$ and $a_n\to0$ as $n\to\infty$. Then a sufficient condition for $P(I=S^1)=1$ is that for some real $k>3/4$ and all large enough $n$ we have $a_n\ge\frac kn\,\ln n$. Indeed, take any real $\ep\in(0,1/2)$ and let
$$n_\ep:=\max\{n\colon a_n>3\ep/2\},$$ so that $$n_\ep\ge\frac{2k-o(1)}{3\ep}\,\ln\frac1\ep;$$ all the limits here are taken for $\ep\downarrow0$.

Take any interval $J$ of length $\ep$, centered at some point $x$. Then $$P(J\not\subseteq I)\le P(d(X_j,x)\ge\ep\ \forall j\le n_\ep) =(1-2\ep)^{n_\ep},$$ where $X_j$ is the center of the random interval $I_j$ and $d(X_j,x)$ is the distance from $X_j$ to $x$. Let now $J_1,\dots,J_{m_\ep}$ be intervals of length $\ep$ each such that $J_1\cup\dots\cup J_{m_\ep}=S^1$; wlog, $m_\ep\sim1/\ep$. Thus, \begin{multline} P(I\ne S_1)\le\sum_{i=1}^{m_\ep} P(J_i\not\subseteq I)\le m_\ep(1-2\ep)^{n_\ep} \le m_\ep e^{-2\ep n_\ep} \\ \le\frac{1+o(1)}\ep\,\exp\Big\{-\frac{4k}{3+o(1)}\,\ln\frac1\ep\Big\}\to0, \end{multline} so that $P(I\ne S_1)=0$, as claimed.

• See the "Added" section in my response. Aug 14, 2018 at 16:33

I would say that no, it is not true.

An idea for the example is as follows. Imagine that you are having 100 intervals of length 1/100, 100000 of length 1/10000, 10^6 of length 1/10^6, etc. The sum of their lengths clearly diverges. Now, what happens for the set left? I am going to modify your process: imagine that the intervals of length 1/N have only discrete allowed positions, $[\frac{k}{N},\frac{k+1}{N}]$, where k=0,1,...,N-1.

It is, formally speaking, a different process and a different question. However, they seem sufficiently alike (and I would say that there is a way to deduce the conclusion for the original one).

Now, for this modified process, if you are considering a given interval of length 1/N at the time when N intervals of length 1/N are being placed, it has a probability of survival $(1-1/N)^N \approx 1/e$. And though it is not independent for different intervals, I guess we can safely say that about $1/e$-th proportion of such intervals survives.

The intervals come in waves: the first wave of N=100 intervals of length 1/100, the second of $N=10^4$ intervals of length $1/10^4$, etc. Each interval that has survived one wave is decomposed into a 100 intervals that face the next one. And about $1/e$-th proportion of them survive.

So there is an (almost: remember, no independence!) Galton-Watson tree with the expectation of $100/e>1$ descendants of each interval, and hence with positive probability there is an exponential growth of number of surviving intervals, in the limit defining a Cantor set that in a complement to the union of intervals placed.

Finally, to get back to the original process, you can consider that an interval $[\frac{k}{N},\frac{k+1}{N}]$ is removed from the complement once it is intersected by one of the randomly placed intervals of length $1/N$. Then each interval still has an $\approx 1/e^2$ chance of survival, and I'm sure whichever way you use to handle the above argument formally, it will still be applicable here.