# Uniform Random Covering Problems

Henna Koivusalo, Lingmin Liao, Tomas Persson

<figure><img src="image_1.png" /></figure>

## To cite this version:

Henna Koivusalo, Lingmin Liao, Tomas Persson. Uniform Random Covering Problems. International Mathematics Research Notices, 2021, 2023 (1), pp.455-481. 10.1093/imrn/rnab272. hal-04281216

HAL Id: hal-04281216

https://hal.science/hal-04281216v1

Submitted on 20 Sep 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>
# Uniform Random Covering Problems

## Henna Koivusalo¹*, Lingmin Liao² and Tomas Persson³

¹School of Mathematics, University of Bristol, Fry Building, Woodland Road, Bristol BS8 1UG, UK, ²Université Paris-Est Creteil, CNRS, LAMA, F-94010 Creteil, France, and Université Gustave Eiffel, LAMA, F-77447 Marne-la-Vallée, France, and ³Centre for Mathematical Sciences, Lund University, Box 118, 221 00 Lund, Sweden

*Correspondence to be sent to: e-mail: henna.koivusalo@bristol.ac.uk

Motivated by the random covering problem and the study of Dirichlet uniform approximable numbers, we investigate the uniform random covering problem. Precisely, consider an i.i.d. sequence $\omega = (\omega_n)_{n \ge 1}$ uniformly distributed on the unit circle $\mathbb{T}$ and a sequence $(r_n)_{n \ge 1}$ of positive real numbers with limit 0. We investigate the size of the random set

$$ \mathcal{U}(\omega) := \{y \in \mathbb{T} : \forall N \gg 1, \exists n \le N, \text{ s.t. } |\omega_n - y| < r_N\}. $$

Some sufficient conditions for $\mathcal{U}(\omega)$ to be almost surely the whole space, of full Lebesgue measure, or countable, are given. In the case that $\mathcal{U}(\omega)$ is a Lebesgue null measure set, we provide some estimations for the upper and lower bounds of Hausdorff dimension.

## 1 Introduction

Let $\mathbb{T} = \mathbb{R}/\mathbb{Z}$ be the one-dimensional torus. Denote by $|\cdot|$ the distance of a point in $\mathbb{T}$ to the point 0. The famous Dirichlet theorem states that for any real numbers $\theta$ and $N \ge 1$, there exists an integer $1 \le n \le N$, such that $|n\theta| < N^{-1}$. As a corollary, for any real number $\theta$, there exist infinitely many positive integers $n$, such that $|n\theta| < n^{-1}$.

Received March 2, 2021; Revised August 2, 2021; Accepted August 25, 2021
Communicated by Prof. Barak Weiss

© The Author(s) 2021. Published by Oxford University Press. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted reuse, distribution, and reproduction in any medium, provided the original work is properly cited.
The Dirichlet theorem and its corollary tell us that for any $\theta$, in two different ways, 0 is approximated by the sequence $(n\theta)_{n\ge 1}$ with degree-one-polynomial speed. Such two different ways are called uniform approximation (uniform with respect to $N$) and asymptotic approximation in the survey paper of Waldschmidt [17].

In general, one can study the approximation of any point $y$ by the sequence $(n\theta)_{n\ge 1}$ with a faster speed. For the asymptotic approximation, in 2003, Bugeaud [2] and, independently, Schmeling and Troubetzkoy [16] proved that for any irrational $\theta$, for any $\alpha > 1$, the Hausdorff dimension of the set

$$ \{ y \in \mathbb{T} : |n\theta - y| < n^{-\alpha} \text{ for infinitely many } n \} $$

is $1/\alpha$. The corresponding uniform approximation problem was quite recently studied by Kim and Liao [10] who proved that the Hausdorff dimension of the set

$$ \mathcal{U}[\theta, \alpha] := \{ y \in \mathbb{T} : \forall N \gg 1, \exists n \le N, \text{ s.t. } |n\theta - y| < N^{-\alpha} \} $$

depends on the irrationality exponent of $\theta$ defined by $w(\theta) := \sup\{s > 0 : \liminf_{j \to \infty} j^s |j\theta| = 0\}$. Specially, when $w(\theta) = 1$ (thus for Lebesgue almost all $\theta$), the Hausdorff dimension of $\mathcal{U}[\theta, 1]$ is between 1/2 and 1. For the complicated dimensional formulae and estimations, one can consult [10].

Motivated by these metric number theory results, one wonders about the analog results when the sequence $(n\theta)_{n\ge 1}$ is replaced by an i.i.d. sequence. In fact, for the asymptotic approximation, this is nothing but the widely studied Dvoretzky covering problem. Let $(\omega_n)_{n\ge 1}$ be an i.i.d. random sequence of uniform distribution on the torus $\mathbb{T}$. Let $(r_n)_{n\ge 1}$ be a decreasing sequence of positive real numbers with $\sum_{n=1}^{\infty} r_n = \infty$. In 1956, Dvoretzky [3] asked what are necessary and sufficient conditions on $(r_n)_{n\ge 1}$ such that almost surely, all points in $\mathbb{T}$ are covered by infinitely many open intervals with centre $\omega_n$ and radius $r_n$, or equivalently,

$$ P(\{y \in \mathbb{T} : |\omega_n - y| < r_n \text{ for infinitely many } n\} = \mathbb{T}) = 1. \quad (1) $$

