Resources

This space serves as a repository for reference materials, study notes, cheat sheets, and technical guides compiled throughout my studies and research.

Posts below are arranged chronologically—spanning probability theory, machine learning, software tools, and computational notes. You can also use the Archive to browse all articles organized by tags.

Selected notes have also been compiled into standalone PDF documents:

  • Introduction to Probability Theory I (Spring 2020) [PDF]
  • Introduction to Probability Theory II (Fall 2020) [PDF]
  • Introduction to Latent Dirichlet Allocation [PDF]

Borel-Cantelli lemmas are converses of each other

  probability  

(1) Let $A_n$ be a sequence of events. If $\sum\limits_{k=1}^\infty P(A_k) < \infty$, then $P(A_n \:\: i.o) = 0$.
(2) If $A_n$'s are independent, $\sum\limits_{k=1}^\infty P(A_k) = \infty$, then $P(A_n \:\: i.o) = 1$
(1) Let $N := \sum\limits_{k=1}^\infty \mathbf{1}_{A_k}$. The given condition implies $E(N)<\infty$, and thus $P(N<\infty)=1$. Hence at most finitely many $\mathbf{1}_{A_k}$'s should be $1$, and this is equivalent to $P(A_n \:\: i.o) = 0$
(2) \begin{align*} P(\bigcap\limits_{k \geq m}{A_k}^c) &= \prod\limits_{k \geq m}\big( 1-P({A_k}) \big) \\ &\leq \prod\limits_{k \geq m}e^{-P(A_k)} = e^{-\sum\limits_{k \geq m} P(A_k)} = 0, \:\: \forall m>0 \end{align*} $\therefore P(\bigcup\limits_{k \geq m}{A_k}) = 1$ and $P(\limsup\limits_n{A_n}) = P(A_n \:\: i.o.) = 1$.
If $X_1, X_2, \cdots$ are independent, $A \in \mathcal{T}$, where $\mathcal{T} := \bigcap\limits_{k\geq1} \sigma(X_k, X_{k+1}, \cdots)$, then $P(A)=0$ or $1$.
Let $A \in \sigma(X_1, \cdots, X_k)$ and $B \in \sigma(X_{k+1}, \cdots, X_{k+j})$ for some $j$. Because $X_i$'s are independent, $A \perp B$. Thus $\sigma(X_1, \cdots, X_k) \perp \bigcup_j \sigma(X_{k+1}, \cdots, X_{k+j})$. Since both are $\pi$-systems, by Dynkin's $\pi$-$\lambda$ theorem, \begin{equation} \sigma(X_1, \cdots, X_k) \perp \sigma(X_{k+1}, \cdots) \end{equation} Now, let $A \in \sigma(X_1, \cdots, X_j)$ for some $j$ and $B \in \mathcal{T} \subset \sigma(X_{j+1}, \cdots)$. By (1) and similar process, \begin{equation} \sigma(X_1, \cdots) \perp \mathcal{T} \end{equation} By (2), since $\mathcal{T} \subset \sigma(X_1, \cdots)$, $\mathcal{T}$ is independent of itself.
$\therefore A \in \mathcal{T} \to P(A) = P(A \cap A) = P(A)P(A)$.

Borel-Cantelli lemmas are widely used to prove almost sure convergence/existence of limit points of random variables. e.g. By showing that $P(|X_n - X|>\epsilon)$ is summable for any given $\epsilon > 0$, one can easily check almost sure convergence from convergence in probability.
» continue reading

Limitation of $R^2$

  linear model  

For a linear regression $y_i = \beta_0 + \sum\limits_{j=1}^{p} \beta_j x_{ij}$, $1 \leq i \leq n$, suppose $x_{ij}$'s does not have any relationship with $y_i$'s. i.e. true model is $y_i = \beta_0 = \bar{y}$. Under this assumption, $$\begin{align*} \frac{\mathrm{SSE}}{\sigma^2} &\sim \chi^2(n-p-1) \overset{D}{=} \Gamma(\frac{n-p-1}{2}, 2)\\ \frac{\mathrm{SSR}}{\sigma^2} &\sim \chi^2(p) \overset{D}{=} \Gamma(\frac{p}{2}, 2)\\ \mathrm{SSE} &\perp \mathrm{SSR} \end{align*}$$ Thus, $R^2 = \frac{\mathrm{SSR}}{\mathrm{SSR} + \mathrm{SSE}} \sim \mathcal{B}(\frac{p}{2}, \frac{n-p-1}{2})$, and $E(R^2) = \frac{p}{n-1}$.

Hence expectation of $R^2$ increases as the dimension of predictors increases, regardless of fit of the model.
» continue reading

Irregularity of almost sure convergence

  probability  

Let $y_n$ be a sequence on topological space. If $\forall$ subsequence $y_{n_k}$, $\exists$ a further subsequence $y_{n(m_k)}$ s.t. $y_{n(m_k)} \to y$, then $y_n \to y$.
A sequence of random variables $X_n \to X$ in probability $\iff$ $\forall$ subsequence $X_{n_k}$, $\exists$ a further subsequence $X_{n(m_k)}$ s.t. $X_{n(m_k)} \to X$ a.s.

Theorem 1 and 2 combined implies that almost sure convergence does not come from topology. In fact, while convergence in probability forms convergence class, a.s. convergence does not. This shows that a.s. convergense is actually not a “convergence” concept that we generally think of.
» continue reading

Strong law of large numbers

  probability  

$X_1, X_2, \cdots$ are pairwise independent and identically distributed random variables. If $E|X_1| = \mu < \infty$, then $\frac{X_1 + \cdots + X_n}{n} \to \mu \:\: a.s.$

SLLN is “strong” in two senses. First, it only requires pairwise independence which is much generous condition than mutual independence required in WLLN. Second, it implies almost sure convergence rather than convergence in probability.
» continue reading

High-dimensional box

  probability  

Consider an $n$-dimensional box $[-1, 1]^n$. Suppose we randomly pick an element from this box. i.e. $\mathbf{X_n}=(X_1, \cdots, X_n)$, where $X_1, \cdots, X_n \stackrel{iid}{\sim} \mathcal{U}(-1,1)$. Then as $n \to \infty$, $P(\sqrt{\frac{n}{3}(1-\epsilon)}< \|\mathbf{X_n}\|_2 < \sqrt{\frac{n}{3}(1+\epsilon)}) \to 1$, $\forall{0<\epsilon<1}$.

This implies that the probability of observing the element at the surface of the box becomes 1 as the dimension increases. This is one of the properties of high-dimensional problems which makes them challenging.
» continue reading