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$?"

up vote 7 down vote accepted

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

  • 1
    Nice improvement. As for Shepp, it's very hard to compete with him anyway, but especially in a tight time frame. :-) – Iosif Pinelis Aug 14 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
\begin{equation} n_\ep:=\max\{n\colon a_n>3\ep/2\}, \end{equation} so that \begin{equation} n_\ep\ge\frac{2k-o(1)}{3\ep}\,\ln\frac1\ep; \end{equation} all the limits here are taken for $\ep\downarrow0$.

Take any interval $J$ of length $\ep$, centered at some point $x$. Then \begin{equation} P(J\not\subseteq I)\le P(d(X_j,x)\ge\ep\ \forall j\le n_\ep) =(1-2\ep)^{n_\ep}, \end{equation} 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. – GH from MO Aug 14 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.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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