This problem attracted much attention of mathematicians, such as Lévy, Kahane, Erdős, Billard, et al. (see Kahane's book [8] and his survey paper [9]). Specially, for the case $r_n = c/n$ ($c > 0$), Kahane [7] proved in 1959 that (1) holds when $c > 1$. In 1961, Erdős [4] announced that (1) holds if and only if $c \ge 1$ but never published a proof. In 1965, Billard [1] showed that (1) does not hold if $c < 1$. Finally, Orey [13] in 1971 and independently Mandelbrot [12] in 1972, proved that (1) holds if $c = 1$. The complete solution to the Dvoretzky problem was given in 1972 by Shepp [15] who proved that (1) holds if and
only if

$$ \sum_{n=1}^{\infty} \frac{1}{n^2} \exp(r_1 + \dots + r_n) = \infty. $$

When $r_n$ decreases to 0 faster, one is also interested in the Hausdorff dimension of the set of points that are covered infinitely often by the random intervals. In 2004, Fan and Wu [5] proved that almost surely, the Hausdorff dimension of the set

$$ \{y \in \mathbb{T} : |\omega_n - y| < n^{-\alpha} \text{ for infinitely many } n\} $$

is $1/\alpha$ for all $\alpha \ge 1$. Comparing with the above-mentioned result of Bugeaud and Schmeling-Troubetzkoy, one finds that the i.i.d. sequence exhibits some similar asymptotic approximation property as the irrational rotation sequence $n\theta$.

As a counterpart of the famous random covering problem that corresponds to the asymptotic Diophantine approximation, we would like to study the uniform covering problem that corresponds to the uniform Diophantine approximation. Analogously, for an i.i.d. random sequence $\omega = (\omega_n)_{n \ge 1}$ of uniform distribution and a real positive sequence $(r_n)_{n \ge 1}$, we want to describe the size (in the sense of Lebesgue measure and Hausdorff dimension) of the random set

$$ \mathcal{U}(\omega) := \{ y \in \mathbb{T} : \forall N \gg 1, \exists n \le N, \text{ s.t. } |\omega_n - y| < r_N \}. $$

If we let $B_{k,n} = B(\omega_k, r_n)$ be the ball with centre $\omega_k$ and radius $r_n$ and set

$$ E_n = \bigcup_{k=1}^{n} B_{k,n}, $$

then

$$ \mathcal{U}(\omega) = \liminf_{n \to \infty} E_n. $$

## 2 Main Results

Our 1st main theorem gives a sufficient condition and a necessary condition for $P(\mathcal{U}(\omega) = \mathbb{T}) = 1$.

### Theorem 1.

(i) If $\sum_{n=1}^{\infty} n(1 - r_n)^n < \infty$, then $\mathcal{U}(\omega) = \mathbb{T}$ almost surely.

In particular, if $r_n = \frac{c \log n}{n}$ with $c > 2$, then $\mathcal{U}(\omega) = \mathbb{T}$ almost surely.

(ii) If $\lim_{n \to \infty} n(1 - r_n)^n = \infty$, then $\mathcal{U}(\omega) \neq \mathbb{T}$ almost surely.

In particular, if $r_n = \frac{c \log n}{n}$ with $c < 1$, then $\mathcal{U}(\omega) \neq \mathbb{T}$ almost surely.
**Remark 1.** Note that the condition $\sum_{n=1}^{\infty} n(1-r_n)^n < \infty$ holds also for $r_n = \frac{2\log n + \gamma \log \log n}{n}$ with $\gamma > 1$.

As for the Lebesgue measure, denoted by $\lambda$, we have the following theorem.

**Theorem 2.**

(i) Assume that $(r_n)_{n \ge 1}$ is decreasing. Then, depending on $(r_n)_{n \ge 1}$, either $\lambda(\mathcal{U}(\omega)) = 1$ almost surely, or $\lambda(\mathcal{U}(\omega)) = 0$ almost surely.

(ii) Suppose that the sequence $(r_n)_{n \ge 1}$ is decreasing and that $(nr_n)_{n \ge 1}$ is increasing. We have $\lambda(\mathcal{U}(\omega)) = 1$ almost surely if and only if the sequence $(r_n)_{n \ge 1}$ satisfies

$$ \sum_{n=1}^{\infty} r_n = \infty \quad \text{and} \quad \sum_{n=1}^{\infty} r_n e^{-2nr_n} < \infty. \qquad (2) $$

In particular, if $r_n = \frac{c \log \log n}{2n}$, then $\lambda(\mathcal{U}(\omega)) = 1$ almost surely if and only if $c > 1$.

**Remark 2.** The condition (2) holds also for $r_n = \frac{\log \log n + \gamma \log \log \log n}{2n}$ with $\gamma > 1$.

We also give a sufficient condition that $\mathcal{U}(\omega)$ is countable.

**Theorem 3.** If $\sum_{n=1}^{\infty} nr_n < \infty$, then almost surely $\mathcal{U}(\omega) = \{\omega_k : k \in \mathbb{N}\}$.

Finally, some estimations of the Hausdorff dimension of $\mathcal{U}(\omega)$ are obtained in the following two theorems.

**Theorem 4.** If $r_n = \frac{c}{n}$ and $0 < c < \frac{1}{2}$, then almost surely

$$ \dim_{\mathbb{H}}\mathcal{U}(\omega) \le \inf_{\theta>1} \frac{\log \Lambda}{\log \theta}, $$

where

$$ \Lambda = \frac{1}{2} + \frac{c}{\theta}(\theta^2 - 1) + \sqrt{\left(\frac{1}{2} + \frac{c}{\theta}(\theta^2 - 1)\right)^2 - 2c(\theta - 1)(\theta^{-1} - \theta^{-2})}. $$

In particular, since $\inf_{\theta>1} \frac{\log \Lambda}{\log \theta}$ tends to 0 as $c \to 0$, we conclude that $\dim_{\mathbb{H}}\mathcal{U}(\omega) = 0$ almost surely when $r_n = 1/n^\alpha$ with $\alpha > 1$.
**Theorem 5.** If $r_n = \frac{c}{n}$ with $c > 0$, then almost surely

$$ \dim_H \mathcal{U}(\omega) \ge \sup_{\theta>1} \left( 1 - \frac{-\log(1 - \exp(-2c^{\frac{\theta-1}{\theta^2}}))}{\log \theta} \right). $$

In particular, (let $\theta = 8.6$), if $r_n = \frac{1}{n}$, then almost surely

$$ \dim_H \mathcal{U}(\omega) \ge 0.2177444298485995. $$

Below is an illustration of the dimension bounds provided by Theorems 4 and 5. Note that there is no $c$ for which the dimension is known to be intermediate, but at least Theorems 4 and 5 show that $r_n = \frac{c}{n}$ is the "right" quantity to look at, in the sense that for such sequences $(r_n)_{n \ge 1}$ there is a chance for the dimension to be intermediate.

<figure><img src="image_3.png" /></figure>

The proofs of the above results are given in Sections 5–8.

### 3 Zero-One Law for the Events {$\mathcal{U}(\omega) = \mathbb{T}$} and {$\dim_H \mathcal{U}(\omega) = s$}

Theorem 2 shows that the zero-one law holds for the events {$\lambda(\mathcal{U}(\omega)) = 1$} and {$\lambda(\mathcal{U}(\omega)) = 0$}. Theorem 1 indicates that the zero-one law may also hold for the event {$\mathcal{U}(\omega) = \mathbb{T}$}. In this section, we confirm this guess. Further, we also show that for any $0 \le s \le 1$, the event {$\dim_H \mathcal{U}(\omega) = s$} has probability 0 or 1.

The arguments in this section were provided to us by Jeffrey Steif.

Let us begin with the following slightly generalised version of the Kolmogorov zero-one law.

**Lemma 1.** Let $X_1, X_2, \dots$ be a sequence of independent random variables, and let $A$ be an event measurable with respect to the $\sigma$-algebra generated by this sequence. Assume, furthermore, that for any $n$ there is an event $A_n$ such that $A$ and $A_n$ only differ on a set of null probability, and $A_n$ is measurable with respect to the $\sigma$-algebra $\sigma(X_n, X_{n+1}, \dots)$. Then, $A$ has probability either 0 or 1.

**Proof.** Assume, to the contrary, that $P(A) = c$ with $0 < c < 1$, and let $0 < \varepsilon < c$. Take $k$ so large that there is an event $A'$ measurable with respect to $\sigma(X_1, \dots, X_k)$ such that $P(A \Delta A') < \varepsilon$.
Let $A_{k+1}$ be as in the assumption: a set differing from $A$ only on a set of null probability, and in the $\sigma$-algebra $\sigma(X_{k+1}, X_{k+2}, \dots)$. Then, $A_{k+1}$ is clearly independent of $A'$ and, consequently, so is $A$.

Note that

$$P(A \cap A') \geq c - \varepsilon \text{ and } P(A)P(A') \leq c(c + \varepsilon).$$

Thus, $c - \varepsilon \leq c(c + \varepsilon)$. However, since $0 < c < 1$, this is impossible when $\varepsilon$ is small. ■

**Theorem 6.** Assume that the sequence $(r_n)_{n \geq 1}$ is decreasing. Let $0 \leq s \leq 1$. The events $\{U(\omega) = \mathbb{T}\}$ and $\{\dim_H U(\omega) = s\}$ satisfy a zero-one law.

**Proof.** Define

$$U_k(\omega) = \{y \in \mathbb{T} : \forall N \gg 1, \exists n \in \{k, \dots, N\}, \text{ s.t. } |\omega_n - y| < r_N\}.$$

Notice that $U(\omega) = U_1(\omega)$ and that

$$U_k(\omega) \subset U(\omega) \subset U_k(\omega) \cup \{\omega_1, \dots, \omega_{k-1}\}. \qquad (3)$$

We will first focus on the event $A = \{U(\omega) = \mathbb{T}\}$. Fix $x \in \mathbb{T}$. We will show as part of the proof of Theorem 2 part (i) below that $P(x \in U(\omega))$ is either 0 or 1. If $P(x \in U(\omega)) = 0$, then $P(A) = 0$ and we are done. So, assume that $P(x \in U(\omega)) = 1$. Note that

$$A \cap \{\omega_1, \dots, \omega_{k-1}\} \subset U_k(\omega) \subset \{U_k(\omega) = \mathbb{T}\}.$$

Since $P(x \in U(\omega)) = 1$, we have $P(\{\omega_1, \dots, \omega_{k-1}\} \subset U_k(\omega)) = 1$. Hence, $A$ and $\{U_k(\omega) = \mathbb{T}\}$ only differ on a set of null probability. Since $\{U_k(\omega) = \mathbb{T}\}$ does not depend on the 1st $k$ terms of $\omega$, we can apply Lemma 1 to deduce the claim.

Now, we prove the zero-one law for the Hausdorff dimension. By (3), and since Hausdorff dimension does not depend on any finite number of points, we know that

$$\{\dim_H U(\omega) \geq s\} = \{\dim_H U_k(\omega) \geq s\}.$$

Since $\{\dim_H U_k(\omega) \geq s\}$ is a tail event, we can apply the usual Kolmogorov zero-one law to deduce that $\{\dim_H U_k(\omega) \geq s\}$ has probability either 0 or 1. This then implies the zero-one law for $\{\dim_H U(\omega) = s\}$. ■

# 4 Open Questions and Problems

Our results do not give a complete picture of the size of the set $U(\omega)$. We list below some open questions and problems.
1. What is a necessary and sufficient condition on $(r_n)_{n \ge 1}$ for $P(\mathcal{U}(\omega) = \mathbb{T}) = 1$? In particular, for $r_n = \frac{c \log n}{n}$ with $1 \le c \le 2$, which is the critical value of $c$ such that $\mathcal{U}(\omega) = \mathbb{T}$ almost surely?

2. Give better dimension estimates of $\dim_{\mathbb{H}}\mathcal{U}(\omega)$ when $r_n = \frac{c}{n}$. In particular, is there a value of $c$ such that $P(0 < \dim_{\mathbb{H}}\mathcal{U}(\omega) < 1) = 1$?

## 5 Proof of Theorem 1 on Uniform Covering

In this section, we prove that Theorem 1 gives sufficient conditions for $\mathcal{U}(\omega) = \mathbb{T}$ to hold almost surely.

By Shepp [15, Formula (90)], we have

$$ 
\begin{aligned}
P(\mathbb{T} \not\subset E_n) &\le \frac{2(1-r_n)^{2n}}{\int_0^{r_n} (1-r_n-t)^n dt + \left(\frac{1}{4}-r_n\right)(1-2r_n)^n} \\
&= \frac{2(1-r_n)^{2n}}{\frac{(1-r_n)^{n+1}-(1-2r_n)^{n+1}}{n+1} + \left(\frac{1}{4}-r_n\right)(1-2r_n)^n}.
\end{aligned}
$$

