# Speed of convergence in Lebesgue's density theorem

Let $\lambda=\text{unif}([0,1])$ be uniform distribution on $[0,1]$ and $B$ be any Borel set. Lebesgue's density theorem states that for $\lambda$-almost all $x\in[0,1]$ the limit $$\lim_{\epsilon\downarrow o}\frac{\lambda([x-{\epsilon},x+\epsilon]\cap B)}{2\epsilon}$$ exists and is either $0$ or $1$. Im interested in a 'global' approximation.

For $n\geq 1$ let $$D_n:=\big\{\frac{0}{2^n},\frac{1}{2^n},\frac{2}{2^n},\dots,\frac{2^n-1}{2^n}\big\}.$$

Now i look at the expression

$$a_n:=(1/2)^n\cdot\sum_{x\in D_n}\frac{\lambda\big([x,x+(1/2)^n]\cap B\big)}{(1/2)^n}\cdot\bigg[1-\frac{\lambda\big([x,x+(1/2)^n]\cap B\big)}{(1/2)^n}\bigg].$$ So for large $n$ every summand should be close to Zero. Additionally every summand gets weighted by $(1/2)^n$.

The number $a_n$ tells you something about how 'intervall-like' $B$ is. Since you can approximate every $B$ by finite unions of intervalls you can show that $a_n\rightarrow 0$ for each $B$. I want to know: How fast does $a_n$ tend to Zero? Is it true that $\sum_{n\geq 1}a_n<\infty$ for any measurable $B$? If this is not the case, can you provide an example of a set $B$ with $\sum_n a_n=\infty$?

Remark: This is a special instance of a more general question I posted on Stackexchange (before I knew that Overflow exists, sorry about that): https://math.stackexchange.com/questions/1835620/switching-independent-experiments-does-i-ax-1-dots-x-n-y-n1-y-n2-dots

The answer is negative. In fact, let us show that $a_n$ as defined in the question may converge to $0$ however slowly. Indeed, let $(\epsilon_j)$ is any sequence in $(0,1]$ converging to $0$ slowly and regularly enough, in the sense that $$\epsilon_{j-1}-\epsilon_j\ge2^{2-j}\tag{1}$$ eventually in $j$ -- that is, for some natural $j_0$ and all natural $j\ge j_0$. For instance, this condition will hold if $\epsilon_j$ is (eventually in $j$) of the form $2^{2-j}$ or $j^{-a}$ or $(\underbrace{\ln\dots\ln}_N j)^{-a}$ for some real $a$ and some natural $N$.

In what follows, $j$ is a natural number $\ge j_0$.
Let $$k_j:=\lfloor2^j\epsilon_j\rfloor$$ and $$r_j:=k_j/2^j.$$ Then $$\epsilon_j-\tfrac1{2^j}<r_j\le\epsilon_j\tag{2}$$ and hence, by the regularity condition $(1)$, $r_j<r_{j-1}$. Let $$\Delta_j:=(r_{j},r_{j-1}].$$ Note that the intervals $\Delta_j$ are pairwise disjoint. Let then $$s_{j,\ell}:=r_{j}+\ell/2^{j+1}$$ for $\ell=0,\dots,\ell_j:=(r_{j-1}-r_{j})2^{j+1}$, so that $\ell_j$ is even, and $$\delta_{j,\ell}:=(s_{j,\ell},s_{j,\ell+1}].$$ Note that $\Delta_j$ is the disjoint union of the $\delta_{j,\ell}$'s over $\ell=0,\dots,\ell_j-1$. Let, finally,
$$B:=\bigcup_{j=j_0}^\infty\bigcup_{q=0}^{\ell_j/2-1}\delta_{j,2q}.$$

Take now any large enough natural $n$. Let $$H_{n,i}:=\Big(\frac i{2^n},\frac{i+1}{2^n}\Big]$$ for $i=0,\dots,2^n-1$.

From now on, suppose also that $j\ge n\ge j_0$.

