Convergence Concepts

Implications of convergence

1. Almost Sure Convergence

Examples of statements that hold almost surely (a.s.)

• Let \(X,X'\) be two random variables.  Then \(X=X'\) a.s. means \[P[X=X']=1;\] that is, there exists an event \(N\in \mathcal{B}\), such that \(P(N)=0\) and if \(\omega\in N^c\), then \(X(\omega)=X'(\omega)\).
• If \(\{X_n\}\) is a sequence of random variables, then \(\lim_{n\rightarrow \infty}X_n\) exists a.s. means there exists an event \(N\in \mathcal{B}\), such that \(P(N)=0\) and if \(\omega\in N^c\) then \[\lim_{n\rightarrow \infty}X_n(w)\] exists. It also means that for a.a. \(\omega\), \[\underset{n\rightarrow \infty}{\text{lim sup}}X_n(\omega)=\underset{n\rightarrow \infty}{\text{lim inf}}X_n(\omega).\] We will write \(\lim_{n\rightarrow \infty}X_n = X\) or \(X_n \overset{a.s.}{\rightarrow}X\).
• If \(\{X_n\}\) is a sequence of random variables, then \(\sum_n X_n\) converges a.s. means there exists an event \(N\in \mathcal{B}\), such that \(P(N)=0\), and \(\omega \in N^c\) implies \(\sum_n X_n(w)\) converges.

2. Convergence in Probability

Suppose \(X_n, n\ge 1\) and \(X\) are random variables.  Then \({X_n}\) converges in probability (i.p.) to \(X\), written \(X_n \overset{P}{\rightarrow}X\), if for any \(\epsilon > 0\) \[ \lim_{n\rightarrow \infty} P[|X_n-X|>\epsilon]=0.\]
Almost sure convergence of \(\{X_n\}\) demands that for a.e. \(\omega\), \(X_n(w)-X(w)\) gets small and stay small.  Convergence i.p. is weaker and merely requires that the probability of the difference \(X_n(w)-X(w)\) being non-trivial become small.

It is possible for a sequence to converge in probability but not almost surely.

Theorem 1. Convergence a.s. implies convergence i.p. Suppose that \(X_n, n\ge 1\) and \(X\) are random variables on a probability space \((\Omega,\mathcal{B},P)\).  If \[ X_n \rightarrow X, \; a.s.\] then \[X_n \overset{P}{\rightarrow}X.\]
Proof.  If \(X_n \rightarrow X\) a.s. then for any \(\epsilon\),
\[\begin{aligned}
0\;&=P([|X_n-X|>\epsilon]i.o.) \\
  &=P(\underset{n\rightarrow \infty}{\text{lim sup}}[|X_n-X|>\epsilon]) \\
  &=\lim_{N\rightarrow \infty}P(\bigcup_{n\ge N}[|X_n-X|>\epsilon] ) \\
  &\ge \lim_{n\rightarrow \infty}P[|X_n-X|>\epsilon]
\end{aligned} \]

3. \(L_p\) Convergence

Recall the notation \(X\in L_p\) which means \(E(|X|^p)<\infty \). For random variables \(X,Y\in L_p\), we define the \(L_p\) metric for \(p\ge 1\) by
\[d(X,Y)=(E|X-Y|^p)^{1/p}.\]  This metric is norm induced because
\[\|X\|_p := (E|X|^p)^{1/p} \] is a norm on the space \(L_p\).

A sequence \(\{X_n\}\) of random variables converges in \(L_p\) to \(X\), written
\[X_n \overset{L_p}{\rightarrow}X , \] if
\[ E(|X_n-X|^p) \rightarrow 0 \] as \(n\rightarrow \infty\).

Facts about \(L_p\) convergence.

1. \(L_p\) convergence implies convergence in probability: For \(p>0\), if \(X_n\overset{L_p}{\rightarrow} X\) then \(X_n \overset{P}{\rightarrow}X \).  This follows readily from Chebychev's inequality, \[P[|X_n-X|\ge \epsilon] \leq  \frac{E(|X_n-X|^p|)}{\epsilon^p} \rightarrow 0.\]
2. Convergence in probability does not imply \(L_p\) convergence.  What can go wrong is that the \(n\)th function in the sequence can be huge on a very small set.
   Example.  Let the probability space be \( ([0,1],\mathcal{B}([0,1]),\lambda) \), where \(\lambda\) is Lebesgue measure and define
   \[X_n = 2^n 1_{(0,\frac{1}{n}) }\] then
   \[P[|X_n| > \epsilon ] = P \left( (0,\frac{1}{n}) \right)  = \frac{1}{n} \rightarrow 0 \] but
   \[ E(|X_n|^p) = 2^{np} \frac{1}{n} \rightarrow \infty \]
3. \(L_p\) convergence does not imply almost sure convergence.
   Example.  Consider the functions \(\{X_n\}\) defined on \( ([0,1],\mathcal{B}([0,1]),\lambda) \), where \(\lambda\) is Lebesgue measure.
   \begin{align*}
       X_1 &= 1_{[0,\frac{1}{2}]},  \quad  X_2 = 1_{[\frac{1}{2},1]} \\
       X_3 &= 1_{[0,\frac{1}{3}]},  \quad  X_4 = 1_{[\frac{1}{3},\frac{2}{3}]} \\
       X_5 &= 1_{[\frac{1}{3},1]},  \quad  X_6 = 1_{[0,\frac{1}{4}]}, \cdots \\
   \end{align*} and so on, Note that for any \(p>0\),
   \[ E(|X_1|^p)=E(|X_2|^p)=\frac{1}{2},\\
       E(|X_3|^p)=E(|X_4|^p)=E(|X_5|^p)=\frac{1}{3}, \\
       E(|X_6|^p)=\frac{1}{4}, \cdots \] so  \(E(|X_n|^p) \rightarrow 0\) and
   \[X_n \xrightarrow[]{L_p} 0.\]
   Observe that \(\{X_n\}\) does not converge almost surely to 0.

Limits and Integrals

Under certain circumstances we are allowed to interchange expectation with limits.

Theorem 1. Monotone Convergence Theorem (MCT). If
\[0\leq X_n \uparrow X\]then
\[0\leq E(X_n) \uparrow E(X)\]
Corollary 1.  Series Version of MCT.  If \(X_n \ge 0\) are non-negative random variables for \(n\ge1\), then
\[E(\sum_{n=1}^\infty X_n)= \sum_{n=1}^\infty E(X_n)\]
so that the expectation and infinite sum can be interchanged

Theorem 2. Fatou Lemma. If \(X_n \ge 0\), then
\[ E(\underset{n\rightarrow \infty}{\text{lim inf}} X_n ) \leq \underset{n\rightarrow \infty}{\text{lim inf}}E(X_n)\]
More generally, if there exists \(Z\in L_1\) and \(X_n\ge Z\), then
\[ E(\underset{n\rightarrow \infty}{\text{lim inf}} X_n ) \leq \underset{n\rightarrow \infty}{\text{lim inf}}E(X_n)\]
Corollary 2. More Fatou.  If \( 0 \leq X_n \leq Z\) where \(Z\in L_1\), then
\[ E(\underset{n\rightarrow \infty}{\text{lim sup}} X_n ) \ge \underset{n\rightarrow \infty}{\text{lim sup}}E(X_n)\]
Theorem 3. Dominated Convergence Theorem (DCT).  If
\[X_n \rightarrow X\] and there exists a dominating random variable \(Z\in L_1\) such that
\[ |X_n| \leq Z\]then
\[E(X_n)\rightarrow E(X) \; \text{and} \; E|X_n-X|\rightarrow 0.\]
\(
\newcommand{\scriptB}{\mathcal{B}}
\newcommand{\scriptP}{\mathcal{P}}
\newcommand{\vecX}{\mathbf{X}}
\newcommand{\vecx}{\mathbf{x}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\cplxs}{\mathbb{C}}
\newcommand{\rationals}{\mathbb{Q}}
\newcommand{\naturals}{\mathbb{N}}
\newcommand{\integers}{\mathbb{Z}}
\newcommand{\ntoinf}{n\rightarrow\infty}
\newcommand{\mtoinf}{m\rightarrow\infty}
\newcommand{\tendsto}{\rightarrow}
\)
Example of when interchanging limits and integrals without the dominating condition.  (When something very nasty happens on a small set and the degree of nastiness overpowers the degree of smallness).

Let
\[ (\Omega, \scriptB, P) = ([0,1], \scriptB([0,1]), \lambda)\] \(\lambda\) the Lebesgue measure. Define
\[ X_n = n^2 1_{(0,1/n)}. \] For any \(\omega \in [0,1]\),
\[  1_{(0,1/n)}(w) \tendsto 0,\] so
\[ X_n \tendsto 0. \] However
\[  E(X_n) = n^2 \cdot \frac{1}{n} = n \tendsto \infty, \] so
\[ E(\liminf_{\ntoinf} X_n) = 0 \le \liminf_{\ntoinf} (EX_n) = \infty \] and
\[ E(\limsup_{\ntoinf} X_n) = 0 \not\ge \limsup_{\ntoinf} (EX_n) = \infty.\]

Zero-One Laws

There are several common zero-one laws which identify the possible range of a random variable to be trivial. There are also several zero-one laws which provide the basis for all proofs of almost sure convergence.

Proposition 1. Borel-Cantelli Lemma Let \(\{A_n\}\) be any events (not necessarily independent).

If \(\sum_n{P(A_n)}<\infty\), then
\[P([A_n \; i.o.])=P(\underset{n\rightarrow \infty}{\text{lim sup}} A_n) = 0\].
Proposition 2. Borel Zero-One Law If \(\{A_n\}\) is a sequence of independent events, then

\[  \begin{equation*}
P([A_n \; i.o.])= \begin{cases}
0, \quad &  \text{iff} \sum_n P(A_n) < \infty \\
1, \quad &  \text{iff} \sum_n P(A_n) = \infty
\end{cases}
\end{equation*}
\]
Definition.  An almost trivial \(\sigma\)-field is a \(\sigma\)-field all of whose events has probability 0 or 1.

Theorem 3. Kolmogorov Zero-One Law If \(\{X_n\}\) are independent random variables with tail \(\sigma\)-field \(\mathcal{T}\), then \(\Lambda\in \mathcal{T}\) implies \(P(\Lambda)=0\) or 1 so that the tail \(\sigma\)-field is almost trivial.

Lemma 4. Almost trivial \(\sigma\)-fields  Let \(\mathcal{G}\) be an almost trivial \(\sigma\)-field and let \(X\) be a random variable measurable with respect to \(\mathcal{G}\).  Then there exists \(c\) such that \(P[X=c] = 1\).

Corollary 5.  Let \(\{X_n\}\) be independent random variables.  Then the following are true.

(a) The event
\[ [\sum_n X_n \;converges] \] has probability 0 or 1.

(b) The random variables \(\text{lim sup}_{n\rightarrow \infty}X_n\) and \(\text{lim inf}_{n\rightarrow \infty}X_n\) are constant with probability 1.

(c) The event
\[ \{\omega: S_n(\omega)/n \rightarrow 0 \} \] has probability 0 or 1.

Inequalities

Another valuable book for anyone in computer science who ever wants to bound any quantity (so, everyone!) is: The Cauchy-Schwarz Master Class: An Introduction to the Art of Mathematical Inequalities by Michael Steele.

An encyclopedic book on the topic is A Dictionary of Inequalities. While this is not a book for reading cover-to-cover, it is good to have it at your disposal. See also the supplement of the book.

Moreover, Wikipedia has an excellent list of inequalities.

For specific topics, you may consult:

• Probabilistic Inequalities
• Matrix Inequalities
• Geometric Inequalities
• The book "A=B" by Petkovsek, Wilf and Zeilberger
• Inequality cheatsheet

Dynkin's theorem

First we define a structure named \(\lambda\)-system.

A class of subsets \(\mathcal{L}\) of \(\Omega\) is called a \(\lambda\)-system if it satisfies the following postulates

1.  \(\Omega\in \mathcal{L}\)
2. \(A\in\mathcal{L} \Rightarrow A^c \in \mathcal{L}\)
3. \(n\neq m, A_nA_m = \emptyset, A_n \in \mathcal{L} \Rightarrow \cup_n A_n \in \mathcal{L}\)

It is clear that a \(\sigma\)-field is always a \(\lambda\)-system.

Next a \(\pi\)-system is a class of sets closed under finite intersections.

Dynkin's theorem

a) if \(\mathcal{P}\) is a \(\pi\)-system and \(\mathcal{L}\) is a \(\lambda\)-system such that \(\mathcal{P}\subset\mathcal{L}\), then \(\sigma(\mathcal{P})\subset \mathcal{L}\).