For large enough $n$, we therefore have

$$ P(\mathbb{T} \not\subset E_n) \le \frac{2(1-r_n)^{2n}}{\frac{1}{n+1}(1-r_n)^{n+1}} = 2(n+1)(1-r_n)^{n-1}. $$

Hence, if $\sum_{n=1}^{\infty} n(1-r_n)^n < \infty$, then $P(\mathbb{T} \not\subset E_n)$ is summable. By Borel-Cantelli lemma, it follows that almost surely, $E_n = \mathbb{T}$ for all but finitely many $n$.

For the special case $r_n = c \log n/n$ ($c > 2$), one can easily check that $\sum_{n=1}^{\infty} n(1-r_n)^n < \infty$. The 1st part of the theorem is thus proved.

For the 2nd part, assume that

$$ \lim_{n \to \infty} n(1-2r_n)^n = \infty. \qquad (4) $$

Let $P_{\epsilon,n,r}$ be the probability that an interval of length $\epsilon$ is not covered by $n$ uniformly distributed i.i.d. balls of radius $r$. This probability does not depend on the position of the interval of length $\epsilon$ that we consider (because of the uniform distribution).

Let $U_{n,r}$ be the union of the above-mentioned $n$ balls of radius $r$. By Shepp [15, Formulae (24) and (25)], we have

$$ P_{\epsilon,n,r} \ge \frac{\epsilon}{2} \frac{P(0 \notin U_n)^2}{\int_0^{\epsilon} P(t \notin U_n, 0 \notin U_n) dt}. $$
By Shepp [15, Formula (34)], we then have when $r < \varepsilon$ that

$$ 
\begin{aligned}
P_{\varepsilon,n,r} &\ge \frac{\varepsilon P(0 \notin U_n)^2}{2 \int_0^\varepsilon (1-2r-\min(t,2r))^n dt} \\
&\ge \frac{\varepsilon (1-2r)^{2n}}{2 \int_0^{2r} (1-2r-t)^n dt + \int_0^\varepsilon (1-4r)^n dt} \\
&= \frac{\varepsilon (1-2r)^{2n}}{2 - (n+1)^{-1}(1-4r)^n + (n+1)^{-1}(1-2r)^n + \varepsilon(1-4r)^n} \\
&\ge \frac{1}{2 \varepsilon^{-1}(n+1)^{-1}(1-2r)^{-n} + 1}.
\end{aligned}
$$

From (4), it follows that for any fixed $\varepsilon > 0$ and $m$, we have $P_{\varepsilon,n-m,r_n} \to \frac{1}{2}$ as $n \to \infty$.

We will now construct inductively two sequences $(\varepsilon_k)_{k \ge 1}$ and $(n_k)_{k \ge 1}$. The 1st sequence is positive and decays to 0. The 2nd will be a sequence of rapidly increasing integers. Along with these sequences, we will choose a nested sequence of compact intervals $I_k$ with $|I_k| = \varepsilon_k$.

Suppose that $\varepsilon_k$, $n_k$, and $I_k$ have been chosen for a particular value of $k$. We explain how $\varepsilon_{k+1}$, $n_{k+1}$, and $I_{k+1}$ are chosen.

Consider the $n_k$ 1st centres $\omega_1, \dots, \omega_{n_k}$, and the balls

$$ \mathcal{B}_{k,n} = \{ B(\omega_j, r_n) : j \le n_k \} $$

for some $n \gg n_k$. The total length of these balls is $n_k r_n$ and if we choose $n$ large enough this will be as small as we like. In particular, we can choose $n_{k+1} \gg n_k$ such that the balls in $\mathcal{B}_{k,n_{k+1}}$ cover less than half of $I_k$. Since there are $n_k$ balls they will cut $I_k$ in at most $n_k + 1$ pieces and always leave an interval $J_k \subset I_k$ with $|J_k| = \delta_k := \frac{\varepsilon_k}{2(n_k+1)}$ completely uncovered.

We now consider the balls $B(\omega_j, r_{n_{k+1}})$ for $j \le n_{k+1}$. The 1st $n_k$ balls do not intersect $J_k$, so $J_k$ can only be intersected by a ball $B(\omega_j, r_{n_{k+1}})$ when $j > n_k$. It follows that the probability that $J_k$ is not covered by the balls $B(\omega_j, r_{n_{k+1}})$, $j \le n_{k+1}$ is given by $P_{\delta_k,n_{k+1}-n_k,r_{n_{k+1}}}$.

$$ P_{\delta_k, n_{k+1}-n_k, r_{n_{k+1}}} \ge \frac{1}{3}. $$

The part of $J_k$ that is not covered is an open set (possibly empty), so every time $J_k$ is not coved, the uncovered part contains a compact interval of positive length. The probability that we have such a compact interval of length $\varepsilon$ approaches $P_{\delta_k,n_{k+1}-n_k,r_{n_{k+1}}}$ as $\varepsilon$ approaches 0. It follows that there is a number $\varepsilon_{k+1}$ such the probability that $J_k$
contains a compact interval of length $\varepsilon_{k+1}$, which is completely uncovered is at least $\frac{1}{4}$. Such an $\varepsilon_{k+1}$ is our choice of $\varepsilon_{k+1}$.

Now, it remains to choose $I_{k+1}$. If $J_k$ contains a compact interval of length $\varepsilon_{k+1}$ that does not intersect any of the balls $B(\omega_j, r_{n_{k+1}})$, $j \le n_{k+1}$, then we let $I_{k+1}$ be this compact interval. (The probability that this happens is at least $\frac{1}{4}$.) If this is not the case, then we just let $I_{k+1}$ be any subinterval of $J_k$ with $|I_{k+1}| = \varepsilon_{k+1}$. In this case, the interval $I_{k+1}$ intersects the balls $B(\omega_j, r_{n_{k+1}})$, $j \le n_{k+1}$.

The effect is that we have chosen a compact interval $I_{k+1} \subset J_k \subset I_k$ of length $|I_{k+1}| = \varepsilon_{k+1}$ and with probability at least $\frac{1}{4}$ this interval does not intersect any of the balls $B(\omega_j, r_{n_{k+1}})$, $j \le n_{k+1}$, that is, $I_{k+1} \cap E_{n_{k+1}} = \emptyset$, where we recall $E_{n_k} = \bigcup_{j=1}^{n_k} B(\omega_j, r_{n_k})$. Since this intersecting property by construction does not depend on the $n_k$ 1st balls, the events $\{I_k \cap E_{n_k} = \emptyset\}$ ($k \ge 1$) are independent and all have probability bigger than $\frac{1}{4}$. Thus, by Borel-Cantelli lemma, with probability 1, there are infinitely many $k$ for which $I_k \cap E_{n_k} = \emptyset$.

On the other hand, by induction, we have constructed a nested sequence of compact intervals $I_k$ with $|I_k| = \varepsilon_k > 0$. Hence, the intersection $\cap_k I_k$ contains exactly one point $p$.

Therefore, with probability 1, the point $p$ is not in all $E_{n_k}$ ($k \ge 1$). By the definition of $\mathcal{U}(\omega)$, we thus have $p \notin \mathcal{U}(\omega)$ almost surely. In particular, $\mathcal{U}(\omega) \ne \mathbb{T}$ almost surely.

# 6 Proof of Theorem 2 on Lebesgue Measure

## 6.1 Proof of the zero-one law

The i.i.d. sequence $\omega = (\omega_1, \omega_2, \dots)$ can be naturally modelled as an element in the probability space $\Omega := \mathbb{T}^N$ with the $\sigma$-algebra being the infinite product $\sigma$-algebra of the Borel $\sigma$-algebra on $\mathbb{T}$, and the probability $P$ being the infinite product of the Lebesgue measure on $\mathbb{T}$. Then, by defining $T$ as the left shift on $\Omega$, we know that $T$ is an ergodic transformation with respect to $P$.

Note that for any $\omega \in \Omega$ and any point $y \in \mathbb{T}$, we have $y \in \mathcal{U}(\omega)$ if and only if

$$ \forall N \gg 1, \exists n \le N, \text{ s.t. } \omega_n \in B(y, r_N), $$

or, equivalently, $\omega$ is in the following set:

$$ \bigcup_{p=1}^{\infty} \bigcap_{N=p}^{\infty} \{ \omega : \{\omega_1, \dots, \omega_N\} \cap B(y, r_N) \neq \emptyset \}. $$
For $y \in \mathbb{T}$ and $(r_n)_{n \ge 1}$, let

$$B_n(y) := B(y, r_n) \times \mathbb{T}^{N_{\ge 2}}.$$

Then, $(B_n(y))_{n \ge 1}$ is a sequence of shrinking targets in $\Omega$ such that $P(B_n(y)) \to 0$ as $n \to \infty$. Further, $y \in \mathcal{U}(\omega)$ if any only if

