Stochastic Modeling

Formula Sheet¶

Most Important Concepts¶

Probability Space & Axioms: Foundation of all probability theory
Conditional Probability: Essential for Bayesian reasoning
Expectation & Variance: Fundamental measures of central tendency and spread
Limit Theorems: LLN and CLT are the most important results in probability
Markov Property: Foundation for Markov Chains and many stochastic processes
Stationary Distributions: Long-term behavior of Markov Chains
Poisson Process: Fundamental continuous-time stochastic process

Problem-Solving Strategies¶

Identify the Distribution: Recognize which distribution the problem involves
Use Definitions: Start with the definition (PMF, PDF, or property)
Check Conditions: Verify all conditions are met before applying theorems
Use Linearity: Expectation is linear - use this whenever possible
Conditioning: Break complex problems into simpler conditional problems
Symmetry: Look for symmetry to simplify calculations
Approximations: Use CLT for large $n$ approximations

Probability¶

\begin{align*} P(E|F) &= \frac{P(E \cap F)}{P(F)} & P(E) &= P(E|A)P(A) + P(E|A^c)P(A^c) \\ P(A|E) &= \frac{P(E|A)P(A)}{P(E)} & P(A \cap B) &= P(A)P(B|A) = P(B)P(A|B) \end{align*}

(1)

Expectation & Variance¶

\begin{align*} \mathbb{E}[X] &= \sum x P(X=x) & \mathbb{E}[X] &= \int x f_X(x) dx \\ \operatorname{Var}(X) &= \mathbb{E}[X^2] - (\mathbb{E}[X])^2 & \operatorname{Var}(aX+b) &= a^2 \operatorname{Var}(X) \\ \operatorname{Cov}(X,Y) &= \mathbb{E}[XY] - \mathbb{E}[X]\mathbb{E}[Y] & \rho_{X,Y} &= \frac{\operatorname{Cov}(X,Y)}{\sqrt{\operatorname{Var}(X)\operatorname{Var}(Y)}} \end{align*}

(2)

Distributions¶

\begin{align*} \text{Binomial: } P(X=k) &= \binom{n}{k} p^k (1-p)^{n-k} & \mathbb{E}[X] = np, \operatorname{Var}(X) = np(1-p) \\ \text{Poisson: } P(X=k) &= \frac{\lambda^k e^{-\lambda}}{k!} & \mathbb{E}[X] = \lambda, \operatorname{Var}(X) = \lambda \\ \text{Geometric: } P(X=k) &= (1-p)^{k-1} p & \mathbb{E}[X] = 1/p, \operatorname{Var}(X) = (1-p)/p^2 \\ \text{Normal: } f(x) &= \frac{1}{\sqrt{2\pi\sigma^2}} e^{-(x-\mu)^2/(2\sigma^2)} & \mathbb{E}[X] = \mu, \operatorname{Var}(X) = \sigma^2 \\ \text{Exp: } f(x) &= \lambda e^{-\lambda x} & \mathbb{E}[X] = 1/\lambda, \operatorname{Var}(X) = 1/\lambda^2 \end{align*}

(3)

Limit Theorems¶

\begin{align*} \text{LLN: } \frac{S_n}{n} &\xrightarrow{P} \mu & \text{CLT: } Z = \frac{S_n - \mu}{\sigma} &\xrightarrow{d} N(0,1) \\ \text{Chebyshev: } P(|X-\mu| \geq \varepsilon) &\leq \frac{\sigma^2}{\varepsilon^2} & \text{Markov: } P(X \geq a) &\leq \frac{\mathbb{E}[X]}{a} \end{align*}

(4)

Markov Chains¶

\begin{align*} \text{Markov: } P(X_{n+1}|X_n, \ldots, X_0) &= P(X_{n+1}|X_n) & \text{Chapman-Kolmogorov: } p_{ij}^{(m+n)} &= \sum_k p_{ik}^{(m)} p_{kj}^{(n)} \\ \text{Stationary: } \vec{\pi} &= \vec{\pi} P & \text{Convergence: } \vec{\nu} P^n &\to \vec{\pi} \end{align*}

(5)

Stochastic Processes¶

\begin{align*} \text{Mean: } m_X(t) &= \mathbb{E}[X_t] & \text{Correlation: } R_X(t_1,t_2) &= \mathbb{E}[X_{t_1}X_{t_2}] \begin{cases} t_1 = t_2 \\ t_1 \neq t_2 \end{cases}\\ \text{Covariance: } C_X(t_1,t_2) &= R_X(t_1,t_2) - m_X(t_1)m_X(t_2) & \text{Stationary: } R_X(t_1,t_2) &= R_X(|t_2-t_1|) \end{align*}