b) If \(\mathcal{P}\) is a \(\pi\)-system,

\(\sigma(\mathcal{P})=\mathcal{L}(\mathcal{P})\)

that is, the minimal \(\sigma\)-field over \(\mathcal{P}\) equals the minimal \(\lambda\)-system over \(\mathcal{P}\)

An example of Stein's paradox

Charles Stein showed in 1958, that a nonlinear, biased estimator of a multivariate mean has a lower MSE compared to the ML estimator.

Given a sample of \(N\) measurements of \(X\sim\mathcal{N}(\mu,\sigma I_p)\) with unknown parameter vector \(\mu\) of length \(p\).

The James-Stein estimator is given by

\begin{equation*}
\hat{\mu}_{JS}=\left (1-\frac{(p-2)\frac{\sigma^2}{N}}{\|\bar{x} \|^2}\right ) \bar{x}
\end{equation*}
where \(\bar{x}\) is the sample mean.

This estimator dominates the MLE everywhere in terms of MSE.  For all \(\mu\in\mathbb{R}^p\),

\begin{equation*}
\mathbb{E}_\mu \| \hat{\mu}_{JS}-\mu\|^2 < \mathbb{E}_\mu \| \hat{\mu}_{MLE}-\mu\|^2
\end{equation*}
This makes the MLE inadmissible for \(p\ge3\)!