$$\forall N \gg 1, \exists n \le N, \text{ s.t. } T^{n-1}\omega \in B_N(y),$$

which is equivalent to

$$\omega \in \bigcup_{p=1}^{\infty} \bigcap_{N=p}^{\infty} \bigcup_{n=0}^{N-1} T^{-k} B_N(y) =: \mathcal{E}_{ah}(y).$$

Here, the subscript “ah” in $\mathcal{E}_{ah}(y)$ stands for “always hitting” (see [11, Definition 1]). By [11, Lemma 1], for fixed $y$, the set $\mathcal{E}_{ah}(y)$ has probability 1 or 0. Because of rotational invariance, $P(\mathcal{E}_{ah}(y))$ does not depend on $y$ but only on the sequence $(r_n)_{n \ge 1}$. Hence, by Fubini’s theorem, we have either $P(\lambda(\mathcal{U}(\omega)) = 1) = 1$ or $P(\lambda(\mathcal{U}(\omega)) = 0) = 1$, which proves the 1st part of Theorem 2.

## 6.2 The condition on $(r_n)_{n \ge 1}$

That the condition (2) in Theorem 2 is necessary and sufficient for $\lambda(\mathcal{U}(\omega)) = 1$ to hold almost surely follows from Theorem 4.3.1 of the book of Galambos [6]. We present here a simplified statement.

**Theorem 7.** (Galambos [6, Theorem 4.3.1]) Let $X_1, X_2, \dots$ be a sequence of independent, identically distributed random variables with a nondegenerate, continuous distribution function $F$. Let $Z_n = \max\{X_1, X_2, \dots, X_n\}$, and assume that sequences $(u_n)_{n \ge 1}$ and $(n(1 - F(u_n)))_{n \ge 1}$ are both increasing. Then, the probability

$$P(Z_n \le u_n \text{ for infinitely many } n) = 0, \quad (5)$$

if and only if

$$\sum_{j=1}^{\infty} (1 - F(u_j)) = \infty \quad \text{and} \quad \sum_{j=1}^{\infty} (1 - F(u_j)) \exp(-j(1 - F(u_j))) < \infty.$$

We will now connect the quantities in our special case to the notation of Galambos.

Fix a point $y \in \mathbb{T}$. Let $X_n = |\omega_n - y|^{-1}$ and $u_n = r_n^{-1}$. The sequence of random variables $(X_n)_{n \ge 1}$ is i.i.d. and $y \in B(\omega_k, r_n)$ if and only if $X_k > u_n$.
Notice that $Z_n > u_n$ if and only if there is a $k \le n$ such that $y \in B(\omega_k, r_n)$. Thus, $\omega \in \mathcal{E}_{ah}(y)$ if and only if $Z_n > u_n$ holds eventually (i.e., for all sufficiently large $n$). Hence, $\omega \in \mathcal{E}_{ah}(y)$ if and only if $Z_n \le u_n$ holds for at most finitely many $n$.

We have $F(x) = P(X_n < x) = P(|\omega_n - y| > x^{-1}) = 1 - 2x^{-1}$. By the above theorem of Galambos, we have (5) holds if and only if

$$ \sum_{n=1}^{\infty} P(X_n > u_n) = \infty \quad \text{and} \quad \sum_{n=1}^{\infty} (1 - F(u_n)) \exp(-n(1 - F(u_n))) < \infty. $$

This translates immediately to condition (2) in Theorem 2. Therefore, $P(\mathcal{E}_{ah}(y)) = 1$ if and only if (2) holds. Since this holds for all $y$, it follows by Fubini's theorem that $P(\lambda(U(\omega)) = 1) = 1$ if and only if (2) holds.

Finally, we note that the zero-one law of Theorem 2 alternatively can also be deduced from [6, Lemma 4.3.1] instead of referring to [11, Lemma 1].

## 7 Proof of Theorem 3

The probability that $B_{n+1,n+1}$ intersects no ball of $B_{k,n}$ for $k \le n$ is at least

$$ 1 - 2n(r_n + r_{n+1}). $$

Thus, the probability that $B_{n+1,n+1}$ intersects at least one of the balls $B_{k,n}$ for some $k \le n$ is at most $2n(r_n + r_{n+1})$. Hence, if $\sum_{n=1}^{\infty} nr_n < \infty$, then by the 1st Borel-Cantelli lemma, almost surely, there is an $m$ such that for all $n \ge m$ the ball $B_{n+1,n+1}$ has empty intersection with all balls $B_{k,n}$ with $k \le n$. Therefore, for all $n \ge m$,

$$ \begin{aligned} E_n \cap E_{n+1} &= \bigcup_{k=1}^{n} B_{k,n} \cap \left( \bigcup_{k=1}^{n} B_{k,n+1} \cup B_{n+1,n+1} \right) \\ &= \left( \bigcup_{k=1}^{n} B_{k,n} \cap \bigcup_{k=1}^{n} B_{k,n+1} \right) \cup \left( \bigcup_{k=1}^{n} B_{k,n} \cap B_{n+1,n+1} \right) \\ &= \bigcup_{k=1}^{n} B_{k,n+1}. \end{aligned} $$

Further, we have

$$ \bigcap_{n=p}^{\infty} E_n = \{\omega_1, \dots, \omega_p\}, \quad \forall p \ge m, $$
which implies

$$ \mathcal{U}(\omega) = \bigcup_{p=1}^{\infty} \bigcap_{n=p}^{\infty} E_n = \{ \omega_k : k \in \mathbb{N} \}. $$

# 8 Proofs Related to Hausdorff Dimension

In this section, we prove Theorems 4 and 5 on the estimations of the Hausdorff dimension of the set $\mathcal{U}(\omega)$.

## 8.1 Proofs of upper bounds on Hausdorff dimension

Before we give the proof of the upper bound of the Hausdorff dimension, which is found in Theorem 4, we give a theorem with a somewhat weaker upper bound. We include the proof of this theorem since it follows the same lines of thought as the more difficult proof of Theorem 4 and might make the proof of Theorem 4 easier to read.

**Theorem 8.** If $r_n = \frac{c}{n}$ and $0 < c < \frac{1}{2}$, then almost surely

$$ \dim_{\mathbb{H}} \mathcal{U}(\omega) \le \inf_{\theta > 1} \frac{\log(1 + 2c^{\theta^2 - 1})}{\log \theta}. $$

**Proof.** Put $n_j = \theta^j$, and let $l > 0$. (Normally, we should define $n_j$ as the integer part of $\theta^j$. However, for simplicity, we write $n_j = \theta^j$ here and in what follows. The interested reader can easily find the more precise arguments without problem.) Consider the set

$$ G_{l,i} = \bigcap_{j=l}^{i} \bigcup_{k=1}^{n_j} B(\omega_k, r_{n_j}). $$

We are going to construct inductively a cover of $G_{l,i}$ by $N_i$ balls $B(\omega_k, r_{n_i})$, where $k \in I_i$ and $I_i \subset \{1, 2, \dots, n_i\}$.

For $i = l$, we let $N_l = n_l$ and $I_l = \{1, 2, \dots, n_l\}$. Suppose that $I_i$ has been defined. We define $I_{i+1}$ to consist of those $k \le n_{i+1}$ such that $B(\omega_k, r_{n_{i+1}})$ intersects the set

$$ \hat{G}_i = \bigcup_{j \in I_i} B(\omega_j, r_{n_i}). $$

Since $B(\omega_k, r_{n_{i+1}})$ is contained in $B(\omega_k, r_{n_j})$, for all $j \le i$, we have

$$ N_{i+1} = N_i + M_{i+1}, $$

where $M_{i+1}$ is the number of $n_i < k \le n_{i+1}$ such that the ball $B(\omega_k, r_{n_{i+1}})$ has non-empty intersection with $\hat{G}_i$.
Let $(\hat{G}_i)_{(r)}$ denote the $r$-neighbourhood of $\hat{G}_i$. We then have

$$M_{i+1} = \sum_{k=n_i+1}^{n_{i+1}} \mathbb{1}_{(\hat{G}_i)_{(r_{n_i+1})}}(\omega_k). \qquad (6)$$

Let $\varepsilon > 0$. The set $\hat{G}_i$ is a union of $N_i$ balls of radius $r_{n_i}$. Hence, the Lebesgue measure of $(\hat{G}_i)_{(r_{n_i+1})}$ is at most $2(r_{n_i} + r_{n_i+1})N_i$. It follows that

$$E(M_{i+1}|\mathcal{S}_i) \le 2(r_{n_i} + r_{n_i+1})N_i(n_{i+1} - n_i) = 2c \frac{\theta^2 - 1}{\theta} N_i,$$

where $\mathcal{S}_i$ denotes the $\sigma$-algebra generated by $\omega_1, \omega_2, \dots, \omega_{n_i}$. Hence,

$$EM_{i+1} = E(E(M_{i+1}|\mathcal{S}_i)) \le 2c \frac{\theta^2 - 1}{\theta} EN_i.$$

