searching for files in Windows command prompt

• If you know the name of the file
• dir secret.* /s /p

Relationship between vec operator, Schur, Kronecker and Khatri-Rao product

\(\DeclareMathOperator{\diag}{diag}\)\(\DeclareMathOperator{\vec}{vec}\) Define \(\vec(A)\) as the operation of stacking the columns of matrix \(A\) into a vector, \(A\otimes B\) the Kronecker product, \(A\circ B\) the Schur (Hadamard) product and finally \(A\diamond B\) Bhatri-Rao product is defined as the column wise Kronecker product.

Here are some useful properties:

\[(A\otimes B)^T = A^T \otimes B^T\]

\[A \diag(x \circ y) B^T = A \diag(x) \diag(y) B^T\]

\[(C\otimes D) ( A \diamond B) = CA \diamond DB \]

\[\vec(AXB^T) = (B \otimes A) \vec(X)\]

\[\vec(A \diag(x) B^T) = (A \diamond B) x\]

\[(A\diamond B \diamond x^T) y = (A \diamond B) (x \circ y)\]

Where \(A,B,C,D,X\) are matrices and \(x,y\) are vectors of compatible dimensions.

Linear separability

(Cover, 1965)  Suppose we have \(N\) data points distributed at random in \(\mathbb{R}^d\) with an unspecified distribution.  Assume that there is no subset of \(d\) or fewer points which are linearly dependent.  We then assign each of the points to one of the two classes \(\mathcal{C}_1\) and \(\mathcal{C}_2\) with equal probability.