The need for measure theory

The problem with measure arises when one needs to decompose a body into (possibly uncountable) number of components and reassemble it after some action on those components.  Even when you restrict attention to just finite partitions, one still runs into trouble here. The most striking example is the Banach-Tarski paradox, which shows that a unit ball \(B\) in three dimension can be disassembled into a finite number of pieces and reassembled to form two disjoint copies of the ball \(B\).

Such pathological sets almost never come up in practical applications of mathematics.  Because of this, the standard solution to the problem of measure has been to abandon the goal of measuring every subset \(E\) of \(\mathbb{R}^d\) and instead to settle for only measuring a certain subclass of
non-pathological subsets of \(\mathbb{R}^d\), referred to as the measurable sets.

The most fundamental concepts of measure is the properties of

1. finite or countable additivity
2. translation invariance
3. rotation invariance

The concept of Jordan measure (closely related to that of Riemann and Darboux integral) is sufficient for undergraduate level analysis.

However, the type of sets that arise in analysis, and in particular those sets that arise as limit of other sets, requires an extended concept of measurability (Lebesgue measurability)

Lebesgue theory is viewed as a completion of the Jordan-Darboux-Riemann theory.  It keeps almost all of the desirable properties of Jordan measure, but with the crucial additional property that many features of the Lebesgue theory are preserved under limits.

