Some Math

Month: March, 2014

Littlewood’s three principles (1)

Littlewood principles describe the relationship between concepts in measure space and concepts in topological space. He summerized these connections which provide a quite intuitive guide:

  • Every set is nearly a finite union of intervals.
  • Every function is nearly continuous.
  • EVery convergent sequence is nearly uniformly convergent.

However, in mathematics we need a precise meaning of the word “nearly”. So let us investigate them in each case one by one. First off, let us introduce the notation we will use. {m(E)} denotes Lebesgue measure of a measurable subset {E} in {\mathbb{R}^{d}}, where we define Lebesgue measurable in the sense that for every {\epsilon}, there exists an open set {O} such that {E\subseteq O} and {m_{*}(O-E)\leq\epsilon} and for Lebesgue measurable subset {E}, {m(E)=m_{*}(E)}. Here {m_{*}(E)} denotes the Lebesgue outer measure of a measurable subset which is defined to be {\mathrm{inf}\sum_{i=1}^{\infty}\left|Q_{i}\right|} and the infimum is taken over all countable coverings of {E} by closed cubes.

Theorem 1 Suppoe E is a measurable subset of {\mathbb{R}^{d}} with finite measure. Then, for every {\epsilon>0}, there exists a finite union {F=\bigcup_{i=1}^{N}Q_{i}} of closed cubes such that {m(E\triangle F)\leq\epsilon}.

Proof: Fix {\epsilon>0}. By definition, for this {\epsilon}, we are able to choose a family of closed cubes {\left\{Q_{i}\right\}_{i=1}^{\infty}} such that {E\subseteq\bigcup_{i=1}^{\infty}Q_{i}} and {\sum_{i=1}^{\infty}\left|Q_{i}\right|\leq m(E)+\epsilon}. Since we assume {m(E)<\infty}, the series on the left hand side converges, i.e., there exists {N>0} such that {\sum_{i>N}\left|Q_{i}\right|<\epsilon}. Now we let {F=\bigcup_{i=1}^{N}Q_{i}}, then

\displaystyle \begin{array}{lll} m(E\triangle F) & = & m(E-F)+m(F-E)\\ & \leq & m(\bigcup_{i=N+1}^{\infty}Q_{i})+m(\bigcup_{i=1}^{\infty}Q_{i}-E)\\ & \leq & \sum_{i>N}\left|Q_{i}\right|+\sum_{i=1}^{\infty}\left|Q_{i}\right|-m(E)\\ &\leq& 2\epsilon \end{array}



Random Walk (1): Reflection Principle