The fraction \(F(N,d)\) of realizations that is linearly separable is given by the expression
\[ F(N,d) = \left\{
    \begin{matrix}
    1 \quad &\mathrm{when}\; N \le d+1 \\
    \frac{1}{2^{N-1}}\sum\limits_{i=0}^d \left( \begin{matrix} N-1 \\ i \end{matrix} \right) \quad & \mathrm{when}\; N \ge d + 1
    \end{matrix}\right.
  \] Intuitively, the probability of separability increase with increasing dimension \(d\).

[TODO] include plot...

http://www-isl.stanford.edu/~cover/papers/paper76.pdf

Simply connectedness

Informally, a thick object in our space is simply-connected if it consists of one piece and does not have any "holes" that pass all the way through it.

A sphere (or, equivalently, a rubber ball with a hollow center) is simply connected, because any loop on the surface of a sphere can contract to a point, even though it has a "hole" in the hollow center.

The stronger condition, that the object has no holes of any dimension, is called contractibility.

Another characterization of simply-connectedness is the following:

\(X\) is simply-connected if and only if 

• it is path-connected, and 
• whenever \(p: [0,1] \rightarrow X\) and \(q: [0,1] \rightarrow X\) are two paths (i.e. continuous maps) with the same start and endpoint (\(p(0)=q(0)\) and \(p(1) == q(1)\)), then \(p\) and \(q\) are homotopic relative to {0,1}.

Intuitively, this means that \(p\) can be "continuously deformed" to get \(q\) while keeping the endpoints fixed. Hence the term simply connected: for any two given points in \(X\), there is one and "essentially" only one path connecting them.

Examples:

• All convex sets in \(\mathbb{R}^n\) are simply connected.
• A sphere is simply connected.

Interesting courses Spring 2015

• ECE 287 Spec Topics/Comm Theory & Syst
• TuTh 5:00p-6:20p CENTR223 Franceschetti, Massimo
• MATH 287D Statistical Learning
• TuTh 5:00p-6:20p APM 5402 Bradic, Jelena
• MATH 281C Mathematical Statistics
• TuTh 2:00p-3:20p APM 5402 Arias-Castro, Ery 
• MATH 280C Probability Theory
• MW 5:00p-6:20p APM 5402 Williams, Ruth J
• MATH 245C Convex Analysis and Optimization III
• MWF 4:00p-4:50p APM 5402 Nie, Jiawang 
• MATH 140C Foundations of Real Analysis III
• MWF 1:00p-1:50p HSS 1128A Saab, Rayan
• CSE 255 Data Mining and Predictive Analytics
• TuTh 3:30p-4:50p WLH 2207 Freund, Yoav 
• CSE 291 Neural Networks
• TuTh 2:00p-3:20p WLH 2113 Cottrell, Garrison W 
• CSE 272 Advanced Image Synthesis
• TuTh 11:00a-12:20p EBU3B 4140 Jensen, Henrik

Epigraph

$ \newcommand{\epi}{\mathop{\mathrm{epi}}} $

The epigraph of a function \(f: \mathbb{R}^n \rightarrow \mathbb{R}\) is the set of points lying on or above its graph:

\[ \text{epi} f = \{ (x,\mu) : x\in \mathbb{R}^n, \mu \in \mathbb{R}, \mu \ge f(x) \} \subset \mathbb{R}^{n+1}\]. 

Properties:

A function is convex if and only if its epigraph is a convex set.

A function is lower semicontinuous if and only if its epigraph is closed.

Entropy maximization, part II

Let \(\mathcal{X} \in \{\alpha_1, \cdots, \alpha_n\}\) be a random variable with finite alphabet, what is the distribution that will achieve maximum entropy given the constraint that \(E[f(\mathcal{X})]=\beta\) ?

We define the expectation
\[\sum_i \alpha_i p_i = \beta \] The optimization problem is given as
\[\max_\mathbf{p} H(\mathbf{p}) \; s.t., \; \sum_i p_i = 1,\; \sum_i \alpha_i p_i = \beta\] Optimizing using Lagrange multipliers \(\lambda\) and \(\mu\), we have
\[ p_i = exp^{-(1-\lambda)}exp^{\mu \alpha_i}\] which turns out to be the familiar expression
\[p_i = \frac{1}{Z}exp^{\mu \alpha_i}\] with \(Z=\sum_i exp^{\mu \alpha_i}\) being the partition function.

The above form is called a Gibbs distribution.

Now consider the problem where with \(\mathcal{X} \in \mathbb{R}^p\) and we are given the moments \(E[f_j(\mathcal{X})]=\beta_j, j=1,\dots,p\).  The optimization problem becomes
\[\max_\mathbf{p} H(\mathbf{p}) \; s.t., \; \sum_i p_i = 1,\; \sum_i \alpha_{ij} p_i = \beta_j\] The expression have the form
\[p_i = \frac{1}{Z} exp^{\sum_{j=1}^p \mu_j \alpha_{ij}}
         =\frac{1}{Z} exp^{\mathbf{\mu}^T \mathbf{\alpha_{i}}}\] Since the distribution in general has infinite support the constraint on the moment will allow one to reach a unique solution.

Entropy maximization

One interesting and well known result is that out of all finite alphabet distributions, the uniform distribution achieves maximum entropy.

The Laplace's principle of insufficient reasoning, calls for assuming uniformity unless there is additional information.

Entropy maximization is the equivalent of minimizing the KL-Divergence between the distribution \(p\) and the uniform distribution.

More precisely, let \(\mathcal{X} \in \{\alpha_1, \cdots, \alpha_n\}\) be a random variable with finite alphabet, given a family of distribution \(\mathcal{P}\) and the uniform distribution \(u\),
\[ \underset{p\in\mathcal{P}}{\text{arg min}} \;D_{KL}(p\| u) = \underset{p\in\mathcal{P}}{\text{arg max}} \;H(p)\] where \(H(p)\) is the entropy.

Proof:
\[ D(p\|u) = \sum_i p_i \log p_i +  (\sum_i p_i) \log (n) = \log (n) - H(p) \]

Note: 

This is true in general for random variables with finite support.  For RVs with infinite support,  additional constraint is required.  See Gibbs measure...

A Side Path to Statistical Mechanics

Consider a physical system with many degrees of freedom, that can reside in any one of a large number of possible states.  Let \(p_i\) denote the probability of occurrence of state \(i\), for example, with the following properties:

\[p_i\ge 0 \quad \text{for all}\; i\]and 

\[\sum_i p_i = 1\] Let \(E_i\) denote the energy of the system when it is in state \(i\).  A fundamental results from statistical mechanics tells us that when the system is in thermal equilibrium with its surrounding environment, statie \(i\) occurs with a probability define by 

\[p_i = \frac{1}{Z}\exp(-\frac{E_i}{k_BT})\] where \(T\) is the absolute temperature in kelvins, \(k_B\) is the Boltzmann's constant, and \(Z\) is a constant that is independent of all states.  The partition function \(Z\) is the normalizing constant with 

\[Z= \sum_i \exp(-\frac{E_i}{k_BT}).\]  The probability distribution is called the Gibbs distribution.

Two interesting properties of the Gibbs distribution are:

1. States of low energy have a higher probability of occurrence than states of high energy.
2. As the temperature \(T\) is reduced, the probability is concentrated on a smaller subset of low-energy states.

In the context of neural networks, the parameter \(T\) may be viewed as a pseudo-temperature that controls thermal fluctualtions representing the effect of "synaptic noise" in a neuron.  Its precise scale is irrelevant.  We can redefine the probability \(p_i\) and partition function Z as

\[p_i = \frac{1}{Z}\exp(-\frac{E_i}{T}) \] and

\[Z = \sum_i \exp(-\frac{E_i}{T})\] where \(T\) is referred to simply as the temperature of the system. 

Note that \(-\log p_i\) may be viewed as a form of "energy" measured at unit temperature.

Free Energy and Entropy

The Helmholtz free energy of a physical system, denoted by \(F\), is defined in terms of the partition function \(Z\) as follows
\[F = -T \log Z.\]  The average energy of the system is defined by
\[\lt E\gt = \sum_i p_i E_i\] The difference between the average energy and free energy is
\[\lt E \gt - F = -T\sum_i p_i \log p_i\] which we can rewrite in terms of entropy \(H\)
\[\lt E \gt - F = T H\] or, equivalently,
\[F = \lt E \gt - TH\].  The entropy of any systems tend to increase until it reaches an equilibrium, and therefore the free energy of the system will reach a minimum.

This is an important principle called the principle of minimal free energy.

Cross Entropy

The cross entropy of distributions \(p\) and \(q\) is
\[H(p,q)=E_p[-\log q]\] It can be viewed as
\[H(p,q)=H(p)+D_{KL}(p\|q)\] where \(H(p)\) is the entropy of \(p\) and \(D_{KL}(p\|q)\) is the non-negative Kullback–Leibler divergence.

From an source coding perspective, it is the total bits required to encode information if the estimated distributed \(q\) diverged from the true distribution \(p\), where \(H(p)\) is the minimum.

This quantity is very useful in machine learning.  Viewed from a vector quantization point of view, logistic regression is a way of finding an optimal boundary to classifying samples in a (possibly high dimensional) space of interest.   This expression quantifies the loss of estimating distribution \(q\) instead of the true distribution \(p\).  Since \(H(p)\) is fixed because it is a property of the underlying true distribution, minimizing cross-entropy is equivalent to minimizing KL divergence in this setting.

Conditional Expectation

Definition.  \(\lambda\) is absolutely continuous (AC) with respect to \(\mu\), written \(\lambda \ll \mu\), if \(\mu(A)=0\) implies \(\lambda(A) = 0\).

Theorem 2 Radon-Nikodym Theorem  Let \((\Omega,\mathcal{B},P)\) be the probability space.  Suppose \(v\) is a positive bounded measure and \(v \ll P\).  Then there exists an integrable random variable \(X\in \mathcal{B}\), such that
\[v(E) = \int_E XdP, \quad \forall E \in \mathcal{B} \] \(X\) is a.s. unique (\(P\)) and is written
\[X=\frac{dv}{dP}.\] We also write \(dv=XdP\)

Definition of Conditional Expectation

Suppose \(X\in L_1(\Omega,\mathcal{B},P)\) and let \(\mathcal{G}\subset \mathcal{B}\) be a sub-\(\sigma\)-field.  Then there exists a random variable \(E(X|\mathcal{G})\), called the conditional expectation of \(X\) with respect to \(\mathcal{G}\), such that

1. \(E(X|\mathcal{G})\) is \(\mathcal{G}\)-measurable and integrable.
2. For all \(G\in\mathcal{G}\) we have \[ \int_G XdP = \int_G E(X|\mathcal{G})dP\]

Notes.

1. Definition of conditional probability: Given \((\Omega,\mathcal{B},P)\), a probability space, with \(\mathcal{G}\) a sub-\(\sigma\)-field of \(\mathcal{B}\), define \[P(A|\mathcal{G})=E(1_A|\mathcal{G}), \quad A\in \mathcal{B}.\]  Thus \(P(A|\mathcal{G}) \) is a random variable such that 
1. \(P(A|\mathcal{G}) \) is \(\mathcal{G}\)-measurable and integrable.
2. \(P(A|\mathcal{G}) \) satisfies \[\int_G P(A|\mathcal{G})dP = P(A\cap G), \quad \forall G \in \mathcal{G}. \]
2. Conditioning on random variables: Suppose \(\{X_t, t\in T \}\) is a family of random variables defined on \((\Omega,\mathcal{B})\) and indexed by some index set \(T\).   Define \[\mathcal{G}:=\sigma(X_t,t\in T)\] to be the \sigma-field generated by the process \(\{X_t, t\in T \}\).  Then define \[E(X|X_t, t\in T)= E(X|\mathcal{G}).\]

Note (1) continues the duality of probability and expectation but seems to place expectation in a somewhat more basic position, since conditional probability is defined in terms of conditional expectation.

Note (2) saves us from having to make separate definitions for \(E(X|X_1)\), \(E(X|X_1,X_2)\), etc.

Countable partitions Let \(\{\Lambda_n, n\ge 1 \}\) be a partition of \(\Omega\) so thyat \(\Lambda_i \cap \Lambda_j = \emptyset, i\neq j\), and \(\sum_n \Lambda_n=\Omega\).  Define
\[\mathcal{G}=\sigma(\Lambda_n, n\ge 1)\] so that
\[\mathcal{G}=\left\{ \sum_{i\in J}\Lambda_i: J\subset\{1,2,\dots \} \right\}.\] For \(X\in L_1(P)\), define
\[E_{\Lambda_n}(X)=\int XP(d\omega|\Lambda_n)=\int_{\Lambda_n}XdP/P\Lambda_n , \] if \(P(\Lambda_n)>0\) and \(E_{\Lambda_n}(X) = 18\) if \(P(\Lambda_n)=0\).  We claim

1. \[E(X|\mathcal{G})\overset{a.s.}{=} \sum_{n=1}^\infty E_{\Lambda_n}(X) 1_{\Lambda_n}  \] and for any \(A\in \mathcal{B}\)
2. \[P(A|\mathcal{G})\overset{a.s.}{=} \sum_{n=1}^\infty P(A|\Lambda_n)1_{\Lambda_n}\]

Product Spaces, Transition Kernel and Rubini's Theorem

Lemma 1. Sectioning sets Sections of measurable sets are measurable.  If \(A\in \mathcal{B}_1 \times \mathcal{B}_2\), then for all \(\omega_1 \in \Omega_1\),
\[A_{w_1}\in \mathcal{B_2}\]
Corollary 1. Sections of measurable functions are measurable.  That is if
\[ X: (\Omega_1\times \Omega_2, \mathcal{B}_1 \times \mathcal{B}_2) \mapsto (S,\mathcal{S})\] then \[ X_{\omega_1} \in \mathcal{B}_2. \]  We say \(X_{\omega_1}\) is \(\mathcal{B}/\mathcal{S}\) measurable.

Define the transition (probability) kernel

\[K(\omega_1,A_2):\Omega_1 \times \mathcal{B}_2 \mapsto [0,1]\]

if it satisfies the following

1. for each \(\omega_1, K(\omega_1,\cdot)\) is a probability measure on \(\mathcal{B}_2\), and
2. for each \(A_2\in \mathcal{B}_2, K(\cdot, A_2)\) is \(\mathcal{B}_1/\mathcal{B}([0,1])\) measurable.

Transition kernels are used to define discrete time Markov processes where \(K(\omega_1,A_2)\) represents the conditional probability that, starting from \(\omega_1\), the next movement of the system results in a state in \(A_2\).

Theorem 1.  Let \(P_1\) be a probability measure on \(\mathcal{B}_1\), and suppose

\[K:\Omega_1 \times \mathcal{B}_2 \mapsto [0,1]\] is a transition kernel.  Then \(K\) and \(P_1\) uniquely determine a probability on \(\mathcal{B}_1 \times \mathcal{B}_2\) via the formula

\[P(A_1\times A_2)= \int_{A_1}K(\omega_1,A_2)P_1(dw_1),\] for all \(A_1\times A_2\) in the class of measurable rectangles.

Theorem 2. Marginalization  Let \(P_1\) be a probability measure on \((\Omega_1,\mathcal{B}_1)\) and suppose \(K: \Omega_1\times \mathcal{B_2} \mapsto [0,1]\) is a transition kernel.  Define \(P\) on \((\Omega_1 \times \Omega_2, \mathcal{B_1}\times \mathcal{B_2})\) by
\[P(A_1\times A_2)= \int_{A_1} K(\omega_1,A_2)P_1(d\omega_1). \]  Assume
\[X:(\Omega_1\times \Omega_2, \mathcal{B}_1\times \mathcal{B}_2) \mapsto (\mathbb{R},\mathcal{B}(\mathbb{R})) \] and furthermore suppose \(X\) is integrable.  Then
\[Y(\omega_1)=\int_{\Omega_2} K(\omega_1,d\omega_2)X_{\omega_2}(\omega_2)\] has the properties

1. \(Y\) is well defined.
2. \(Y \in B_1\)
3. \(Y \in L_1(P_1)\) and furthermore

\[\int_{\Omega_1\times \Omega_2}XdP = \int_{\Omega_1} Y(\omega_1)P_1(d\omega_1) = \int_{\Omega_1} [ \int_{\Omega_2} K(\omega_1,d\omega_2) X_{\omega_1}(d\omega_2)]P_1(\omega_1). \]

Theorem 3.  Fubini Theorem  Let \(P=P_1\times P_2\) be a product measure.  If \(X\) is \(\mathcal{B}_1 \times \mathcal{B}_2\) measurable and is either non-negative or integrable with respect to \(P\) then

\[\begin{aligned}
\int_{\Omega_1\times \Omega_2}XdP &= \int_{\Omega_1}[ \int_{\Omega_2}X_{\omega_1}(\omega_2) P_2(d\omega_2) ] P_1(d\omega_1) \\
                                                                &= \int_{\Omega_2}[ \int_{\Omega_1}X_{\omega_2}(\omega_1) P_1(d\omega_1) ] P_2(d\omega_2)
\end{aligned} \]

Clarification of Expectation

Let \(X\) be a random variable on the probability space \((\Omega, \mathcal{B}, P)\).  Recall that the distribution of X is the measure
\[F := P \circ X^{-1}\] on \((\mathbb{R},\mathcal{B}(\mathbb{R}))\) defined by
\[F(A)=P\circ X^{-1}(A) = P[X\in A].\]
The distribution function of \(X\) is
\[F(x):= F((-\infty,x])=P[X\leq x].\]  Note that the letter "F" is overloaded in two ways.

An application of the Transformation Theorem allows us to compute the abstract integral
\[E(X) = \int_\Omega XdP\] as
\[E(X) = \int_\mathbb{R} xF(dx),\] which is an integral on \(\mathbb{R}\).

More precisely,
\[E(X) = \int_\Omega X(\omega)P(d\omega)=\int_\mathbb{R} x F(dx).\]
Also given a measurable function \(g(X)\), The expectation of \(g(X)\) is
\[E(g(X)) = \int_\Omega g(X(\omega))P(d\omega)=\int_\mathbb{R} g(x) F(dx).\]
Instead of computing expectations on the abstract space \(\Omega\), one can always compute them on \(\mathbb{R}\) using \(F\), the distribution of \(X\).

Random variables and Inverse maps

A random variable is a real valued function with domain \(\Omega\) which has an extra property called measurability that allows us to make probability statements about the random variable.

Suppose \(\Omega\) and \(\Omega'\) are two sets.  Often \(\Omega' = \mathbb{R}\).  Suppose
\[X:\Omega \mapsto \Omega',\]  Then \(X\) determines an inverse map (a set valued function)
\[X^{-1}: \mathcal{P}(\Omega')\mapsto \mathcal{P}(\Omega)\] defined by
\[X^{-1}(A') = \{\omega \in \Omega : X(\omega) \in A'\}\] for \(A' \subset \Omega'\).

\(X^{-1}\) preserves complementation, union and intersections.

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\)!