Steven R. Dunbar
Department of Mathematics
203 Avery Hall
Lincoln, NE 68588-0130
http://www.math.unl.edu
Voice: 402-472-3731
Fax: 402-472-8466

Topics in
Probability Theory and Stochastic Processes
Steven R. Dunbar

__________________________________________________________________________

Borel-Cantelli Lemmas with Examples

_______________________________________________________________________

Note: These pages are prepared with MathJax. MathJax is an open source JavaScript display engine for mathematics that works in all browsers. See http://mathjax.org for details on supported browsers, accessibility, copy-and-paste, and other features.

_______________________________________________________________________________________________

### Rating

Mathematicians Only: prolonged scenes of intense rigor.

_______________________________________________________________________________________________

### Section Starter Question

How would you deﬁne events that happen inﬁnitely often in a sequence?

_______________________________________________________________________________________________

### Key Concepts

1. The ﬁrst, or “easy”, Borel-Cantelli lemma gives a criterion that an event happens inﬁnitely often with probability $0$ in terms of a convergent series.
2. The second Borel-Cantelli lemma gives a criterion that independent events happens inﬁnitely often with probability $1$ in terms of a divergent series.
3. The Borel-Cantelli Lemmas are the ﬁrst examples of $0$-$1$ Laws.
4. The Borel-Cantelli Lemmas are the basis for several interesting results.

__________________________________________________________________________

### Vocabulary

1. The Borel-Cantelli lemmas give a criterion for events to happen inﬁnitely often with probability $0$ or $1$ in terms of an inﬁnite series.
2. The Borel-Cantelli Lemmas are the ﬁrst examples of $0$-$1$ Laws.

__________________________________________________________________________

### Mathematical Ideas

#### Borel-Cantelli Lemmas

Deﬁnition. In probability space $\Omega$ with $\sigma$-ﬁeld $\mathsc{ℱ}$ and probability measure $ℙ$, $\left(\Omega ,\mathsc{ℱ},ℙ\right)$, let ${\left({A}_{n}\right)}_{n=1}^{\infty }\subseteq \mathsc{ℱ}$. Then the set

Recall that i.o. stands for “inﬁnitely often.”

Lemma 1. An element if and only if $\omega \in {A}_{n}$ for inﬁnitely many $n$ if and only if for all $n$ there exists $k\ge n$ so that $\omega \in {A}_{k}$.

The ﬁrst of the two Borel-Cantelli lemmas is sometimes called the easy half, or the direct half.

Theorem 2 (First Borel-Cantelli Lemma). If

$\sum _{n=1}^{\infty }ℙ\left[{A}_{n}\right]<\infty ,$

then

Proof. Let $𝜖>0$ be given.

for suﬃciently large $n$. Hence . □

The next Borel-Cantelli Lemma is sometimes called the hard half or the independent half. It is a partial converse to the ﬁrst Borel-Cantelli Lemma.

Theorem 3 (Second Borel-Cantelli Lemma). If ${A}_{n}\in \mathsc{ℱ}$ is a sequence of independent events and if ${\sum }_{n=1}^{\infty }ℙ\left[{A}_{n}\right]=\infty$, then

Proof. Using DeMorgan’s Law, note that

$ℙ\left[\bigcup _{k=n}^{\infty }{A}_{k}\right]=1-ℙ\left[\bigcap _{k=n}^{\infty }{A}_{k}^{c}\right].$

The proof needs to show that $ℙ\left[{\bigcap }_{k=n}^{\infty }{A}_{k}^{c}\right]=0$. Note that