(6)

Differentiation Rules¶


Power Rule	$\frac{d}{dx} x^n = n x^{n-1}$
Exponential	$\frac{d}{dx} e^{ax} = a e^{ax}$
Natural Log	$\frac{d}{dx} \ln(x) = \frac{1}{x}$
Product Rule	$\frac{d}{dx} [f(x)g(x)] = f'(x)g(x) + f(x)g'(x)$
Quotient Rule	$\frac{d}{dx} \left[\frac{f(x)}{g(x)}\right] = \frac{f'(x)g(x) - f(x)g'(x)}{[g(x)]^2}$
Chain Rule	$\frac{d}{dx} f(g(x)) = f'(g(x)) \cdot g'(x)$

Integration Rules¶


Power Rule	$\int x^n dx = \frac{x^{n+1}}{n+1} + C$ (for $n \neq -1$ )
Exponential	$\int e^{ax} dx = \frac{1}{a} e^{ax} + C$
Natural Log	$\int \frac{1}{x} dx = \ln\|x \| + C$
Integration by Parts	$\int u dv = uv - \int v du$

Integration by Parts Example:

\int x e^{ax} dx = \frac{x e^{ax}}{a} - \frac{1}{a} \int e^{ax} dx = \frac{e^{ax}}{a^2} (a x - 1) + C

(7)

Special Integrals¶

\begin{align*} \int_{-\infty}^{\infty} e^{-x^2} dx &= \sqrt{\pi} \\ \int_0^{\infty} x^n e^{-ax} dx &= \frac{n!}{a^{n+1}} \quad \text{(Gamma function: } \Gamma(n+1) = n!) \\ \int_0^{\infty} e^{-ax} dx &= \frac{1}{a} \quad \text{for } a > 0 \\ \int_0^{\infty} x e^{-ax} dx &= \frac{1}{a^2} \\ \int_0^{\infty} x^2 e^{-ax} dx &= \frac{2}{a^3} \end{align*}

(8)

Taylor Series¶

\begin{align*} e^x &= \sum_{n=0}^{\infty} \frac{x^n}{n!} = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \ldots \\ \ln(1+x) &= \sum_{n=1}^{\infty} (-1)^{n+1} \frac{x^n}{n} = x - \frac{x^2}{2} + \frac{x^3}{3} - \ldots \quad \text{for } |x| < 1 \\ \sin(x) &= \sum_{n=0}^{\infty} (-1)^n \frac{x^{2n+1}}{(2n+1)!} = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \ldots \\ \cos(x) &= \sum_{n=0}^{\infty} (-1)^n \frac{x^{2n}}{(2n)!} = 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \ldots \\ e^{x} &\approx 1 + x + \frac{x^2}{2} \quad \text{(2nd order Taylor)} \end{align*}

(9)

Common Series¶

\begin{align*} \sum_{k=0}^{\infty} r^k &= \frac{1}{1-r} \quad \text{for } |r| < 1 \\ \sum_{k=1}^{\infty} k r^{k-1} &= \frac{1}{(1-r)^2} \quad \text{for } |r| < 1 \\ \sum_{k=1}^{\infty} k^2 r^{k-1} &= \frac{1+r}{(1-r)^3} \quad \text{for } |r| < 1 \\ \sum_{k=1}^{n} k &= \frac{n(n+1)}{2} \\ \sum_{k=1}^{n} k^2 &= \frac{n(n+1)(2n+1)}{6} \\ \sum_{k=1}^{\infty} \frac{1}{k^2} &= \frac{\pi^2}{6} \quad \text{(Basel problem)} \\ H_n &= \sum_{k=1}^n \frac{1}{k} \approx \ln(n) + \gamma \quad \text{where } \gamma \approx 0.5772 \end{align*}

(10)

Probability Theory Fundamentals¶

Probability Space & Axioms¶

A probability space is a triple $(\Omega, \mathcal{A}, P)$ where:

$\Omega$ : Sample space - set of all possible outcomes
$\mathcal{A}$ : $\sigma$ -algebra - set of all measurable events (subsets of $\Omega$ )
$P$ : Probability measure satisfying Kolmogorov’s Axioms:

\begin{align*} 1. &\quad 0 \leq P(E) \leq 1 \quad \forall E \in \mathcal{A} \\ 2. &\quad P(\Omega) = 1 \\ 3. &\quad P\left(\bigcup_{i=1}^{\infty} E_i\right) = \sum_{i=1}^{\infty} P(E_i) \quad \text{for pairwise disjoint } E_i \end{align*}

(11)

Key Properties¶