Since $N_{i+1} = N_i + M_{i+1}$, it follows that

$$EN_{i+1} \le (1 + 2c \frac{\theta^2 - 1}{\theta}) EN_i.$$

By induction,

$$EN_{i+1} \le (1 + 2c \frac{\theta^2 - 1}{\theta})^{i+1-l} EN_l = (1 + 2c \frac{\theta^2 - 1}{\theta})^{i+1-l} n_l.$$

By Markov's inequality,

$$P\{N_{i+1} \ge u_i EN_{i+1}\} \le \frac{1}{u_i}.$$

Letting $u_i = (1 + \varepsilon)^i$ for some $\varepsilon > 0$, we therefore have

$$P\{N_{i+1} \ge (1 + \varepsilon)^i (1 + 2c \frac{\theta^2 - 1}{\theta})^{i+1-l} n_l\} \le P\{N_{i+1} \ge u_i EN_{i+1}\} \\ \le (1 + \varepsilon)^{-i},$$

which is summable over $i$. Hence, almost surely, there is an $i_0$ such that for all $i \ge i_0$,

$$N_{i+1} < (1 + \varepsilon)^i (1 + 2c \frac{\theta^2 - 1}{\theta})^{i+1-l} n_l \\ = K_l(1 + \varepsilon)^{i+1} (1 + 2c \frac{\theta^2 - 1}{\theta})^{i+1},$$
where

$$K_l := (1 + \varepsilon)^{-1} \left(1 + 2c \frac{\theta^2 - 1}{\theta}\right)^{-l} n_l$$

is a constant depending on $l$. We assume from now on that such an $i_0$ exists.

With $i > i_0$, we may cover the set

$$G_{n_l} = \bigcap_{j=n_l}^{\infty} \bigcup_{k=1}^{n_j} B(\omega_k, r_{n_j})$$

by $N_i$ balls of radius $r_{n_i}$. Hence,

$$\dim_H G_{n_l} \le \frac{\log\left((1 + \varepsilon)(1 + 2c \frac{\theta^2 - 1}{\theta})\right)}{\log \theta}.$$

Since $\mathcal{U}(\omega)$ is contained in the union of the sets $G_{n_l}$, we have

$$\dim_H \mathcal{U}(\omega) \le \frac{\log\left((1 + \varepsilon)(1 + 2c \frac{\theta^2 - 1}{\theta})\right)}{\log \theta},$$

and since $\varepsilon$ can be taken as small as we please, the theorem is proved. ■

We now give the proof of Theorem 4, which contains a more careful but similar analysis as in the proof of Theorem 8.

**Proof of Theorem 4.** The proof is similar to that of Theorem 8. We let $n_j = \theta^j$ and $l > 0$. As before, we construct inductively a cover of

$$G_{l,i} = \bigcap_{j=l}^{i} \bigcup_{k=1}^{n_j} B(\omega_k, r_{n_j}).$$

The cover will consist of $N_i + Q_i$ balls $B(\omega_k, r_{n_i})$. We let $I_i, J_i \subset \{1, 2, \dots, n_i\}$ be such that $I_i \cap J_i = \emptyset$, there are $N_i$ balls $B(\omega_k, r_{n_i})$ with $k \in I_i$ and there are $Q_i$ balls $B(\omega_k, r_{n_i})$ with $k \in J_i$. The construction of $I_i$ and $J_i$ is described below.

We let $I_l = \{1, 2, \dots, n_l\}$ and $J_l = \emptyset$. Hence, $N_l = n_l$ and $Q_l = 0$. The set $G_{l,l}$ is covered by the $N_l = n_l$ balls $B(\omega_k, r_{n_l})$, where $k \in I_l$.
Suppose that the cover of $G_{l,i}$ is defined for some $i$, that is,

$$G_{l,i} \subset \bigcup_{k \in I_i \cup J_i} B(\omega_k, r_{n_i}).$$

The balls counted by $Q_i$ are balls $B(\omega_k, r_{n_i})$ such that $B(\omega_k, r_{n_{i+1}})$ can be discarded in the cover of $G_{l,i+1}$. The $N_i$ balls are balls such that $B(\omega_k, r_{n_{i+1}})$ is not discarded in the cover of $G_{l,i+1}$ (regardless of whether they can be discarded or not). What determines if $k \in I_{i+1}$ or $k \in J_{i+1}$ is described below.

Consider first a $k \in \{1, 2, \dots, n_i\}$. If $k \in I_i$, then we let $k \in I_{i+1}$. Otherwise, $k$ is not included in $I_i$ or $J_i$. This means that all $k \in J_i$ are discarded for the next step.

We now consider a $k \in \{n_i + 1, n_i + 2, \dots, n_{i+1}\}$. If $B(\omega_k, r_{n_{i+1}})$ intersects the set

$$H_i = \bigcup_{h \in I_i \cup J_i} B(\omega_h, r_{n_i}),$$

then we include $k$ in either $I_{i+1}$ or $J_{i+1}$. If $B(\omega_k, r_{n_{i+1}}) \cap H_i = \emptyset$, then $k$ is not included in any of $I_{i+1}$ or $J_{i+1}$.

Suppose that $B(\omega_k, r_{n_{i+1}}) \cap H_i \neq \emptyset$. Then, there exists an $h \in I_i \cup J_i$ such that $B(\omega_k, r_{n_{i+1}}) \cap B(\omega_h, r_{n_i}) \neq \emptyset$. Hence, $|\omega_k - \omega_h| < r_{n_i} + r_{n_{i+1}}$.

Note that for any $h \in I_i \cup J_i$, if $|\omega_k - \omega_h| \ge r_{n_i} + r_{n_{i+2}}$, then $B(\omega_k, r_{n_{i+2}}) \cap B(\omega_h, r_{n_i}) = \emptyset$. Thus, if $|\omega_k - \omega_h| \ge r_{n_i} + r_{n_{i+2}}$ holds for all $h \in I_i \cup J_i$, then $B(\omega_k, r_{n_{i+2}})$ will have empty intersection with $H_i$ and it is therefore not necessary to include $k$ in any of $I_{i+2}$ or $J_{i+2}$. We therefore put $k$ in $J_{i+1}$ in this case.

Finally, if $k$ satisfies $|\omega_k - \omega_h| < r_{n_i} + r_{n_{i+2}}$ for some $h \in I_i \cup J_i$, then we include $k$ in $I_{i+1}$. In this way, we obtain

$$H_{i+1} = \bigcup_{k \in I_i \cup J_i} B(\omega_k, r_{n_i}) \supset G_{l,i+1}$$

and by induction $H_i \supset G_{l,i}$ for all $i$.

As before, we let $\mathcal{S}_i$ denote the $\sigma$-algebra generated by $\omega_1, \omega_2, \dots, \omega_{n_i}$. We get

$$\begin{cases} \mathrm{E}(N_{i+1}|\mathcal{S}_i) \le N_i + 2(r_{n_i} + r_{n_{i+2}})(n_{i+1} - n_i)(N_i + Q_i), \\ \mathrm{E}(Q_{i+1}|\mathcal{S}_i) \le 2(r_{n_{i+1}} - r_{n_{i+2}})(n_{i+1} - n_i)(N_i + Q_i). \end{cases}$$

Hence,

$$\begin{cases} \mathrm{E}N_{i+1} \le \mathrm{E}N_i + 2(r_{n_i} + r_{n_{i+2}})(n_{i+1} - n_i)(\mathrm{E}N_i + \mathrm{E}Q_i), \\ \mathrm{E}Q_{i+1} \le 2(r_{n_{i+1}} - r_{n_{i+2}})(n_{i+1} - n_i)(\mathrm{E}N_i + \mathrm{E}Q_i). \end{cases}$$
Letting

$$ 
\begin{aligned}
\Theta &= 2c(\theta - 1)(1 + \theta^{-2}), \\
\Delta &= 2c(\theta - 1)(\theta^{-1} - \theta^{-2}),
\end{aligned}
$$

we have

$$ \begin{bmatrix} EN_{i+1} \\ EQ_{i+1} \end{bmatrix} \le \begin{bmatrix} 1 + \Theta & \Theta \\ \Delta & \Delta \end{bmatrix} \begin{bmatrix} EN_i \\ EQ_i \end{bmatrix}. $$

The largest eigenvalue of the above square matrix is

$$ \Lambda = \frac{1 + \Theta + \Delta}{2} + \sqrt{\left(\frac{1 + \Theta + \Delta}{2}\right)^2 - \Delta}, $$

and we have $EN_i + EQ_i \le C_0\Lambda^i$ for some constant $C_0$. A similar argument as that in the proof of Theorem 8 gives that for all $\varepsilon > 0$, almost surely, there exists a constant $C$ such that

$$ N_i + Q_i \le C(1 + \varepsilon)^i \Lambda^i. $$

The set

$$ G_{n_l} = \bigcap_{j=n_l}^{\infty} \bigcup_{k=1}^{n_j} B(\omega_k, r_{n_j}) $$