$\begin{array}{llll}\hfill ℙ\left[\bigcap _{k=n}^{\infty }{A}_{k}^{c}\right]& =\prod _{k=n}^{\infty }ℙ\left[{A}_{k}^{c}\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\prod _{k=n}^{\infty }\left(1-ℙ\left[{A}_{n}\right]\right).\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

Taking the logarithm and using $log\left(1-x\right)\le -x$ gives

$\begin{array}{llll}\hfill log\left(\prod _{k=n}^{\infty }\left(1-ℙ\left[{A}_{k}\right]\right)\right)& =\sum _{k=n}^{\infty }log\left(1-ℙ\left[{A}_{k}\right]\right)\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \le -\sum _{k=n}^{\infty }ℙ\left[{A}_{k}\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =-\infty .\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

Therefore

$ℙ\left[\bigcap _{k=n}^{m}{A}_{k}^{c}\right]=exp\left(-\sum _{k=n}^{m}ℙ\left[{A}_{k}\right]\right)$

can be made arbitrarily small by choosing a large enough $m$, so ${\bigcap }_{k=n}^{\infty }{A}_{k}^{c}$ is a negligible event. □

Remark. The Borel-Cantelli Lemmas are examples of $0$-$1$ Laws. Some other examples include the Kolmogorov $0$-$1$ Law and the Hewitt-Savage $0$-$1$ Law.

#### Examples and Applications

Theorem 4. Let $s$ be any ﬁnite sequence of $k$ heads or tails (H or T). If ${A}_{n}=\left\{\omega :\left({\omega }_{n},\dots ,{\omega }_{n+k-1}\right)=s\right\}$ and . Then .

Proof. Let

$\begin{array}{llll}\hfill {B}_{1}& :=\left\{\omega :\left({\omega }_{1},\dots ,{\omega }_{k}\right)=s\right\}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill {B}_{2}& :=\left\{\omega :\left({\omega }_{k+1},\dots ,{\omega }_{2k}\right)=s\right\}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill {B}_{3}& :=\left\{\omega :\left({\omega }_{2k+1},\dots ,{\omega }_{3k}\right)=s\right\}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & ⋮\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

The ${B}_{k}$’s are independent and . Note that ${\sum }_{n=1}^{\infty }ℙ\left[{B}_{n}\right]={\sum }_{n=1}^{\infty }{\left(p,1-p\right)}^{s}=\infty ,$ so . □

Example. Let

$\begin{array}{llllllll}\hfill {k}_{1}& =1\phantom{\rule{2em}{0ex}}& \hfill \phantom{\rule{2em}{0ex}}{\ell }_{1}& =1\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill {k}_{2}& =2\phantom{\rule{2em}{0ex}}& \hfill \phantom{\rule{2em}{0ex}}{\ell }_{2}& =2\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill {k}_{3}& =4\phantom{\rule{2em}{0ex}}& \hfill \phantom{\rule{2em}{0ex}}{\ell }_{3}& =4\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \phantom{\rule{2em}{0ex}}& \hfill ⋮& \phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

Set ${A}_{n}=\left\{\omega \in \Omega :{\omega }_{{k}_{n}}={\omega }_{{k}_{n}+1}=\cdots ={\omega }_{{k}_{n}+{\ell }_{n}-1}=1\right\}$. Then .

Example. Let

$\begin{array}{llllllll}\hfill {k}_{1}& =1\phantom{\rule{2em}{0ex}}& \hfill \phantom{\rule{2em}{0ex}}{\ell }_{1}& =1\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill {k}_{2}& =4\phantom{\rule{2em}{0ex}}& \hfill \phantom{\rule{2em}{0ex}}{\ell }_{2}& =1\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill {k}_{3}& =16\phantom{\rule{2em}{0ex}}& \hfill \phantom{\rule{2em}{0ex}}{\ell }_{3}& =1\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill {k}_{4}& =64\phantom{\rule{2em}{0ex}}& \hfill \phantom{\rule{2em}{0ex}}{\ell }_{4}& =1\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \phantom{\rule{2em}{0ex}}& \hfill ⋮& \phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

Set ${A}_{n}=\left\{\omega \in \Omega :{\omega }_{{k}_{n}}=\cdots ={\omega }_{{k}_{n}+{\ell }_{n}-1}=1\right\}$. Then .

Example. Consider three independent sequences of fair coin ﬂips: ${Y}_{n}^{\left(1\right)},{Y}_{n}^{\left(2\right)},{Y}_{n}^{\left(3\right)}$, that is $ℙ\left[{Y}_{n}^{\left(i\right)}=±1\right]=\frac{1}{2}$. The associated cumulative fortunes are ${M}_{n}^{\left(1\right)},{M}_{n}^{\left(2\right)},{M}_{n}^{\left(3\right)}$. Then

Proof. Consider the probability of the event ${M}_{2n}^{\left(i\right)}=0$ for all $i$ i.o. The proof for other values is similar. Note that

$ℙ\left[{M}_{2n}^{\left(i\right)}=0\right]=\left(\genfrac{}{}{0.0pt}{}{2n}{n}\right){\left(\frac{1}{2}\right)}^{2n}\sim \frac{1}{\sqrt{\pi n}}.$

Using independence

$ℙ\left[{M}_{2n}^{\left(1\right)}={M}_{2n}^{\left(2\right)}={M}_{2n}^{\left(3\right)}=0\right]\sim \frac{1}{{\left(\pi n\right)}^{3∕2}}$

so

$\sum _{n}ℙ\left[{M}_{2n}^{\left(1\right)}={M}_{2n}^{\left(2\right)}={M}_{2n}^{\left(3\right)}=0\right].$

Hence

Example. Let $x={x}_{0}+{\sum }_{i=0}^{\infty }\frac{{x}_{i}}{1{0}^{i}}$ be a decimal expansion of $x$; i.e., ${x}_{0}\in ℤ$ and ${x}_{i}\in \left\{0,\dots ,9\right\}$ for $i\ge 1$. Deﬁne ${L}_{n}\left(x\right)={\sum }_{i=1}^{n}{x}_{i}1{0}^{i}$. For instance,

${L}_{1}\left(\pi \right)=10,{L}_{2}\left(\pi \right)=410,{L}_{3}\left(\pi \right)=1410,\dots$

and

${L}_{1}\left(\mathrm{e}\right)=70,{L}_{2}\left(\mathrm{e}\right)=170,{L}_{3}\left(\mathrm{e}\right)=8170,\dots .$

This is a natural way to associate a sequence of real numbers to a real number through its decimal expansion. Given ${𝜖}_{n}$ so that $\sum {𝜖}_{n}<\infty$, then for almost every $x\in ℝ$ (with Lebesgue measure) there exists $n\left(x\right)$ so that ${L}_{n}\left(x\right)\ge {𝜖}_{n}1{0}^{n+1}$ for every $n\ge n\left(x\right)$.

Proposition 1. Let ${\left({X}_{n}\right)}_{n\ge 1}$ be a sequence of random variables. If ${\sum }_{n=1}^{\infty }ℙ\left[|{X}_{n}|>𝜖\right]<\infty$ for all $𝜖>0$ then $\underset{n\to \infty }{lim}{X}_{n}=0$ almost surely.

Proof.

1. Set ${A}_{n}=\left[|{X}_{n}|>𝜖\right]$.
2. , so for every $𝜖>0$ there exists ${n}_{0}\left(\omega ,𝜖\right)\ge 0$ so that $|{X}_{n}\left(\omega \right)|\le 𝜖$ for all $n\ge {n}_{0}\left(\omega ,𝜖\right)$ almost surely.
3. Take a sequence $𝜖=\frac{1}{m}$ for $m\in ℕ$. Throw out a negligible set for each $𝜖=\frac{1}{m}$.
4. Almost surely, then for $\omega$ there exists ${n}_{0}\left({\omega }_{0},\frac{1}{m}\right)\ge 0$ and $|{X}_{n}\left(\omega \right)|\le \frac{1}{m}$ for all $n\ge {n}_{0}\left(\omega ,\frac{1}{m}\right)$.
5. $|{X}_{n}|$ converges to $0$ almost surely and so ${X}_{n}$ converges to $0$ almost surely.

Corollary 2. Let ${\left({X}_{n}\right)}_{n\ge 0}$ be a sequence of random variables. If ${\sum }_{n=1}^{\infty }𝔼\left[|{X}_{n}|\right]$ converges, then ${X}_{n}$ converges to zero, almost surely.

Proof. Recall that Markov’s Inequality says that

$ℙ\left[|{X}_{n}|\ge a\right]\le \frac{𝔼\left[|{X}_{n}|\right]}{a},$

and is suﬃcient to prove the corollary. □

Theorem 5 (Breiman, page 42, 3.17). Let ${Y}_{i}=±1=2{X}_{i}-1$ and set ${M}_{n}={\sum }_{k=1}^{n}{Y}_{i}$. If $ℙ\left[\text{H}\right]\ne \frac{1}{2}$ ($p=ℙ\left[{\omega }_{n}=1\right]\ne \frac{1}{2}$), then .

Proof.

$ℙ\left[{M}_{2n}=0\right]=\left(\genfrac{}{}{0.0pt}{}{2n}{n}\right){p}^{n}{\left(1-p\right)}^{n}\sim \frac{1}{\sqrt{\pi n}}{e}^{-n∕2}$

by the Local Limit Theorem. Recall that the Local Limit Theorem (for $k=0$) says

$\begin{array}{llll}\hfill ℙn\left[{M}_{2n}=0\right]& =\sqrt{\frac{2}{\pi }}{\left(\frac{p}{1-p}\right)}^{0∕2}\frac{{\left(2\sqrt{p\left(1-p\right)}\right)}^{2n}}{\sqrt{2n}}\left[exp\left(\frac{-{0}^{2}}{2\left(2n\right)}\right)+o\left(1\right)\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =K\frac{{a}^{2n}}{\sqrt{n}}\left(1+o\left(1\right)\right)\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \le {K}^{\prime }\frac{{a}^{2n}}{\sqrt{n}},\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

where

$a=2\sqrt{p\left(1-p\right)}\left\{\begin{array}{cc}=1,\phantom{\rule{1em}{0ex}}\hfill & p=\frac{1}{2}\hfill \\ <1,\phantom{\rule{1em}{0ex}}\hfill & p\ne \frac{1}{2}.\hfill \end{array}\right\$

Then $ℙ\left[{M}_{2n}=0\right]=\frac{1}{\sqrt{\pi n}}\left(1+o\left(1\right)\right)$. □

Theorem 6 (Breiman, page 42, 3.18). If $p=1∕2$, then .

Proof. Note that ${A}_{2n}=\left[{M}_{2n}=0\right]$ are not independent. Consider a subsequence ${n}_{1}<{n}_{2}<{n}_{3}<\cdots \subseteq ℕ$. Select ${m}_{k}\in ℕ$ so that ${n}_{k}<{m}_{k}<{n}_{k+1}$. Let ${C}_{k}=\left\{{Y}_{{n}_{k}+1}+\cdots +{Y}_{{m}_{k}}\le -{n}_{k}\right\}\cap \left\{{Y}_{{m}_{k}+1}+\cdots +{Y}_{{n}_{k+1}}\ge {m}_{k}\right\}$. Then ${M}_{{n}_{k}}={Y}_{1}+\cdots +{Y}_{{n}_{k}}\le {n}_{k}$ because each ${Y}_{i}=±1$. If $\omega \in {C}_{k}$, then ${M}_{{m}_{k}}\le 0$ and ${M}_{{n}_{k+1}}\ge 0$; i.e., $\omega \in {C}_{k}$ implies that .

Remark. This is a standard trick in probability theory of considering stretches ${n}_{1},{n}_{2},\dots$ so far apart that the eﬀect of what happened previously to ${n}_{k}$ is small compared to the amount ${M}_{n}$ can change between ${n}_{k}$ and ${n}_{k+1}$

Note that The proof needs to show that ${n}_{k}$ and ${m}_{k}$ can be selected so that ${\sum }_{k=1}^{\infty }ℙ\left[{C}_{k}\right]=\infty$. Now the claim is: Given any $0<\alpha <1$ and any $k\ge 1$ there exists an integer $\varphi \left(k\right)$ so that $ℙ\left[|{M}_{\varphi \left(k\right)}|. In other words, most of our paths will be outside the band $-k\le {M}_{n}\le k$ after the point $\varphi \left(k\right)$.

For ﬁxed $j$ note that $ℙ\left[{M}_{n}=j\right]\to 0$ as $n\to \infty$ Fix $k$ so that ${\sum }_{|j| as $n\to \infty$. Take $\varphi \left(k\right)$ so large that ${\sum }_{|j|. Let ${n}_{1}=1$ and ${m}_{k}={n}_{k}+\varphi \left({n}_{k}\right)$ and ${n}_{k+1}={m}_{k}+\varphi \left({m}_{k}\right)$. Then

$ℙ\left[{C}_{k}\right]=ℙ\left[{Y}_{{n}_{k}+1}+\cdots +{Y}_{{m}_{k}}\le -{n}_{k}\right]\cdot ℙ\left[{Y}_{{m}_{k}+1}+\cdots +{Y}_{{n}_{k+1}}\ge {m}_{k}\right].$

By symmetry,

$\begin{array}{llll}\hfill ℙ\left[{C}_{k}\right]& =\frac{1}{4}ℙ\left[\left|{Y}_{{n}_{k}+1}+\cdots +{Y}_{{m}_{k}}\right|\ge {n}_{k}\right]\cdot ℙ\left[\left|{Y}_{{m}_{k}+1}+\cdots +{Y}_{{n}_{k+1}}\right|\ge {m}_{k}\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\frac{1}{4}ℙ\left[\left|{Y}_{1}+\cdots +{Y}_{\varphi \left({n}_{k}\right)}\right|\ge {n}_{k}\right]\cdot ℙ\left[\left|{Y}_{1}+\cdots +{Y}_{\varphi \left({m}_{k}\right)}\right|\ge {m}_{k}\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\frac{1}{4}{\left(1-\alpha \right)}^{2}.\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

Now adding all inﬁnitely many of these ﬁxed ﬁnite values gives an inﬁnite value, so done by the Borel-Cantelli Lemma. □

The following proof is a slightly diﬀerent version of the Borel-Cantelli proof of the Strong Law of Large Numbers in the previous section.

Proof. (of Strong Law with Borel Cantelli)

Consider coin ﬂips with $ℙ\left[H=1\right]=p$ and $ℙ\left[T=0\right]=1-p$. Set ${X}_{n}={\omega }_{n}-p$ so $𝔼\left[{X}_{n}\right]=0$ for the sequence of independent random variables${\left({X}_{n}\right)}_{n=1}^{\infty }$.

$\begin{array}{llll}\hfill 𝔼\left[{\left(\frac{{S}_{n}}{n}-p\right)}^{4}\right]& =𝔼\left[{\left(\frac{{S}_{n}-np}{n}\right)}^{4}\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\frac{1}{{n}^{4}}𝔼\left[{\left(\sum _{i=1}^{4}{X}_{i}\right)}^{4}\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\frac{1}{{n}^{4}}\sum _{1\le i,j,k,l\le n}𝔼\left[{X}_{i}{X}_{j}{X}_{k}{X}_{l}\right]\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =\frac{1}{{n}^{4}}\left(\sum _{i=1}^{n}𝔼\left[{X}_{i}^{4}\right]+6\sum _{1\le i

This last line came from the fact that if $i\ne j,k,l$ then

$𝔼\left[{X}_{i}{X}_{j}{X}_{k}{X}_{l}\right]=𝔼\left[{X}_{i}\right]𝔼\left[{X}_{j}{X}_{k}{X}_{l}\right]=0$

where the ﬁrst equality is by independence. Note that $|{X}_{i}|=p$ or $1-p$ and both are less than $1$. Then $𝔼\left[{X}_{1}^{4}\right]\le 1$ and $𝔼\left[{X}_{i}^{2}{X}_{j}^{2}\right]\le 1$ and so $𝔼\left[{\left(\frac{{S}_{n}}{n}-p\right)}^{4}\right]\le \frac{1}{{n}^{4}}\left(n+3n\left(n-1\right)\right)\le \left(\frac{K}{{n}^{2}}\right)$ for a suitable value of $K$. By Corollary 11.11, $\sum 𝔼\left[{\left(\frac{{S}_{n}}{n}-p\right)}^{4}\right]<\infty$ and so ${\left(\frac{{S}_{n}}{n}-p\right)}^{4}\to 0$ almost surely, which means that $\frac{{S}_{n}}{n}-p\to 0$ almost surely. □

#### Sources

This section is adapted from: Heads or Tails, by Emmanuel Lesigne, Student Mathematical Library Volume 28, American Mathematical Society, Providence, 2005, Chapter 11.5, pages 89-96, [2]. Theorems 5 and 6 and following remarks are adapted from Probability by Leo Breiman, Addison-Wesley, Reading MA, 1968, Chapters 1 and 3. [1].

_______________________________________________________________________________________________

### Algorithms, Scripts, Simulations

#### Scripts

__________________________________________________________________________

### Problems to Work for Understanding

1. Let $\begin{array}{llllllll}\hfill {k}_{1}& =1\phantom{\rule{2em}{0ex}}& \hfill \phantom{\rule{2em}{0ex}}{\ell }_{1}& =1\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill {k}_{2}& =2\phantom{\rule{2em}{0ex}}& \hfill \phantom{\rule{2em}{0ex}}{\ell }_{2}& =2\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill {k}_{3}& =4\phantom{\rule{2em}{0ex}}& \hfill \phantom{\rule{2em}{0ex}}{\ell }_{3}& =4\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \phantom{\rule{2em}{0ex}}& \hfill ⋮& \phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

Set ${A}_{n}=\left\{\omega \in \Omega :{\omega }_{{k}_{n}}={\omega }_{{k}_{n}+1}=\cdots ={\omega }_{{k}_{n}+{\ell }_{n}-1}=1\right\}$. Show that .

2. Let $\begin{array}{llllllll}\hfill {k}_{1}& =1\phantom{\rule{2em}{0ex}}& \hfill \phantom{\rule{2em}{0ex}}{\ell }_{1}& =1\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill {k}_{2}& =4\phantom{\rule{2em}{0ex}}& \hfill \phantom{\rule{2em}{0ex}}{\ell }_{2}& =1\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill {k}_{3}& =16\phantom{\rule{2em}{0ex}}& \hfill \phantom{\rule{2em}{0ex}}{\ell }_{3}& =1\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill {k}_{4}& =64\phantom{\rule{2em}{0ex}}& \hfill \phantom{\rule{2em}{0ex}}{\ell }_{4}& =1\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & \phantom{\rule{2em}{0ex}}& \hfill ⋮& \phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

Set ${A}_{n}=\left\{\omega \in \Omega :{\omega }_{{k}_{n}}=\cdots ={\omega }_{{k}_{n}+{\ell }_{n}-1}=1\right\}$. Show that .

3. Let $x={x}_{0}+{\sum }_{i=0}^{\infty }\frac{{x}_{i}}{1{0}^{i}}$ be a decimal expansion of $x$; i.e., ${x}_{0}\in ℤ$ and ${x}_{i}\in \left\{0,\dots ,9\right\}$ for $i\ge 1$. Deﬁne ${L}_{n}\left(x\right)={\sum }_{i=1}^{n}{x}_{i}1{0}^{i}$. For instance,
${L}_{1}\left(\pi \right)=10,{L}_{2}\left(\pi \right)=410,{L}_{3}\left(\pi \right)=1410,\dots$

and

${L}_{1}\left(\mathrm{e}\right)=70,{L}_{2}\left(\mathrm{e}\right)=170,{L}_{3}\left(\mathrm{e}\right)=8170,\dots$

Show that, given ${𝜖}_{n}$ so that $\sum {𝜖}_{n}<\infty$, then for almost every $x\in ℝ$ (with Lebesgue measure) there exists $n\left(x\right)$ so that ${L}_{n}\left(x\right)\ge {𝜖}_{n}1{0}^{n+1}$ for every $n\ge n\left(x\right)$.

__________________________________________________________________________

### References

[1]   Leo Breiman. Probability. Addison Wesley, 1968.

[2]   Emmanuel Lesigne. Heads or Tails: An Introduction to Limit Theorems in Probability, volume 28 of Student Mathematical Library. American Mathematical Society, 2005.

__________________________________________________________________________

__________________________________________________________________________

I check all the information on each page for correctness and typographical errors. Nevertheless, some errors may occur and I would be grateful if you would alert me to such errors. I make every reasonable eﬀort to present current and accurate information for public use, however I do not guarantee the accuracy or timeliness of information on this website. Your use of the information from this website is strictly voluntary and at your risk.

I have checked the links to external sites for usefulness. Links to external websites are provided as a convenience. I do not endorse, control, monitor, or guarantee the information contained in any external website. I don’t guarantee that the links are active at all times. Use the links here with the same caution as you would all information on the Internet. This website reﬂects the thoughts, interests and opinions of its author. They do not explicitly represent oﬃcial positions or policies of my employer.

Information on this website is subject to change without notice.