Then $|\delta_{j,\ell}|=1/2^{j+1}<1/2^n=|H_{n,i}|$, where $|\cdot|$ denotes the Lebesgue measure. For any given $i=0,\dots,2^n-1$ such that $H_{n,i}\subseteq\Delta_j$, we have $$B\cap H_{n,i}=\bigcup_{q=q_1}^{q_2}\delta_{j,2q} \quad\text{and}\quad H_{n,i}=\bigcup_{\ell=2q_1}^{2q_2+1}\delta_{j,\ell}$$ for some integers $q_1=q_{1;n,i}$ and $q_2=q_{2;n,i}$ such that $0\le q_1\le q_2\le\ell_j/2-1$. Hence, $|B\cap H_{n,i}|=\frac12|H_{n,i}|=\frac12\frac1{2^n}$.
So, $$\frac{|B\cap H_{n,i}|}{2^{-n}}\Big(1-\frac{|B\cap H_{n,i}|}{2^{-n}}\Big) =\frac14$$ -- for each $j\in\{n,n+1,\dots\}$ and each $i=0,\dots,2^n-1$ such that $H_{n,i}\subseteq\Delta_j$.
By $(2)$ and $(1)$, the length $|\Delta_j|$ of the dyadic interval $\Delta_j$ is $r_{j-1}-r_j\ge\epsilon_{j-1}-\epsilon_j-\tfrac1{2^{j-1}}\ge\tfrac12\,(\epsilon_{j-1}-\epsilon_j)$, and so, for a given natural $n\ge j_0$, the dyadic interval $\Delta_j$ contains at least $2^{n-1}(\epsilon_{j-1}-\epsilon_j)$ dyadic intervals $H_{n,i}$. So, for $a_n$ as defined in the question, we have
$$a_n\ge\frac1{2^n}\sum_{j=n}^\infty\ \sum_{i\colon H_{n,i}\subseteq\Delta_j} \frac{|B\cap H_{n,i}|}{2^{-n}}\Big(1-\frac{|B\cap H_{n,i}|}{2^{-n}}\Big) \ge \frac1{2^n}\sum_{j=n}^\infty 2^{n-1}(\epsilon_{j-1}-\epsilon_j)\frac14 =\frac{\epsilon_{n-1}}8.$$ Thus, $a_n\ge\frac{\epsilon_{n-1}}8$ for all $n\ge j_0$. For instance, letting $\epsilon_j=1/j$ for all natural $j$, we have
$\sum_n a_n=\infty$.

• Thanks a lot for this detailed and understandable answer! Jun 24 '16 at 17:02
• I have provided details on my previous comment that $a_n$ may converge to $0$ however slowly. Jun 26 '16 at 3:15

As Iosif Pinelis has just written, the answer is, indeed, negative. However, I would still like to make a couple of comments about this question which are too long for a comment.

First of all, this question is not about the Lebesgue density theorem. An important feature of this theorem is that it deals with neighborhoods of (almost) all points, and because of that it requires some information about the geometry of the space under consideration. However, the neighborhoods in the question are just the dyadic intervals which form a monotone sequence of partitions of the unit interval, so that the question belongs entirely to the measure category and is just about the properties of this sequence of partitions. In fact, the numbers $a_n$ are nothing else than $$a_n = \| 1_B - \mathbf E(1_B|\mathfrak A_n) \|^2 \;,$$ where $\|\cdot\|$ is the $L^2$ norm on the unit interval, $\mathfrak A_n$ is the algebra of order $n$ dyadic intervals, and $f\mapsto \mathbf E(f|\mathfrak A_n)$ is the projection of $L^2$ onto the space of $\mathfrak A_n$-measurable functions given by the conditional expectation ($\equiv$ averaging over the order $n$ dyadic intervals). The convergence $$\mathbf E(1_B|\mathfrak A_n) \to 1_B$$ in various senses (in particular, in $L^2$) is then just the theorem on convergence of conditional probabilities (more generally also known under the name of the martingale convergence theorem).

The example of Iosif Pinelis - if I understand it correctly - then boils down just to the following. First of all, there is no need to stick to the unit interval, and it is more convenient to describe it in (the equivalent) terms of the product (Bernoulli) measure space whose base is the two-point set $X=\{0,1\}$ endowed with the uniform measure. Then $\mathfrak A_n$ is just the algebra generated by the first $n$ coordinates. Now, let $A_n$ be a sequence of subsets of $X^n$, let $A'_n\subset X^{n+1}$ be the sets of strings obtained from $A_n$ by adding 1 in the $(n+1)$-th position, let $C'_n\in\mathfrak A_{n+1}$ be the associated cylinder sets, and let $$B = \bigcup_n C'_n \;.$$ If the cylinder sets $C_n\in\mathfrak A_n$ associated with the sets $A_n$ are pairwise disjoint, then $|1_B-E(1_B|\mathfrak A_n)|$ vanishes on $C'_k$ for $k\le n-1$ and is 1/2 otherwise, whence $$\sum \| 1_B - \mathbf E(1_B|\mathfrak A_n) \|^2 = \infty$$ iff $$\sum n |C_n| = \infty \;.$$ These two conditions (disjointness of the sets $C_n$ and divergence of the above series) can be easily satisfied.