can be covered by the $N_i + Q_i$ balls of radius $r_{n_i}$. Hence,

$$ \dim_{\mathbb{H}} G_{n_l} \le \frac{\log(1 + \varepsilon) + \log \Lambda}{\log \theta} $$

and since $\varepsilon$ can be taken as close to 0 as we desire, we obtain $\dim_{\mathbb{H}} G_{n,l} \le \frac{\log \Lambda}{\log \theta}$. Which $\theta$ is the optimal choice depends on $c$, and there is no simple expression for the optimal $\theta$ in terms of $c$. ■

## 8.2 Preparations to the proof of Theorem 5

We begin with the following theorem, which is useful for the lower bound estimating of Hausdorff dimension.

Suppose $\eta$ is a Borel measure, and let $0 < s < 1$. The $s$-dimensional Riesz potential of $\eta$ is a function $R_s\eta: \mathbb{T} \to \mathbb{R} \cup \{\infty\}$ defined by

$$ R_s\eta(x) = \int |x - y|^{-s} d\eta(y). $$
**Theorem 9.** Let $\eta$ be a finite Borel measure, and suppose $0 < s < 1$. Then, the Borel measure $\rho = (R_s\eta)^{-1}\eta$, defined by

$$\rho(A) = \int_A (R_s\eta)^{-1} d\eta,$$

satisfies $\rho(U) \le |U|^s$ for any Borel set $U$. ($|U|$ denotes the diameter of $U$.)

**Proof.** The proof follows the proof of Lemma 1.1 (or Lemma 5.1) in Persson [14].

It is clear that $\rho$ is a Borel measure.

We may assume that $\eta(U) > 0$, since otherwise, there is nothing to prove. It now follows that

$$\begin{aligned}
\rho(U) &= \int_U \left( \int |x-y|^{-s} d\eta(y) \right)^{-1} d\eta(x) \\
&\le \int_U \left( \int_U |x-y|^{-s} d\eta(y) \right)^{-1} d\eta(x) \\
&= \int_U \left( \int_U |x-y|^{-s} \frac{d\eta(y)}{\eta(U)} \right)^{-1} \frac{d\eta(x)}{\eta(U)} \\
&\le \int_U \int_U |x-y|^s \frac{d\eta(y)}{\eta(U)} \frac{d\eta(x)}{\eta(U)} \le |U|^s,
\end{aligned}$$

where we have made use of Jensen's inequality. ■

Throughout the proof of Theorem 5, we will assume that the balls $B_{k,n}$ are closed. This makes certain arguments in the proof a bit simpler, and it does not change the Hausdorff dimension of $\mathcal{U}(\omega)$.

We will consider a subset of $\mathcal{U}(\omega)$. Let $n_j$ be a strictly increasing sequence of integers. Put

$$F_j = \bigcup_{k=n_{j-1}+1}^{n_j} B_{k,n_{j+1}}.$$

Then, $F_j$ is compact and we have

$$F := \liminf F_j \subset \mathcal{U}(\omega).$$

To see this, note that for every $n$ with $n_j < n \le n_{j+1}$, we have $F_j \subset E_n$, so that

$$\bigcap_{j=j_0}^{\infty} F_j \subset \bigcap_{n=m}^{\infty} E_n$$

holds when $n_{j_0} < m$.
We define measures $\mu_{l,m}$ on $\mathbb{T}$ by