Probability space concepts

A field is a non-empty class of subsets of \(\Omega\) closed under finite union, finite intersection and complements.  A synonym for field is algebra.

From de Morgan's laws a field is also closed under finite intersection.

A \(\sigma\)-field \(\mathcal{B}\) is a non-empty class of subsets of \(\Omega\) closed under countable union, countable intersection and complements.  A synonym for \(\sigma\)-field is \(\sigma\)-algebra.

In probability theory, the event space is a \(\sigma\)-field.  This allows us enough flexibility constructing new-events from old ones (closure) but not so much flexibility that we have trouble assigning probabilities to the elements of the \(\sigma\)-field.

For the Reals, we start with sets that we know how to assign probabilities.

Supposes \(\Omega=\mathbb{R}\) and let

\(\mathcal{C}=\{(a,b],-\infty \leq a \leq b < \infty \}\)

The Borel sets is defined as

\(\mathcal{B}(\mathbb{R}) \equiv \sigma(\mathcal{C})\)

Also one can show that

\(\mathcal{B}(\mathbb{R}) = \sigma(\text{open sets in } \mathbb{R}) \)

Russell's Paradox

Shortly after the turn of the 19th century, Bertrand Russell demonstrated a hole in mathematical logic of set theory at the time.  A set can be member of itself. For sets \(R\) and \(S\)