• Thanks for the answer! 'fair coin tosses' is what the question comes from. In the end of my original questions I posted the link to a question of mine on Stackexchange. With this question here I wanted to clarify if Borel-Cantelli is applicable to prove something concerning fair coin tosses. Iosif Pinelis' example shows that this strategy won't work for my usual question. I would be glad if you could take a look at my question on Stackexchange (and probably say why that question is in general 'negativ' as well)! Thanks! Jun 24 '16 at 17:13
• To begin with, what does $I$ denote in that question?
– R W
Jun 25 '16 at 14:20
• $I$ is indicator-function $I((X_1,X_2,\dots)\in A)=I_A(X_1,X_2,\dots)$, i will edit it. Jun 25 '16 at 16:02

For reals $x<y$ denote $\rho(x,y)=1/2^n$ if integer $n$ is minimal such that there exist integer $i$ with $x<i/2^n\leqslant y$. We have $\rho(x,y)\geqslant |x-y|/2$ and in average'' $\rho(x,y)$ behaves like $|x-y|$, whatever this means. Your sum is nothing but $$\sum a_n=\int_0^1\int_0^1 \frac{\chi_A(x)\chi_{\bar{A}}(x)dxdy}{\rho(x,y)}$$ (maybe I loss a factor of 2 or something like that). So, the question is essentially the following: does integral $$\int_0^1\int_0^1 \frac{\chi_A(x)\chi_{\bar{A}}(x)dxdy}{|x-y|}$$ converge? By Tonelli theorem, this is equivalent to the following question: is it true that for almost all points $x\in A$ we have $\int_{\bar{A}} dy/|x-y|<\infty$? I doubt that such refinement of density theorem holds. Actually I think that there is no divergent integral $\int_0^{\dots} \varphi(t)dt$ of a positive function $\varphi$ for which $\int_{\bar{A}} \varphi(|a-y|)dy$ converges for almost all $a\in A$ whenever $A$ is a measurable subset of $[0,1]$. I would search for examples of perfect compact sets of Cantor type with very small segments being removed on each step.

My original incorrect claims were too strong, but the argument does give the following, which is perhaps of some interest also:

Suppose that $B$ is closed, and write the complement as a disjoint union of open intervals $B^c=\bigcup I_n$. If $\sum |I_n|\log |I_n|^{-1}<\infty$, then $\sum a_n(B)<\infty$.

This also says something about arbitrary Borel sets $B$ by using inner regularity.

To prove this, suppose we had an $N$ for which $\sum_{n\le N} a_n$ is very large, and in particular much larger than $\sum |I|\log |I|^{-1}$. Let $I$ be one of these intervals.

I now want to take a look at what happens to $\sum a_n$ if I add $I$ to $B$. Clearly, your quadratic function of the density is only affected for those dyadic intervals that have a part in $I$ as well as a part in $I^c$. At each level $n$, there are at most two such intervals. If $|I|\ll 2^{-n}$, then the density of a dyadic interval at level $n$ changes by not more than $2^n|I|$. So the change of $a_n$ will be $\lesssim |I|$. There are $\lesssim -\log |I|$ such levels $n$. At the others levels $n$, with $|I|\gtrsim 2^{-n}$, it's clear that $a_n$ changes by $\lesssim 2^{-n}$.

We obtain a total change $\lesssim -|I|\log |I|$ to $\sum a_n$ when $I$ is included in $B$. By successively adding intervals, we can pass to a new set $C\supseteq B$, of almost full measure, and $$\sum_{n\le N} a_n(B) \lesssim \sum_{n\le N} a_n(C) + \sum |I|\log |I|^{-1} .$$ However, $\sum_{n\le N} a_n(C)$ is clearly not very large, so it follows that $\sum_{n\le N} a_n(B)$ can actually not be made arbitrarily large.

• It is bit unclear what exactly does your argument prove. That $\sum_{n\le N} a_n$ always does not exceed, say, 100 for any set? Jun 24 '16 at 6:02
• @ChrtistianRemling Hm, what if $K$ is a union of segments $[2i/2^N,(2i+1)/2^N]$ for $i=0,\dots,2^{N-1}-1$? On the first glance, all $a_n$ for $n< N$ are bounded from below by $1/8$ or something like that? Jun 24 '16 at 7:57
• @FedorPetrov I think you're right. Let $K_N$ be the set you defined, then you get $a_n(K_N)=1/4$ for all $n<N$ and $a_n(K_N)=0$ for all $n\geq N$, so $\sum_n a_n(K_N)=(N-1)/4$. But there really is no "limit-analogue" for the sets $K_N$ as $N\rightarrow\infty$. 'Infinite' sets can't be that balanced. I'm going to think about your and ChristianRemling's answer now, thanks so far! Jun 24 '16 at 14:35