\begin{align*} P(\emptyset) &= 0 \\ P(A^c) &= 1 - P(A) \\ P(A \setminus B) &= P(A) - P(A \cap B) \\ P(A \cup B) &= P(A) + P(B) - P(A \cap B) \quad \text{(Inclusion-Exclusion)} \end{align*}

(12)

Conditional Probability¶

Interpretation: Restricts the sample space to $F$ and considers the relative frequency of $E$ within $F$ .

Independence¶

For $n$ events $E_1, E_2, \ldots, E_n$ :

P\left(\bigcap_{i=1}^n E_i\right) = \prod_{i=1}^n P(E_i)

(13)

Important: Independence is pairwise and for all subsets, not just pairs.

Law of Total Probability¶

For a partition $A_1, A_2, \ldots, A_n$ of $\Omega$ :

P(E) = \sum_{i=1}^n P(E|A_i) \cdot P(A_i)

(14)

Simplified (for binary partition):

P(E) = P(E|A) \cdot P(A) + P(E|A^c) \cdot P(A^c)

(15)

Bayes’ Theorem¶

P(A|E) = \frac{P(E|A) \cdot P(A)}{P(E)} = \frac{P(E|A) \cdot P(A)}{P(E|A) \cdot P(A) + P(E|A^c) \cdot P(A^c)}

(16)

Example: Medical testing - given test result, compute probability of disease.

Random Variables¶

Definition¶

A random variable (RV) $X: \Omega \to \mathbb{R}$ assigns a numerical value to each outcome.

Types of Random Variables¶

Type	Definition	Example
Discrete	Takes finite or countable values	Dice roll, coin toss
Continuous	Takes uncountable values	Height, time

Probability Mass Function (PMF)¶

For discrete RV $X$ :

P(X = x_i) = p_X(x_i) \quad \text{where } \sum_i p_X(x_i) = 1

(17)

Probability Density Function (PDF)¶

For continuous RV $X$ :

P(a \leq X \leq b) = \int_a^b f_X(x) \, dx \quad \text{where } \int_{-\infty}^{\infty} f_X(x) \, dx = 1

(18)

Distribution Function (CDF)¶

For any RV $X$ :

F_X(t) = P(X \leq t) = \begin{cases} \sum_{x_i \leq t} P(X = x_i) & \text{for discrete } X \\ \int_{-\infty}^t f_X(x) \, dx & \text{for continuous } X \end{cases}

(19)

Properties: $F_X$ is right-continuous, non-decreasing, with $\lim_{t\to-\infty} F_X(t) = 0$ and $\lim_{t\to\infty} F_X(t) = 1$ .

Expectation (Mean)¶

\mathbb{E}[X] = \begin{cases} \sum_i x_i P(X = x_i) & \text{for discrete } X \\ \int_{-\infty}^{\infty} x f_X(x) \, dx & \text{for continuous } X \end{cases}

(20)

Linearity of Expectation:

\mathbb{E}[aX + bY] = a\mathbb{E}[X] + b\mathbb{E}[Y] \quad \text{for any RVs } X, Y \text{ and constants } a, b

(21)

Important: Linearity holds regardless of independence.

Variance¶

\operatorname{Var}(X) = \mathbb{E}[(X - \mathbb{E}[X])^2] = \mathbb{E}[X^2] - (\mathbb{E}[X])^2

(22)

Properties:

\begin{align*} \operatorname{Var}(aX) &= a^2 \operatorname{Var}(X) \\ \operatorname{Var}(X + Y) &= \operatorname{Var}(X) + \operatorname{Var}(Y) + 2\operatorname{Cov}(X, Y) \\ \operatorname{Var}(X + c) &= \operatorname{Var}(X) \quad \text{for constant } c \end{align*}

(23)

Moment Generating Function (MGF)¶

\phi_X(t) = \mathbb{E}[e^{tX}] = \begin{cases} \sum_i e^{t x_i} P(X = x_i) & \text{for discrete } X \\ \int_{-\infty}^{\infty} e^{t x} f_X(x) \, dx & \text{for continuous } X \end{cases}

(24)

Important Property: The $n$ -th derivative at $t=0$ gives the $n$ -th moment:

\phi_X^{(n)}(0) = \mathbb{E}[X^n]

(25)

Taylor Expansion:

\phi_X(t) = \sum_{n=0}^{\infty} \frac{t^n}{n!} \mathbb{E}[X^n]

(26)

Important Discrete Distributions¶

Common Discrete Distributions