\(R = \{S | R \notin S\}\)

The set \(R\) contains all sets that do not have themselves as members.

However, is \(R\) a member of itself?

Clearly not, since by definition \(R\) is the set of all sets that do not have themselves as member.

But then, if \(R\) does not have itself as a member then it must be a member of the set \(R\)

At that point in time, it created a huge stir among the mathematical community since most of what they do are based upon the foundation of sets.

Message passing on codes with cycles

Section 2.7 Modern coding theory

• Except for some degenerate cases, message passing in the presence of cycles is strictly suboptimal.
• For codes with cycles, message passing no longer performs MAP decoding.

Interesting courses Winter 2015

• ECE 275A Parameter Estimation II
• TuTh 5:00p-6:20p York 4050A Kreutz-Delgado, Kenneth
• ECE 285 Sparsity and Compressed Sensing
• MW 5:00p-6:20p WLH 2110 Rao, B
• ECE 259C Advanced Topics in Coding
• TuTh 5:00p-6:20p HSS 2305B Siegel, Paul
• CSE 250B Learning Algorithms
• TuTh 3:30p-4:50p CENTR 105 Dasgupta, Sanjoy
• MATH 245B Convex Analysis
• MWF 4:00p-4:50p APM 7421 Nie, Jiawang 
• MATH 251B Lie Groups
• MWF 1:00p-1:50p APM B412 Kemp, Todd 
• MATH 282B Applied Statistics II
• TuTh 11:30a-12:50p APM 5402 Arias-Castro, Ery
• MATH 280B Probability Theory 
• MW 5:00p-6:20p APM 5402 Williams, Ruth J 

Application of matrix congruence and similarity

A homework problem in statistical parameter estimation asks us to show that for two symmetric positive definite matrices \(\Sigma_1\) and \(\Sigma_2\).

If \(\Sigma_1 \leq \Sigma_2\), then \(\Sigma_1^{-1} \ge \Sigma_2^{-1}\)

Note that by assumption \(B=\Sigma_2 - \Sigma_1\) is positive semi-definite.  If I can show that the resolvent identity of  \(\Sigma_1^{-1} - \Sigma_2^{-1}\), \(\Sigma_2^{-1} (\Sigma_2 - \Sigma_1 ) \Sigma_1^{-1}\) is positive semi-definite, then the above statement is verified.

This requires the following two results:

Sylvester's Law of Inertia

Symmetric matrices \(A\) and \(B\) are congruent (i.e. there is a non-singular matrix \(C\) such that \(C^TAC=B\)) if and only if \(A\) and \(B\) have the same inertia.  They have the same number of positive, negative and zero eigenvalues.

Theorem 1.

The product of a symmetric positive definite matrix \(A\) and a symmetric matrix \(B\) has the same inertia as \(B\)

Proof

Note that \(A^{-1/2}ABA^{1/2} = A^{1/2}BA^{1/2}\).  The right hand side is similar to \(AB\), which means they have the same eigenvalues.  Since \(A^{1/2}\) is symmetric, the matrix \(A^{1/2}BA^{1/2}\) is congruent to \(B\).  By Sylvester's Law of inertia, the eignevalues of \(B\) have the same inertia as \(A^{1/2}BA^{1/2}\) and also of \(AB\).