Consider a simple random walk {\left\{S_{i}\right\}_{i=1}^{\infty}:=\sum_{i=1}^{\infty}X_{i}} on {\mathbb{Z}} with {\mathbb{P}(X_{i}) = \left\{ \begin{array}{lr} p & : X_{i}=1\\ 1-p & : X_{i}=-1 \end{array} \right. } for all {i} which implies {X_{1}, X_{2}, ..., X_{n}} are independent.

We are interested in finding the distribution of the first passage time to a point {a\in\mathbb{Z}}, denoted by {T_{a}:=\mathrm{inf}\left\{n\ge 1| X_{n}=a\right\}}. Namely, we want to find the probability measure assigned to the event {\left\{T_{a}=n\right\}}. We note that {\left\{T_{a}=n\right\}=\left\{T_{a}>n-1\right\}\cap\left\{S_{n}=a\right\}=\left\{T_{a}>n-1\right\}\cap\left\{S_{n}=a-1\right\}\cap\left\{X_{n}=1\right\}} where the last equality follows from the fact that when the first passage time to {a} is greater then {n-1}, the walk reaches {a} at time {n} if and only if it moves up at step {n-1} from {a-1}, so

\displaystyle \mathbb{P}(T_{a}=n)=\mathbb{P}(T_{a}>n-1\&S_{n}=a) = p\cdot\mathbb{P}(T_{a}>n-1 \& S_{n-1}=a-1)

Here in the last equality we use the independence between {\left\{X_{n}=1\right\}} and {\left\{S_{n-1}=a-1\right\}}. Hence the problem now is reduced to finding the distribution of {\left\{T_{a}>n-1 \& S_{n-1}=a-1\right\}}. In order to do so, recall that for any particular path reaching {a-1} at time {n-1}, its probability is {p^{\frac{n+a}{2}-1}(1-p)^{\frac{n-a}{2}}}. Then if we are able to count the number of all paths which reach {a-1} at time {n-1} and never pass {a} at all previous steps, i.e. {T_{a}>n-1}, then the problem is solved. Denote the number of all paths by {N(n,a)}. We have the probability

\displaystyle \mathbb{P}(T_{a}=n)= p\cdot N(n,a)p^{\frac{n+a}{2}-1}(1-p)^{\frac{n-a}{2}}=N(n,a)p^{\frac{n+a}{2}}(1-p)^{\frac{n-a}{2}}


Note that the number of paths such that {S_{n-1}=a-1} is {\binom{n-1}{\frac{n+a}{2}-1}}. Now we look at the number of paths such that {S_{n-1}=a-1} and {S_{i}\ge a} for some {1\leq i\leq n-1},{N^{c}(n,a)}. Observe that we have {\binom{n-1}{\frac{n+a}{2}-1}=N(n,a)+N^{c}(n,a)}, so {N(n,a)= \binom{n-1}{\frac{n+a}{2}-1}-N^{c}(n,a)}. To compute {N^{c}(n,a)} is a rather easy task where we are going to employ an elegent argument, the reflection principle. Notice that for any particular path such that {S_{n-1}=a-1} and {S_{i}\ge a}, the walk has passed {a} for some time. Look at the first time it reaches {a}, and denote it by {\ell}. Then we reflect the walk by the following: {\hat{S}_{i}=S_{i}} for {1\leq i\leq \ell} and {\hat{S}_{i}=2a-S_{i}} for {\ell\leq i\leq n-1}. The reflection comes from {2a-S_{i}} which equals {a} plus the distance between {a} and {S_{i}}, i.e. {a-S_{i}} . Note that there must exist a bijection between the original walk and the reflected walk. In fact, the reflecting process is itself the bijection since if we reflect any walk twice we get the identity. Hence the number of original paths must equal to the number of reflected paths. It is fairly easy to compute the latter. The latter is just the set of paths such that {S_{i}\ge a} for some {1\leq i\leq n-1} and {S_{n-1}=2a-(a-1)=a+1}. Then, we don’t really need the condition {S_{i}\ge a} for some {1\leq i\leq n-1} as {S_{n-1}=a+1}. Therefore, it is just the set of paths such that {S_{n-1}=a+1} which we already how to count. There are {\binom{n-1}{\frac{n+a}{2}}} of them. So

\displaystyle N^{c}(n,a)=\binom{n-1}{\frac{n+a}{2}}


Finally, we have

\displaystyle \begin{array}{lll} \mathbb{P}(T_{a}=n) & = & N(n,a)p^{\frac{n+a}{2}}(1-p)^{\frac{n-a}{2}}\\ & = & \left[\binom{n-1}{\frac{n+a}{2}-1}-\binom{n-1}{\frac{n+a}{2}}\right]p^{\frac{n+a}{2}}(1-p)^{\frac{n-a}{2}}\\ &=& \frac{a}{n}\binom{n}{\frac{n+a}{2}}p^{\frac{n+a}{2}}(1-p)^{\frac{n-a}{2}} \\ &=& \frac{a}{n}\mathbb{P}(S_{n}=a) \end{array}

A Mild Glimpse Into Measure Theory (1)

1. Introduction

The key idea is to define a function which assigns a value {m(A)}, meaning “the size of {A}”, to a subset {A} of a given set {E}, so that

\displaystyle m(A\cup B)=m(A)+m(B)\;\mathrm{if}\;A\cap B=\emptyset

e.g. number of elements, length of an interval.

However, some issues arise in general since one cannot define a function {m:\mathscr{P}(E)\longrightarrow[0,\infty]} which satisfies above or more generally

\displaystyle m(\bigcup_{n\in\mathbb{N}}A_{n})=\sum_{n\in\mathbb{N}}m(A_{n})\;\; \mathrm{\;if\;\left\{A_{n}\right\}_{n\in\mathbb{N}}}\mathrm{\;is\;a\;family\;of\;disjoint\;sets}

Therefore, we should restrict the domain to be a special class of subsets, so called the {\sigma}-algebra.

2. Measureable Sets


2.1. Definition and Examples

Definition: Let {X} be an arbitrary set. An algebra, {\mathscr{M}\subseteq\mathscr{P}(X)}, is a family of subsets of {X} such that:

  1. {X\in\mathscr{M}}
  2. If {A\in\mathscr{M}, \mathrm{then}\;A^{c}\in\mathscr{M}}
  3. If {A_{n}\in\mathscr{M}} for all {n} from {1} to {N}, then {\bigcup_{n=1}^{N}A_{n}\in\mathscr{M}}
  4. If {A_{n}\in\mathscr{M}} for all {n} from {1} to {N}, then {\bigcap_{n=1}^{N}A_{n}\in\mathscr{M}}

Definition: Let {X} be an arbitrary set. A {\sigma}algebra, {\mathscr{M}\subseteq\mathscr{P}(X)}, is a family of subsets of {X} such that:

  1. {X\in\mathscr{M}}
  2. If {A\in\mathscr{M}, \mathrm{then}\;A^{c}\in\mathscr{M}}
  3. If {A_{n}\in\mathscr{M}} for all {n\in\mathbb{N}}, then {\bigcup_{n\in\mathbb{N}}A_{n}\in\mathscr{M}}
  4. If {A_{n}\in\mathscr{M}} for all {n\in\mathbb{N}}, then {\bigcap_{n\in\mathbb{N}}A_{n}\in\mathscr{M}}

We call elements {M\in\mathscr{M}} a {\mathscr{M}}measureable set, and call the pair {(X,\mathscr{M})}measurable space.

Remark 1: Note we can omit (3) or (4) in each definition by de Morgan laws and we can also replace condition (1) by restricting {\mathscr{M}} to be a nonempty family of subsets of {X}.
Remark 2: From this definition, we can see also: {(a)} {\emptyset\in\mathscr{M}}; {(b)} {\bigcap_{n\in\mathbb{N}}^{k} A_{n}\in\mathscr{M}} and {\bigcup_{n\in\mathbb{N}}^{k} A_{n}\in\mathscr{M}} for any finite integer {k}; hence a {\sigma}-algebra is an algebra but not vice versa.


  • {\mathscr{M}=\mathscr{P}(X)} is a {\sigma}-algebra.
  • {\mathscr{M}=\left\{\emptyset, X\right\}} is a {\sigma}-algebra on {X}.
  • {\mathscr{M}=\left\{A\in\mathscr{P}(X)|A\;\mathrm{or}\; A^c\;\mathrm{is}\;\mathrm{at}\;\mathrm{most}\;\mathrm{countable}\right\}} is a {\sigma}-algebra.
  • Let {X} be an infinite set, and let {\mathscr{F}} be the collection of all finite subsets of {X}. Then {\mathscr{F}} is not even an algebra since {X\notin\mathscr{F}}.
  • Let {X} be an infinite set, and let {\mathscr{F}} be the collection of all subsets {F} of {X} such that either {F} or {F^{c}} is finite. Then {\mathscr{F}} is an algebra but not a {\sigma}-algebra.

We now consider ways of constructing {\sigma}-algebras, first starting with a proposition.

Proposition 1 Let X be an arbitrary set, and let {\left\{\mathscr{M}_{j}\right\}_{j\in J}} be a nonempty collection of {\sigma}-algebras on {X}. Then {\bigcap_{j\in J}\mathscr{M}_{j}} is a {\sigma}-algebra on X.

Proof: Let {\mathscr{A}=\bigcap_{j\in J}\mathscr{M}_{j}}. We need to check that {\mathscr{A}} fulfills the definiton. First, note that {X\in\mathscr{M}_{j}} for all {j} since each {\mathscr{M}_{j}} is a {\sigma}-algebra, so {X\in\mathscr{A}}. Then if {A\in\mathscr{A}}, {A\in\mathscr{M}_{j}} for all {j} by definition, thereby {A^{c}\in\mathscr{M}_{j}} for all {j}, which implies {A^{c}\in\mathscr{A}}. Lastly, let {\left\{A_{n}\right\}_{n\in\mathbb{N}}} be a sequence of elements of {\mathscr{A}}, then for all {n\in\mathbb{N}} we have {A_{n}\in\mathscr{M}_{j}} for all {j\in J}. So we know {\bigcup_{n\in\mathbb{N}}\in\mathscr{M}_{j}} for all {j} by definition of {\sigma}-algebra, hence {\bigcup_{n\in\mathbb{N}}\in\mathscr{A}}.


Corollary 2 Let X be an arbitrary set, and let {\mathscr{F}} be a family of subsets of X. Then there exists a smallest {\sigma}-algebra on X that includes {\mathscr{F}}.

Proof: Let {\mathscr{C}} be the collection of {\sigma}-algebras that includes {\mathscr{F}} and note {\mathscr{C}\neq\emptyset} since {\mathscr{P}(E)\in\mathscr{C}}. Then by proposition 1, the intersection of {\sigma}-algebras in {\mathscr{C}} is desired.


We have this basic tool to construct {\sigma}-algebras. Consider any family of subsets of {E}, {\mathscr{C}\subseteq\mathscr{P}(E)}. Then there exist a unique smallest {\sigma}-algebra {\sigma(\mathscr{C})\supseteq\mathscr{C}}, i.e., {\forall C\in\mathscr{C}\;\;C\in\sigma(\mathscr{C})}. We call {\sigma(\mathscr{C})} the {\sigma}-algebra generated by {\mathscr{C}}. Namely, any {\sigma}-algebra containing {\mathscr{C}} also contains {\sigma(\mathscr{C})}. Now we turn our attention to an important {\sigma}-algebras.

Remark3: By corollary 2, we have an important relationship between {\sigma}-algebra and its subfamilies. If {\mathscr{M}} is a {\sigma}-algebra and {\mathscr{A}\subseteq\mathscr{M}}, then {\sigma(\mathscr{A})\subseteq\mathscr{M}} which will be used in the proof of the following proposition.

Definition: The Borel {\sigma}-algebra on {\mathbb{R}^{n}} is the {\sigma}-algebra generated by the collection/family of open subsets of {\mathbb{R}^{n}}, denoted by {\mathscr{B}(\mathbb{R}^{n})}. We call elements of {\mathscr{B}(\mathbb{R}^{n})} the Borel subsets of {\mathbb{R}^{n}}. In particular, if {n=1}, one often writes {\mathscr{B}(\mathbb{R})}.


Proposition 3 {\mathscr{B}(\mathbb{R})} is generated by each of the following collections of sets:

  1. the collection of all closed subsets of {\mathbb{R}}.
  2. the collection of all subintervals of {\mathbb{R}} of the form {(-\infty, b]}.
  3. the collection of all subintervals of {\mathbb{R}} of the form {(a, b]}.


Proof: Let’s denote the corresponding {\sigma}-algebra generated by the family of sets in (1), (2), (3) by {\mathscr{B}_{1}}, {\mathscr{B}_{2}}, {\mathscr{B}_{3}} respectively. It then suffices to show {\mathscr{B}(\mathbb{R})\supseteq\mathscr{B}_{1}\supseteq\mathscr{B}_{2}\supseteq\mathscr{B}_{3}} and {\mathscr{B}_{3}\supseteq\mathscr{B}(\mathbb{R})}. First consider {\mathscr{C}}, the collection of all closed subsets of {\mathbb{R}}. Notice each any closed subset is just the complement of open subsets so every closed subsets of {\mathbb{R}} is an element of the {\sigma}-algebra {\mathscr{B}(\mathbb{R})}, i.e., {\mathscr{C}\subseteq\mathscr{B}(\mathbb{R})} and by proposition 2 we know {\mathscr{B}_{1}=\sigma(\mathscr{C})\subseteq\mathscr{B}(\mathbb{R})}. Secondly, since each subintervals of the form {(-\infty,b]} is closed we have {\mathscr{B}_{2}(\mathbb{R})\subseteq\mathscr{B}_{1}(\mathbb{R})}. Finally, intervals of the form {(a,b]} can be written as

\displaystyle (a,b]=(-\infty,b]\cap(-\infty,a]^{c}

which gives us {\mathscr{B}_{3}(\mathbb{R})\subseteq\mathscr{B}_{2}(\mathbb{R})}.

For the other direction we need to show {\mathscr{B}(\mathbb{R})\subseteq\mathscr{B}_{3}(\mathbb{R})}. Notice that every open subset of {\mathbb{R}} is a countable union of open intervals and each open interval is a countable union of subintervals of the form {(a,b]} hence {\mathscr{B}(\mathbb{R})\subseteq\mathscr{B}_{3}(\mathbb{R})}.


Now we take a closer look at Borel sets on {\mathbb{R}}. Let’s denote the collection of open subsets by \mathscr{G} and the collection of closed subsets by \mathscr{F}. Then define

\displaystyle G_{\delta}:=\bigcap_{G\in\mathscr{G}} G


\displaystyle F_{\sigma}:=\bigcup_{F\in\mathscr{F}}F

We have the following consequences.


Proposition 4 Every open subset of {\mathbb{R}^{n}} is a {F_{\sigma}} and every closed subset of {\mathbb{R}^{n}} is a {G_{\delta}}.

Proof: Let {F} be a closed subset of {\mathbb{R}^{n}} and define

\displaystyle U_{n}:=\left\{x\in\mathbb{R}^{n}|\left\|x-y\right\|<1/n\;\text{for some }y\in F\right\}

Clearly {F\subseteq \bigcap_{n}U_{n}}. For the other direction, note that by definition each point in {U_{n}} is the limit of sequence of points in {F} and {F} is closed, so such limit should also be in {F}; therefore, {\bigcap_{n}U_{n}\subseteq F}.

Let {U} be an open subset of {\mathbb{R}^{n}} then {U_{c}} is closed. Thus by above {U^{c}} is a {G_{\delta}}, say {U^{c}=\bigcap_{n} U_{n}} where {\left\{U_{n}\right\}} is a sequence of open subsets of {\mathbb{R}^{n}}. Notice {U_{n}^{c}} is open for each {n}, and the identity {U=(\bigcap_{n} U_{n})^{c}=\bigcup_{n} U_{n}^{c}} shows that U is a {F_{\sigma}}.


We end this section by a interesting proposition.


Proposition 5

Definition: Let {(E_{1}, \mathscr{M}_{1})} and {(E_{2}, \mathscr{M}_{2})} be measurable spaces. The product {\sigma}-algebra on {E_{1}\times E_{2}} is defined by

\displaystyle \mathscr{M}_{1}\otimes\mathscr{M}_{2}:=\sigma(\mathscr{M}_{1}\times\mathscr{M}_{2})