Distribution	PMF	Support	$\mathbb{E}[X]$	$\operatorname{Var}(X)$	MGF
Uniform	$P(X=k) = \frac{1}{n}$	$k \in \{1,2,\ldots,n\}$	$\frac{n+1}{2}$	$\frac{n^2-1}{12}$	$\frac{e^t(1-e^{nt})}{n(1-e^t)}$
Bernoulli	$P(X=k) = p^k(1-p)^{1-k}$	$k \in \{0,1\}$	$p$	$p(1-p)$	$pe^t + (1-p)$
Binomial	$P(X=k) = \binom{n}{k}p^k(1-p)^{n-k}$	$k \in \{0,1,\ldots,n\}$	$np$	$np(1-p)$	$(pe^t + 1-p)^n$
Geometric	$P(X=k) = (1-p)^{k-1}p$	$k \in \mathbb{N}$	$\frac{1}{p}$	$\frac{1-p}{p^2}$	$\frac{pe^t}{1-(1-p)e^t}$
Poisson	$P(X=k) = \frac{\lambda^k e^{-\lambda}}{k!}$	$k \in \mathbb{N}_0$	$\lambda$	$\lambda$	$e^{\lambda(e^t-1)}$

Bernoulli Distribution¶

Models a single yes/no experiment with success probability $p$ .

Example: Coin toss, single trial in an experiment.

Binomial Distribution¶

Models the number of successes in $n$ independent Bernoulli trials.

Geometric Distribution¶

Models the number of trials until the first success.

Example: Number of coin tosses until the first head appears.

Coupon Collector’s Problem¶

Problem: How many boxes must you buy to collect all $n$ different coupons?

Solution: Let $S_n = X_1 + X_2 + \ldots + X_n$ where $X_k \sim \text{Geom}\left(\frac{n-(k-1)}{n}\right)$ .

\mathbb{E}[S_n] = n \sum_{k=1}^n \frac{1}{k} = n H_n \approx n \ln(n) + \gamma n

(27)

where $H_n = \sum_{k=1}^n \frac{1}{k}$ is the $n$ -th harmonic number and $\gamma \approx 0.5772$ is the Euler-Mascheroni constant.

Important Continuous Distributions¶

Common Continuous Distributions

Distribution	PDF	Support	$\mathbb{E}[X]$	$\operatorname{Var}(X)$	MGF
Uniform	$f(x) = \frac{1}{b-a}$	$x \in [a,b]$	$\frac{a+b}{2}$	$\frac{(b-a)^2}{12}$	$\frac{e^{tb} - e^{ta}}{t(b-a)}$
Exponential	$f(x) = \lambda e^{-\lambda x}$	$x \geq 0$	$\frac{1}{\lambda}$	$\frac{1}{\lambda^2}$	$\frac{\lambda}{\lambda - t}$
Normal	$f(x) = \frac{1}{\sqrt{2\pi\sigma^2}} e^{-\frac{(x-\mu)^2}{2\sigma^2}}$	$x \in \mathbb{R}$	$\mu$	$\sigma^2$	$e^{t\mu + \frac{1}{2}t^2\sigma^2}$
Cauchy	$f(x) = \frac{1}{\pi} \frac{1}{1+x^2}$	$x \in \mathbb{R}$	Undefined	Undefined	Undefined

Exponential Distribution¶

Memoryless Property: For $X \sim \text{Exp}(\lambda)$ :

P(X > s + t | X > t) = P(X > s) = e^{-\lambda s}

(28)

Interpretation: The probability of surviving an additional $s$ units of time is independent of how long the component has already survived.

Normal Distribution¶

Standard Normal: $Z \sim N(0,1)$ with CDF $\Phi(z) = P(Z \leq z)$ .

Standardization: If $X \sim N(\mu, \sigma^2)$ , then:

Z = \frac{X - \mu}{\sigma} \sim N(0,1)

(29)

Probability Calculation:

P(X \leq t) = \Phi\left(\frac{t - \mu}{\sigma}\right)

(30)

Symmetric Properties:

\Phi(-z) = 1 - \Phi(z) \quad \text{and} \quad \Phi(0) = 0.5

(31)

Cauchy Distribution¶

Used to model spikes or peaks in large datasets (rare events).

Note: Mean and variance are undefined due to heavy tails.

Joint Distributions & Independence¶

Joint Distribution Function¶

For two RVs $X, Y$ :

F_{X,Y}(a,b) = P(X \leq a, Y \leq b)

(32)

Marginal Distributions:

F_X(a) = \lim_{b\to\infty} F_{X,Y}(a,b)

(33)

Joint PMF/PDF¶

Discrete:

p_{X,Y}(x,y) = P(X = x, Y = y)

(34)

Continuous:

f_{X,Y}(x,y) \quad \text{such that } \int\int_{A} f_{X,Y}(x,y) \, dx \, dy = P((X,Y) \in A)