$$ \frac{d\mu_{l,m}}{dx} = \prod_{j=l}^{m} 1_{F_j'} $$

where $1_{F_j'}$ denotes the indicator function of $F_j$. Hence, $\mu_{l,m}$ has support in

$$ \bigcap_{j=l}^{m} F_j' $$

In fact, $\mu_{l,m}$ is the restriction of Lebesgue measure to $\bigcap_{j=l}^{m} F_j'$.

Suppose $\{U_i\}$ is an open cover of $F$. Then, $\{U_i\}$ is an open cover of

$$ \bigcap_{j=l}^{\infty} F_j $$

for any $l$. Since the sets $F_j$ are compact, there exists, for each $l$, an $m$, such that $\{U_i\}$ covers

$$ \bigcap_{j=l}^{m} F_j' $$

We shall therefore investigate the typical behaviour of $\mu_{l,m}$, aiming to apply Theorem 9. We start with the following three lemmata.

**Lemma 2.** Let $x, y \in \mathbb{T}$. Then,

$$ E[1_{B_{k,n}}(x)1_{B_{k,n}}(y)] = \int 1_{B_{k,n}}(x)1_{B_{k,n}}(y) dP \le 2r_n 1_{B(0,2r_n)}(|x-y|). $$

**Proof.** We have

$$ \int 1_{B_{k,n}}(x)1_{B_{k,n}}(y) dP = \begin{cases} 0 & \text{if } |x - y| \ge 2r_n \\ 2r_n - |x - y| & \text{if } |x - y| < 2r_n \end{cases}, $$

which proves the lemma.

**Lemma 3.** Let $x, y \in \mathbb{T}$. Then,

$$ E[(1 - 1_{B_{k,n}}(x))(1 - 1_{B_{k,n}}(y))] \le 1 - 4r_n + 2r_n 1_{B(0,2r_n)}(|x - y|). $$
**Proof.** We have

$$ 
\begin{aligned}
& E[(1 - \mathbb{1}_{B_{k,n}}(x))(1 - \mathbb{1}_{B_{k,n}}(y))] \\
&=1 - E[\mathbb{1}_{B_{k,n}}(x)] - E[\mathbb{1}_{B_{k,n}}(y)] + E[\mathbb{1}_{B_{k,n}}(x)\mathbb{1}_{B_{k,n}}(y)] \\
&=1 - 4r_n + E[\mathbb{1}_{B_{k,n}}(x)\mathbb{1}_{B_{k,n}}(y)],
\end{aligned}
$$

and the estimate follows from Lemma 2.

**Lemma 4.** Let

$$ \Psi_{l,m}(t) = \prod_{j=l}^{m} \left( 1 + \frac{(1 - 2r_{n_{j+1}})^{n_j - n_{j-1}}}{1 - (1 - 2r_{n_{j+1}})^{n_j - n_{j-1}}} \mathbb{1}_{B(0, r_{n_{j+1}})}(t) \right). $$

If $n_j = \theta^j$ and $r_n = \frac{c}{n}$, then $\Psi_{l,m}(t) \le 1 + C_l|t|^{-s(c,\theta)}$, where

$$ C_l = c^{s(c,\theta)} \left(1 - \exp\left(-2c \frac{\theta - 1}{\theta^2}\right)\right)^l $$

and

$$ s(c, \theta) = \frac{-\log(1 - \exp(-2c \frac{\theta-1}{\theta^2}))}{\log \theta}. $$

**Proof.** Take $t > 0$. If $t > r_{n_{l+1}}$, then $\Psi_{l,m}(t) = 1$. Otherwise, there is a $j_0 > l$ such that $r_{n_{j_0+1}} \le t < r_{n_{j_0}}$. Then,

$$ 
\begin{aligned}
\Psi_{l,m}(t) &= \prod_{j=l}^{j_0} \left( 1 + \frac{(1 - 2r_{n_{j+1}})^{n_j - n_{j-1}}}{1 - (1 - 2r_{n_{j+1}})^{n_j - n_{j-1}}} \right) \\
&= \prod_{j=l}^{j_0} \left( \frac{1}{1 - (1 - 2r_{n_{j+1}})^{n_j - n_{j-1}}} \right).
\end{aligned}
$$

With $n_j = \theta^j$ and $r_n = \frac{c}{n}$, we get

$$ \Psi_{l,m}(t) \le \prod_{j=l}^{j_0} \left( \frac{1}{1 - (1 - 2c\theta^{-(j+1)})^{\theta^{j+1}(\theta-1)\theta^{-2}}} \right). $$
Since $x \mapsto (1 - 1/x)^x$ is increasing, we get

$$ \Psi_{l,m}(t) \le \prod_{j=l}^{j_0} \left( \frac{1}{1 - \exp(-2c^{\frac{\theta-1}{\theta^2}})} \right) \le C_l t^{-s(c,\theta)}, $$

where $C_l = c^{s(c,\theta)} (1 - \exp(-2c^{\frac{\theta-1}{\theta^2}}))^l$ and

$$ s(c, \theta) = \frac{-\log(1 - \exp(-2c^{\frac{\theta-1}{\theta^2}}))}{\log \theta}. $$

Finally, we have $\Psi_{l,m}(t) \le 1 + C_l |t|^{-s(c,\theta)}$, regardless of whether $t > r_{n_{l+1}}$ or not. ■

We let

$$ K_{l,m} = \prod_{j=l}^{m} (1 - (1 - 2r_{n_{j+1}})^{n_j - n_{j-1}}). $$

These numbers will appear several times in our computations.

**Proposition 1.** We have

$$ E(\mu_{l,m}(\mathbb{T})) = K_{l,m} \quad \text{and} \quad E(\mu_{l,m}(\mathbb{T})^2) \le K_{l,m}^2 \int_{\mathbb{T}} \int_{\mathbb{T}} \Psi_{l,m}(|x - y|) \, dx dy. $$

**Proof.** Since the intervals $[n_{j-1} + 1, n_j]$, which appear as summation intervals in the union

$$ F_j = \bigcup_{k=n_{j-1}+1}^{n_j} B_{k,n_{j+1}}, $$

are disjoint, the sets $F_j$ are pairwise independent, and we have

$$ E(\mu_{l,m}(\mathbb{T})) = \prod_{j=l}^{m} \int_{\mathbb{T}} \int_{\mathbb{T}} \mathbb{1}_{F_j}(x) \, dx \, dP = \prod_{j=l}^{m} \int_{\mathbb{T}} \int_{\mathbb{T}} \mathbb{1}_{F_j}(x) \, dP \, dx. $$
Denote by $\mathcal{C}F$ the complement of a subset $F$. We compute $\int 1_{\mathcal{C}F_j} dP$. By independence, we have

$$ 
\begin{aligned}
\int 1_{\mathcal{C}F_j} dP &= \int \prod_{k=n_{j-1}+1}^{n_j} (1 - 1_{B_{k,n_{j+1}}}) dP \\
&= \prod_{k=n_{j-1}+1}^{n_j} \int (1 - 1_{B_{k,n_{j+1}}}) dP \\
&= \prod_{k=n_{j-1}+1}^{n_j} (1 - 2r_{n_{j+1}}) = (1 - 2r_{n_{j+1}})^{n_j - n_{j-1}}.
\end{aligned}
$$

We then have

$$ \int 1_{F_j} dP = 1 - (1 - 2r_{n_{j+1}})^{n_j - n_{j-1}} $$

and

$$ E(\mu_{l,m}(\mathbb{T})) = \prod_{j=l}^{m} (1 - (1 - 2r_{n_{j+1}})^{n_j - n_{j-1}}) = K_{l,m}. $$

We now estimate $E(\mu_{l,m}(\mathbb{T})^2)$. By Lemma 3, we have

$$ 
\begin{aligned}
\int 1_{\mathcal{C}F_j}(x) 1_{\mathcal{C}F_j}(y) dP &= \prod_{k=n_{j-1}+1}^{n_j} \int (1 - 1_{B_{k,n_{j+1}}}(x))(1 - 1_{B_{k,n_{j+1}}}(y)) dP \\
&\le (1 - 4r_{n_{j+1}} + 2r_{n_{j+1}} 1_{B(0,2r_{n_{j+1}})}(|x-y|))^{n_j - n_{j-1}} \\
&=: \Phi_j(|x-y|).
\end{aligned}
$$

Using this estimate, we have

$$ 
\begin{aligned}
E(\mu_{l,m}(\mathbb{T})^2) &= \int \left( \int_{\mathbb{T}} \int_{\mathbb{T}} \prod_{j=l}^{m} 1_{F_j}(x) 1_{F_j}(y) \, dxdy \right) dP \\
&= \int_{\mathbb{T}} \int_{\mathbb{T}} \prod_{j=l}^{m} \int (1 - 1_{\mathcal{C}F_j}(x))(1 - 1_{\mathcal{C}F_j}(y)) \, dP \, dxdy \\
&= \int_{\mathbb{T}} \int_{\mathbb{T}} \prod_{j=l}^{m} \int (1 - 1_{\mathcal{C}F_j}(x) - 1_{\mathcal{C}F_j}(y) + 1_{\mathcal{C}F_j}(x) 1_{\mathcal{C}F_j}(y)) \, dP \, dxdy \\
&\le \int_{\mathbb{T}} \int_{\mathbb{T}} \prod_{j=l}^{m} (1 - 2(1 - 2r_{n_{j+1}})^{n_j - n_{j-1}} + \Phi_j(|x-y|)) \, dxdy.
\end{aligned}
$$
We consider the factor $1 - 2(1 - 2r_{n_{j+1}})^{n_j - n_{j-1}} + \Phi_j(|x - y|)$. If

$$ \mathbb{1}_{B(0, 2r_{n_{j+1}})}(|x - y|) = 0, $$

then

$$ \begin{aligned} & 1 - 2(1 - 2r_{n_{j+1}})^{n_j - n_{j-1}} + \Phi_j(|x - y|) \\ &= 1 - 2(1 - 2r_{n_{j+1}})^{n_j - n_{j-1}} + (1 - 4r_{n_{j+1}})^{n_j - n_{j-1}} \\ &\le 1 - 2(1 - 2r_{n_{j+1}})^{n_j - n_{j-1}} + (1 - 2r_{n_{j+1}})^{2(n_j - n_{j-1})} \\ &= (1 - (1 - 2r_{n_{j+1}})^{n_j - n_{j-1}})^2. \end{aligned} $$

Similarly, if $\mathbb{1}_{B(0, 2r_{n_{j+1}})}(|x - y|) = 1$, then

$$ \begin{aligned} & 1 - 2(1 - 2r_{n_{j+1}})^{n_j - n_{j-1}} + \Phi_j(|x - y|) \\ &= 1 - 2(1 - 2r_{n_{j+1}})^{n_j - n_{j-1}} + (1 - 2r_{n_{j+1}})^{n_j - n_{j-1}} \\ &= 1 - (1 - 2r_{n_{j+1}})^{n_j - n_{j-1}}. \end{aligned} $$

Hence, we have

$$ \frac{1 - 2(1 - 2r_{n_{j+1}})^{n_j - n_{j-1}} + \Phi_j(|x - y|)}{(1 - (1 - 2r_{n_{j+1}})^{n_j - n_{j-1}})^2} = \left( 1 + \frac{(1 - 2r_{n_{j+1}})^{n_j - n_{j-1}}}{1 - (1 - 2r_{n_{j+1}})^{n_j - n_{j-1}}} \mathbb{1}_{B(0, 2r_{n_{j+1}})}(|x - y|) \right). $$

With

$$ \Psi_{l,m}(|x - y|) = \prod_{j=l}^{m} \left( 1 + \frac{(1 - 2r_{n_{j+1}})^{n_j - n_{j-1}}}{1 - (1 - 2r_{n_{j+1}})^{n_j - n_{j-1}}} \mathbb{1}_{B(0, 2r_{n_{j+1}})}(|x - y|) \right), $$

we therefore have

$$ E(\mu_{l,m}(\mathbb{T})^2) \le K_{l,m}^2 \int_{\mathbb{T}} \int_{\mathbb{T}} \Psi_{l,m}(|x - y|) \, dxdy. $$

**Proposition 2.** Let $\varepsilon > 0, 0 < \delta < 1, \theta > 1$ and $n_j = \theta^j$. If $r_n = \frac{c}{n}$ with

$$ c > -\frac{1}{2} \frac{\theta^2}{\theta - 1} \log\left(1 - \frac{1}{\theta}\right), $$
then we have

$$ \delta E\mu_{l,m}(\mathbb{T}) < \mu_{l,m}(\mathbb{T}) < (2 - \delta)E\mu_{l,m}(\mathbb{T}) $$

with probability at least $1 - \epsilon$ if $l$ is large enough.

**Proof.** The assumption on $c$ implies that $s(c, \theta) < 1$.

Using Lemma 4 and Markov's inequality, we obtain

$$ \begin{aligned} P(|\mu_{l,m}(\mathbb{T}) - E\mu_{l,m}(\mathbb{T})| \ge a) &\le \frac{E(\mu_{l,m}(\mathbb{T}) - E\mu_{l,m}(\mathbb{T}))^2}{a^2} \\ &= \frac{E(\mu_{l,m}(\mathbb{T})^2) - (E\mu_{l,m}(\mathbb{T}))^2}{a^2} \\ &\le D_l \frac{(E\mu_{l,m}(\mathbb{T}))^2}{a^2}, \end{aligned} $$

where

$$ D_l := C_l \iint_{\mathbb{T}} |x - y|^{-s(c,\theta)} dxdy < \infty $$

since $s(c, \theta) < 1$.

With $a = (1 - \delta)E\mu_{l,m}(\mathbb{T})$, we get

$$ P(\delta < \frac{\mu_{l,m}(\mathbb{T})}{E\mu_{l,m}(\mathbb{T})} < (2 - \delta)) \ge 1 - \frac{D_l}{(1 - \delta)^2}. $$

By Lemma 4, we see that $C_l \to 0$ and hence $D_l \to 0$ as $l \to \infty$. This finishes the proof. ■

For $0 < s < 1$, we define the $s$-dimensional Riesz energy of a measure $\mu$ by

$$ I_s(\mu) = \iint |x - y|^{-s} d\mu(x)d\mu(y). $$

We let

$$ J_s = \int_{\mathbb{T}} \int_{\mathbb{T}} |x - y|^{-s} dxdy = 2 \int_0^{\frac{1}{2}} t^{-s} dt = \frac{2^{2-s}}{1-s}. $$

**Proposition 3.** Let $\theta > 1$ and $n_j = \theta^j$. If $r_n = \frac{c}{n}$ with

$$ c > -\frac{1}{2} \frac{\theta^2}{\theta - 1} \log\left(1 - \frac{1}{\theta}\right), $$
then for any $0 < s < 1$

$$E I_s(\mu_{l,m}) \le K_{l,m}^2 C_l J_{s+s(c,\theta)} < \infty.$$

**Proof.** Following the same steps as in the estimation of $E(\mu_{l,m}(\mathbb{T})^2)$ in the proof of Proposition 1, we obtain

$$ \begin{aligned} E(I_s(\mu_{l,m})) &\le \int_{\mathbb{T}} \int_{\mathbb{T}} |x-y|^{-s} \Psi_{l,m}(|x-y|) \, dxdy \\ &\le K_{l,m}^2 C_l \int_{\mathbb{T}} \int_{\mathbb{T}} |x-y|^{-s-s(c,\theta)} \, dxdy = K_{l,m}^2 C_l J_{s+s(c,\theta)}. \end{aligned} $$

The assumption on $c$ implies that $J_{s+s(c,\theta)}$ is finite.

<figure><img src="image_4.png" /></figure>

## 8.3 Proof of Theorem 5

Assume that $\theta$ satisfies

$$c > -\frac{1}{2} \frac{\theta^2}{\theta - 1} \log\left(1 - \frac{1}{\theta}\right). \quad (7)$$

This condition is equivalent to

$$1 - \frac{-\log(1 - \exp(-2c^{\frac{\theta-1}{\theta^2}}))}{\log \theta} > 0,$$

Since we want to bound the dimension from below by the above left-hand side, we may assume (7) without loss.

From (7), it follows that $s(c, \theta) < 1$ and we may choose an $s \in (0, 1 - s(c, \theta))$. Let $0 < \varepsilon < \frac{1}{2}$ and $\delta > 0$. We let $n_j = \theta^j$.

Our choice of $s$ implies that $J_{s+s(c,\theta)}$ is finite since $s + s(c, \theta) < 1$. Using Markov's inequality and Proposition 3, we have for any $a > 0$,

$$P(I_s(\mu_{l,m}) \ge a(E\mu_{l,m})^2) \le \frac{EI_s(\mu_{l,m})}{a(E\mu_{l,m})^2} \le \frac{C_l J_{s+s(c,\theta)}}{a}.$$

Take $a > 0$ such that $\frac{C_l J_{s+s(c,\theta)}}{a} < \varepsilon$. Then,

$$P(I_s(\mu_{l,m}) < a(E\mu_{l,m})^2) \ge 1 - \varepsilon.$$
Taking a large $l$, we deduce from Proposition 2 that with probability at least $1 - 2\epsilon$,

$$I_s(\mu_{l,m}) < a(E\mu_{l,m})^2 \quad \text{and} \quad \delta < \frac{\mu_{l,m}(\mathbb{T})}{E\mu_{l,m}(\mathbb{T})} < 2 - \delta.$$

Hence, with probability at least $1 - 2\epsilon$, for each fixed $m > l$,

$$I_s(\mu_{l,m}) < \frac{a}{\delta^2}(\mu_{l,m}(\mathbb{T}))^2.$$

We cannot guarantee that this holds with positive probability for all $m > l$, but it follows that with probability at least $1 - 2\epsilon$, there is a sequence $(m_j)_{j \ge 1}$, such that for any $j$,

$$I_s(\mu_{l,m_j}) < \frac{a}{\delta^2}(\mu_{l,m_j}(\mathbb{T}))^2.$$

Suppose that $(\omega_k)_{k \ge 1}$ is such that there exists such a sequence $(m_i)_{i \ge 1}$. We normalise $\mu_{l,m_i}$ by defining the probability measure

$$v_{l,m_i} = \frac{\mu_{l,m_i}}{\mu_{l,m_i}(\mathbb{T})}.$$

Then, we may define measures $\rho_{l,m_i}$ by

$$\frac{d\rho_{l,m_i}}{dv_{l,m_i}} = (R_s v_{l,m_i})^{-1},$$

where $R_s v_{l,m_i}$ is the $s$-dimensional Riesz potential. By Theorem 9,

$$\rho_{l,m_i}(U) \le |U|^s,$$

where $|U|$ denotes the diameter of $U$. By Jensen's inequality, we have

$$\rho_{l,m_i}(\mathbb{T}) \ge (I_s(v_{l,m_i}))^{-1} = \frac{\mu_{l,m_i}(\mathbb{T})^2}{I_s(\mu_{l,m_i})} \ge \frac{\delta^2}{a}.$$

Suppose now that $\{U_k\}$ is an open cover of $F$. Then, $\{U_k\}$ covers

$$\bigcap_{j=l}^{\infty} F_j,$$
for any $l$, and in particular for the large enough $l$ chosen above. Since $F_j$ are compact, there is an $i$ such that

$$ \bigcup_k U_k \supset \bigcap_{j=l}^{m_i} F_j. $$

Since $U_k$ covers the support of $\rho_{l,m_j}$, it follows that

$$ \sum_k |U_k|^s \ge \sum_k \rho_{l,m_i}(U_k) \ge \rho_{l,m_i}(\mathbb{T}) \ge \frac{\delta^2}{a}. $$

The above proves that the $s$-dimensional Hausdorff measure of $\cap F_j$ is at least $\delta^2 a^{-1}$, and in particular, $\dim_{\mathbb{H}}F \ge s$ holds with probability at least $1-2\varepsilon$. Since $s$ can be taken as close to $1-s(c, \theta)$ as we please, we therefore have proved that $\dim_{\mathbb{H}}F \ge 1-s(c, \theta)$ holds with probability at least $1-2\varepsilon$.

Since $\varepsilon > 0$ is arbitrary, by the fact that $\mathcal{U}(\omega) \supset F$, we deduce that

$$ \dim_{\mathbb{H}}\mathcal{U}(\omega) \ge 1 - s(c, \theta) = 1 - \frac{-\log(1 - \exp(-2c\frac{\theta-1}{\theta^2}))}{\log \theta} $$

with probability 1.

## References

[1] Billard, P. "Séries de Fourier aléatoirement bornées, continues, uniformément convergentes." *Ann. Sci. Éc. Norm. Supér.* (4) 82 (1965): 131-79.

[2] Bugeaud, Y. "A note on inhomogeneous diophantine approximation." *Glasgow Math. J.* 45 (2003): 105-10.

[3] Dvoretzky, A. "On covering a circle by randomly placed arcs." *Proc. Natl. Acad. Sci. USA* 42 (1956): 199-203.

[4] Erdős, P. "Some unsolved problems." *Publ. Math. Inst. Hung. Acad. Sci. Ser. A* 6, no. 4 (1961): 221-54.

[5] Fan, A.-H. and J. Wu. "On the covering by small random intervals." *Ann. Inst. Henri Poincaré Probab. Stat.* 40, no. 1 (2004): 125-31.

[6] Galambos, J. *The Asymptotic Theory of Extreme Order Statistics*. New York-Chichester-Brisbane: Wiley, 1978.

[7] Kahane, J.-P. "Sur le recouvrement d'un cercle par des arcs disposés au hasard." *C. R. Math. Acad. Sci. Paris* 248 (1959): 184-6.

[8] Kahane, J.-P. *Some Random Series of Functions*. Cambridge: Cambridge University Press, 1985.
[9] Kahane, J.-P. "Random Coverings and Multiplicative Processes." In *Fractal Geometry and Stochastics, II (Greifswald/Koserow, 1998)*, vol. 46. Progress in Probability. 125-46. Basel: Birkhäuser, 2000.

[10] Kim, D. H. and L. Liao. "Dirichlet uniformly well-approximated numbers." *Int. Math. Res. Not.* 24 (2019): 7691-732.

[11] Kirsebom, M., P. Kunde, and T. Persson. "Shrinking targets and eventually always hitting points for interval maps." *Nonlinearity* 33, no. 2 (2020): 892-914.

[12] Mandelbrot, B. B. "Renewal sets and random cutouts." *Z. Wahrsch. V. Geb.* 22 (1972): 145-57.

[13] Orey, S. *Random Arcs on the Circle*. Minneapolis: University of Minnesota, 1971.

[14] Persson, T. "Inhomogeneous potentials, Hausdorff dimension and shrinking targets." *Ann. H. Lebesgue* 2 (2019): 1-37.

[15] Shepp, L. A. "Covering the circle with random arcs." *Israel J. Math.* 11 (1972): 328-45.

[16] Troubetzkoy, S. and J. Schmeling. "Inhomogeneous Diophantine approximation and angular recurrence properties of the billiard flow in certain polygons." *Mat. Sb.* 194, no. 2 (2003): 129-44. Translation in Sb. Math. 194, no. 2 (2003): 295-309.

[17] Waldschmidt, M. "Recent Advances in Diophantine Approximation." In *Number Theory, Analysis and Geometry*. 659-704. New York: Springer, 2012.