The main point from Theorem 1 is that multiplying a positive definite matrix \(A\) to any symmetric matrix \(B\) will not change the inertia of the result.  Note that \(\Sigma_2^{-1}\) and \(\Sigma_1^{-1}\) are positive definite. We let \(\Sigma_2^{-1}= A_1\), \(\Sigma_1^{-1}=A_2\) and \(\Sigma_2-\Sigma_1 =B\), and applying Theorem 1 twice, leads to \(\Sigma_2^{-1} (\Sigma_2 - \Sigma_1 ) \Sigma_1^{-1}\) positive semi-definite.  We have shown \(\Sigma_1^{-1} - \Sigma_2^{-1}\) is indeed positive semi-definite.

Caution!

For real positive definite matrices, not all of them are symmetric!  For example, given a symmetric positive definite matrix \(B\) and a anti-symmetric matrix \(C\) (\(C^T=-C\)), the sum of which (\(A=B+C\)) is positive definite.   Extra care must be taken.  All references of positive definiteness are within the context of symmetric matrices. 

Mathematical structure of quantum mechanics

• A quantum description consists of a Hilbert space of states
• Observables are self adjoint operators on the space of states
• Time evolution is given by a one-parameter group of unitary transformations on the Hilbert space of states
• Physical symmetries are realized by unitary transformations

Postulates of quantum mechanics

The mathematical framework can be traced back to the Dirac-von Neumann axioms

Tensor Calculus

• vector (contra-variant vector) - arrow in space
• covector (co-variant vector) - gradient 

Eigenvalues and Eigenvectors

• \(\lambda\in \lambda(A) \Leftrightarrow A-\lambda I \text{ is singular} \Leftrightarrow \text{det}(A-\lambda I)=0\)
• \(\{x\neq0|x\in \mathcal{N}(A-\lambda I)\}\) is the set of all eigenvectors associated with \(\lambda\).  
• \(\mathcal{N}(A-\lambda I)\) is the eigenspace for A.

Diagonalizability of a matrix

• A nilpotent matrix \(A=\{A\in M_n |A^2=0\}\) is not diagonalizable. 
• Two matrices \(A\) and \(B\) are similar whenever these exists a nonsingular matrix \(P\) such that \(P^{-1} AP=B\)
• A matrix can be diagonalized if it is similar to a diagonal matrix \(D\), i.e. \(P^{-1}AP=D\)
• Or equivalently, \(AP_{*,j}=\lambda_j P_{*,j}\)
• \(A\) is diagonalizable if and only if \(A\) possesses a complete set of eigenvectors.
• Or equivalently, the geometric multiplicity of \(\lambda_i\) is equal to the algebraic multiplicity of \(\lambda_i\) for each \(\lambda_i\in \lambda(A)\)

Orthogonality Principle for LS solution

Geometric condition for a Least-Squares Solutions: \(e=y-Ax\perp\mathcal{R}(A)\)

Geometric condition for a Minimum Norm LS Solution: \(x\in\mathcal{N}(A)^\perp\)

Notes on interesting mathematical objects

Banach space

• A complete linear vector space

Hilbert space

• A complete inner product space (also a Banach space)
• Well defined concept of orthogonality or angle
• Norm induced by the associated inner product

Closed set

• contains all its limit points
• complement of an open set

Complete set (M)

• every Cauchy sequence of points in M has a limit in M
• there are no points missing (inside or at the boundary)

Personalities in RMT

• Roman Vershynin, UMich
• http://www-personal.umich.edu/~romanv/
• Mark Rudelson, U of Missouri
• http://www.math.missouri.edu/~rudelson/
• Mérouane Debbah, Supelec, France
• http://www.flexible-radio.com/merouane-debbah
• Romain Couillet, Supelec, France
• http://couillet.romain.perso.sfr.fr/

On control and analysis of dynamical systems

• Even when simple feed-forward control of a linear, time invariant, first order plant was involved, the analysis of the resulting closed-loop dynamics could be involved - the equations becomes linear, time-varying equations.  
• Once feedback control is involved, the equations become nonlinear and time varying.