(35)

Marginal PDF:

f_X(x) = \int_{-\infty}^{\infty} f_{X,Y}(x,y) \, dy

(36)

Independence of Random Variables¶

$X$ and $Y$ are independent if one of the following is true:

\begin{aligned} F_{X,Y}(a,b) &= F_X(a) F_Y(b) \quad \forall a,b \\ f_{X,Y}(x,y) &= f_X(x)f_Y(y) \quad \text{, (continous RV)} \\ P(X=x, Y=y) &= P(X=x)P(Y=y) \quad \text{, (discrete RV)} \end{aligned}

(37)

Consequences of Independence:

\begin{align*} \mathbb{E}[XY] &= \mathbb{E}[X]\mathbb{E}[Y] \\ \operatorname{Cov}(X,Y) &= 0 \\ \operatorname{Var}(X+Y) &= \operatorname{Var}(X) + \operatorname{Var}(Y) \\ \phi_{X+Y}(t) &= \phi_X(t) \phi_Y(t) \end{align*}

(38)

Covariance & Correlation¶

Covariance:

\operatorname{Cov}(X,Y) = \mathbb{E}[(X - \mathbb{E}[X])(Y - \mathbb{E}[Y])] = \mathbb{E}[XY] - \mathbb{E}[X]\mathbb{E}[Y]

(39)

Correlation:

\rho_{X,Y} = \frac{\operatorname{Cov}(X,Y)}{\sqrt{\operatorname{Var}(X)\operatorname{Var}(Y)}} \quad \in [-1, 1]

(40)

Properties:

\begin{align*} \operatorname{Cov}(X,X) &= \operatorname{Var}(X) \\ \operatorname{Cov}(X,Y) &= \operatorname{Cov}(Y,X) \\ \operatorname{Cov}(aX + b, cY + d) &= ac \operatorname{Cov}(X,Y) \\ \operatorname{Cov}(X + Y, Z) &= \operatorname{Cov}(X,Z) + \operatorname{Cov}(Y,Z) \\ \operatorname{Cov}(X, Y + Z) &= \operatorname{Cov}(X,Y) + \operatorname{Cov}(X,Z) \\ \operatorname{Var}(X + Y) &= \operatorname{Var}(X) + \operatorname{Var}(Y) + 2\operatorname{Cov}(X,Y) \end{align*}

(41)

Conditional Distributions & Expectation¶

Conditional PMF/PDF¶

Discrete:

P_{X|Y}(x|y) = P(X = x | Y = y) = \frac{P(X = x, Y = y)}{P(Y = y)}

(42)

Continuous:

f_{X|Y}(x|y) = \frac{f_{X,Y}(x,y)}{f_Y(y)}

(43)

Conditional Expectation¶

Discrete:

\mathbb{E}[X|Y = y] = \sum_x x P_{X|Y}(x|y)

(44)

Continuous:

\mathbb{E}[X|Y = y] = \int_{-\infty}^{\infty} x f_{X|Y}(x|y) \, dx

(45)

Important: $\mathbb{E}[X|Y]$ is itself a random variable (function of $Y$ ).

Law of Total Expectation¶

\mathbb{E}[X] = \mathbb{E}[\mathbb{E}[X|Y]]

(46)

For discrete $Y$ :

\mathbb{E}[X] = \sum_y \mathbb{E}[X|Y = y] P(Y = y)

(47)

For continuous $Y$ :

\mathbb{E}[X] = \int_{-\infty}^{\infty} \mathbb{E}[X|Y = y] f_Y(y) \, dy

(48)

Conditional Variance¶

\operatorname{Var}(X|Y = y) = \mathbb{E}[X^2|Y = y] - (\mathbb{E}[X|Y = y])^2

(49)

Law of Total Variance:

\operatorname{Var}(X) = \mathbb{E}[\operatorname{Var}(X|Y)] + \operatorname{Var}(\mathbb{E}[X|Y])

(50)

Mean Squared Error (MSE) Minimization¶

Proof: Follows from the orthogonality principle in Hilbert spaces.

Transformation of Random Variables¶

General Transformation Formula¶

For a continuous RV $X$ with density $f_X(x)$ and a differentiable, strictly monotone function $g$ :

Y = g(X) \implies f_Y(y) = f_X(g^{-1}(y)) \cdot \left| \frac{d}{dy} g^{-1}(y) \right| = \frac{f_X(g^{-1}(y))}{|g'(g^{-1}(y))|}

(51)

Validity: Only for $y$ in the range of $g$ ; $f_Y(y) = 0$ outside this range.

Example: Exponential Transformation¶

If $X \sim \text{Unif}([0,1])$ and $Y = e^X$ :

Y \sim \text{Exp}(1) \text{ on } [1, e] \quad \text{with } f_Y(y) = \frac{1}{y} \text{ for } y \in [1, e]

(52)

Verification: $\int_1^e \frac{1}{y} \, dy = \ln(e) - \ln(1) = 1$ .

Multiple Variables¶

For $Y_1 = g_1(X_1, X_2)$ and $Y_2 = g_2(X_1, X_2)$ with invertible transformation:

f_{Y_1,Y_2}(y_1,y_2) = f_{X_1,X_2}(g_1^{-1}(y_1,y_2), g_2^{-1}(y_1,y_2)) \cdot |J|

(53)

where $|J|$ is the absolute value of the Jacobian determinant.

Limit Theorems¶

Law of Large Numbers (LLN)¶

Weak LLN: For i.i.d. RVs $X_1, X_2, \ldots$ with $\mathbb{E}[X_i] = \mu$ and $\operatorname{Var}(X_i) = \sigma^2 < \infty$ :

\frac{S_n}{n} = \frac{X_1 + X_2 + \ldots + X_n}{n} \xrightarrow{P} \mu \quad \text{as } n \to \infty

(54)

Strong LLN: Under the same conditions (with finite mean):

P\left(\lim_{n\to\infty} \frac{S_n}{n} = \mu\right) = 1 \quad \text{(almost sure convergence)}

(55)

Interpretation: The sample mean converges to the true mean as $n \to \infty$ .

Central Limit Theorem (CLT)¶

For i.i.d. RVs $X_1, X_2, \ldots$ with $\mathbb{E}[X_i] = \mu$ and $\operatorname{Var}(X_i) = \sigma^2 < \infty$ :

Z = \frac{S_n - \mu}{\sigma} \xrightarrow{d} N(0,1) \quad \text{as } n \to \infty

(56)

Chebyshev’s Inequality¶

For any RV $X$ with $\mathbb{E}[X] = \mu$ and $\operatorname{Var}(X) = \sigma^2$ :

P(|X - \mu| \geq \varepsilon) \leq \frac{\sigma^2}{\varepsilon^2} \quad \forall \varepsilon > 0

(57)

Application: Provides a bound on the probability of deviation from the mean.

Example: For $S_n \sim \text{Bin}(n,p)$ :

P(|S_n - np| \geq \varepsilon) \leq \frac{np(1-p)}{\varepsilon^2}

(58)

Markov’s Inequality¶

For any non-negative RV $X$ :

P(X \geq a) \leq \frac{\mathbb{E}[X]}{a} \quad \forall a > 0

(59)

Stochastic Processes¶

Definition¶

A stochastic process is a collection of RVs $X = \{X_t: t \in T\}$ where $T$ is an index set (usually time).

Representation:

X: T \times \Omega \to \mathbb{R} \quad \text{via } (t, \omega) \mapsto X_t(\omega)

(60)

Characterization¶

A stochastic process is characterized by its finite-dimensional distributions:

F_{X_{t_1}, \ldots, X_{t_k}}(x_1, \ldots, x_k) = P(X_{t_1} \leq x_1, \ldots, X_{t_k} \leq x_k)

(61)

for all $k \geq 1$ and $t_1 < t_2 < \ldots < t_k$ .

Mean & Correlation Functions¶

Mean Function:

m_X(t) = \mathbb{E}[X_t]

(62)

Correlation Function:

R_X(t_1, t_2) = \mathbb{E}[X_{t_1} X_{t_2}] = \frac{\operatorname{Cov}(X_{t1},X_{t2})}{\sqrt{\operatorname{Var}(X_{t1})\operatorname{Var}(X_{t2})}} \begin{cases} t_1 = t_2 \\ t_1 \neq t_2 \end{cases}

(63)

Covariance Function:

C_X(t_1, t_2) = R_X(t_1, t_2) - m_X(t_1) m_X(t_2)

(64)

Stationary Processes¶

Definition: A process is stationary if its finite-dimensional distributions are invariant under time shifts:

(X_{t_1}, \ldots, X_{t_k}) \stackrel{d}{=} (X_{t_1+s}, \ldots, X_{t_k+s}) \quad \forall s

(65)

Wide-Sense Stationary (WSS):

Constant mean: $m_X(t) = m$ for all $t$
Correlation depends only on time difference: $R_X(t_1, t_2) = R_X(|t_2 - t_1|)$

Examples of Stochastic Processes¶

Process	Description	Mean	Variance	Correlation
Bernoulli	$X_n$ i.i.d. $\pm 1$ valued	$2p-1$	$4p(1-p)$	$(2p-1)^2$ for $t_1\neq t_2$
Random Walk	$X_n = \sum_{i=1}^n B_i$	0 (if $p=1/2$ )	$n$	$\min(t_1, t_2)$
Brownian Motion	Continuous limit of RW	0	$t$	$\min(t_1, t_2)$
Poisson	Counts events in time	$\lambda t$	$\lambda t$	$\lambda \min(t_1, t_2)$

Bernoulli Process¶

$X_n$ i.i.d. with $P(X_n = 1) = p$ and $P(X_n = -1) = 1-p$ .

Random Walk (RW)¶

$X_0 = 0$ , $X_n = X_{n-1} + B_n$ where $B_n$ i.i.d. $\pm 1$ valued.

Symmetric RW: $p = 1/2$
Recurrence: In $d=1,2$ , RW is recurrent (returns to origin infinitely often) with probability 1
Transience: In $d \geq 3$ , RW is transient (never returns to origin) with probability 1

CLT for RW:

\frac{X_n}{\sqrt{n}} \xrightarrow{d} N(0,1) \quad \text{for symmetric RW}

(66)

Brownian Motion (BM)¶

Models particle movement in a liquid (Einstein, 1905)
Models stock market fluctuations (Bachelier, 1900)
Continuous paths, nowhere differentiable
$B_t \sim N(0,t)$ for each $t$
Independent increments

Connection to RW: Scaled limit of symmetric RW as step size $\to 0$ and time $\to \infty$ .

Poisson Process¶

$N_t$ counts the number of events in $[0,t]$ for a process with:

$N_0 = 0$
Independent increments
$N_{s+t} - N_s \sim \text{Pois}(\lambda t)$

Properties:

$\mathbb{E}[N_t] = \lambda t$
$\operatorname{Var}(N_t) = \lambda t$
$C_N(t_1, t_2) = \lambda \min(t_1, t_2)$
Inter-arrival times $T_i \sim \text{Exp}(\lambda)$ and independent

Thinning Property: If each event is kept with probability $p$ , the thinned process is $\text{PP}(p\lambda)$ .

Merging Property: Sum of independent $\text{PP}(\lambda_1)$ and $\text{PP}(\lambda_2)$ is $\text{PP}(\lambda_1 + \lambda_2)$ .

Random Telegraph Process¶

$X_t = (-1)^{N_t}$ where $N_t$ is a Poisson process.

Mean: $\mathbb{E}[X_t] = e^{-2\lambda t}$

Correlation: $R_X(t_1, t_2) = e^{-2\lambda |t_2 - t_1|}$

Markov Chains¶

Definition¶

A Markov Chain (MC) is a discrete-time stochastic process with the Markov Property:

P(X_{n+1} = x_{n+1} | X_n = x_n, X_{n-1} = x_{n-1}, \ldots, X_0 = x_0) = P(X_{n+1} = x_{n+1} | X_n = x_n)

(67)

Interpretation: Given the present, the future is independent of the past.

Transition Probabilities¶

One-step:

p_{ij} = P(X_{n+1} = j | X_n = i)

(68)

Transition Matrix:

P = \begin{pmatrix} p_{11} & p_{12} & \cdots & p_{1k} \\ p_{21} & p_{22} & \cdots & p_{2k} \\ \vdots & \vdots & \ddots & \vdots \\ p_{k1} & p_{k2} & \cdots & p_{kk} \end{pmatrix}

(69)

Properties: $p_{ij} \geq 0$ and $\sum_j p_{ij} = 1$ for all $i$ (stochastic matrix).

m-step:

p_{ij}^{(m)} = P(X_{n+m} = j | X_n = i)

(70)

Chapman-Kolmogorov Equations:

p_{ij}^{(m+n)} = \sum_{k \in S} p_{ik}^{(m)} p_{kj}^{(n)}

(71)

Matrix Form: $P^{(m+n)} = P^m P^n$ and $P^{(m)} = P^m$ .

Classification of States¶

Accessible: $i \to j$ if $p_{ij}^{(n)} > 0$ for some $n \geq 0$
Communicating: $i \leftrightarrow j$ if $i \to j$ and $j \to i$
Communication Classes: Equivalence classes under $\leftrightarrow$
Irreducible: All states communicate (single communication class)
Period: $d_i = \gcd\{n \geq 1: p_{ii}^{(n)} > 0\}$
Aperiodic: $d_i = 1$ for all $i$

Stationary Distributions¶

A probability vector $\vec{\pi} = (\pi_1, \pi_2, \ldots)$ is a stationary distribution if:

\vec{\pi} = \vec{\pi} P \quad \text{and} \quad \sum_i \pi_i = 1, \pi_i \geq 0

(72)

Interpretation: If $X_0 \sim \vec{\pi}$ , then $X_n \sim \vec{\pi}$ for all $n$ .

Existence:

Finite state space + irreducible $\Rightarrow$ unique stationary distribution
Finite state space + irreducible + aperiodic $\Rightarrow$ unique stationary distribution and convergence

Convergence¶

Corollary: Every row of $P^n$ converges to $\vec{\pi}$ as $n \to \infty$ .

PageRank Algorithm¶

Problem: Rank web pages based on link structure.

Model: Random surfer model with:

Follows links with probability $\alpha \approx 0.85$
Teleports to random page with probability $1-\alpha$

Google Matrix:

G = \alpha S + (1-\alpha) \frac{1}{n} \vec{e} \vec{e}^T

(73)

where $S$ is the stochastic matrix from the web graph (with fixes for dangling nodes).

Properties:

$G$ is irreducible and aperiodic (since $G > 0$ )
Converges to unique stationary distribution (PageRank vector)

Dangling Nodes: Pages without outlinks. Solution: Add uniform row.

Rank Sinks: Groups of pages that trap the random surfer. Solution: Use teleportation.

Continuous-Time Markov Chains¶

Holding Times¶

For a continuous-time MC, the time spent in state $i$ before jumping:

Memoryless: $P(T_i > s + t | T_i > t) = P(T_i > s)$
Distribution: $T_i \sim \text{Exp}(\nu_i)$ for some $\nu_i > 0$

Poisson Process (Special Case)¶

A counting process $N_t$ is a Poisson Process with rate $\lambda > 0$ if:

$N_0 = 0$
Independent increments
$N_{s+t} - N_s \sim \text{Pois}(\lambda t)$

Key Properties:

$N_t \sim \text{Pois}(\lambda t)$
$\mathbb{E}[N_t] = \lambda t$
$\operatorname{Var}(N_t) = \lambda t$
Inter-arrival times $T_i \sim \text{Exp}(\lambda)$ and independent

Construction: If $T_i \sim \text{Exp}(\lambda)$ i.i.d., then $N_t = \max\{n: \sum_{i=1}^n T_i \leq t\}$ is a Poisson process.

Important Examples from Exercises¶

Conditional Probability Examples¶

Example 1: Two dice, sum equals 6 vs. first die equals 4

$E_1$ : sum equals 6, $P(E_1) = \frac{5}{36}$
$E_3$ : first die equals 4, $P(E_3) = \frac{1}{6}$
$P(E_1 | E_3) = \frac{1}{6} > P(E_1)$ (dependent!)
$P(E_2 | E_3) = \frac{1}{6} = P(E_2)$ (independent!)

Example 2: Lottery probabilities

Probability of winning with 6 out of 48: $P = \frac{1}{\binom{48}{6}} \approx 1.2 \times 10^{-7}$
Probability that at least one of $H$ participants wins: $1 - \left(1 - \frac{1}{\binom{48}{6}}\right)^H$

Conditional Expectation Examples¶

Exercise from Week 8: Given joint density $f_{X,Y}(x,y) = 6xy(2-x-y)$ for $0 < x,y < 1$ :

\mathbb{E}[X|Y=y] = \frac{5 - 4y}{2(4 - 3y)} \quad \text{for } 0 < y < 1

(74)

Variance Calculation¶

Exercise from Week 8: For $f_{X,Y}(x,y) = \frac{1}{18} e^{-(x+y)}$ for $0 < y < x$ :

\operatorname{Var}(X|Y=2) = 36

(75)

Geometric Distribution Proof¶

Exercise from Week 8: If $X \sim \text{Pois}(Y)$ and $Y \sim \text{Exp}(\lambda)$ , then $W = X + 1 \sim \text{Geom}\left(\frac{\lambda}{\lambda+1}\right)$ .

Markov Chain Examples¶

Example: Gambler’s Ruin

States: $\{0, 1, 2, 3\}$ (0 and 3 are absorbing)
Communication classes: $\{0\}, \{1,2\}, \{3\}$
Not irreducible (multiple classes)

Example: Simple Two-State Chain

States: $\{1, 2\}$
Transition matrix: $P = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$
Stationary distribution: $\vec{\pi} = (1/2, 1/2)$
Periodic with period 2

Poisson Process Examples¶

Example: Machine failures with rate $\lambda = 2$ per week.

$P(\text{no failure in 2 weeks}) = e^{-4}$
$P(\text{at most 1 failure in 2 weeks}) = e^{-4} + 4e^{-4} = 5e^{-4}$
$P(\text{inter-arrival > 5 weeks}) = e^{-10}$