Stochastic Modeling

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:

Key Properties¶

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$:

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$:

Simplified (for binary partition):

Bayes’ Theorem¶

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¶

Probability Mass Function (PMF)¶

For discrete RV $X$:

Probability Density Function (PDF)¶

For continuous RV $X$:

Distribution Function (CDF)¶

For any RV $X$:

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)¶

Linearity of Expectation:

Important: Linearity holds regardless of independence.

Variance¶

Properties:

Moment Generating Function (MGF)¶

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

Taylor Expansion:

Discrete Distributions¶

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)$.

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.

Continuous Distributions¶

Exponential Distribution¶

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

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 standard normal CDF $F_X(z) = \Phi(z) = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^z e^{-t^2/2} \, dt$

• Standardization: If $X \sim N(\mu, \sigma^2)$, then $Z = \frac{X - \mu}{\sigma} \sim N(0,1)$

• Probability Calculation: $P(X \leq t) = \Phi\left(\frac{t - \mu}{\sigma}\right)$

• Symmetric Properties: $\Phi(-z) = 1 - \Phi(z) \quad \text{and} \quad \Phi(0) = 0.5$

Joint Distributions & Independence¶

Joint Distribution Function¶

For two RVs $X, Y$:

Marginal Distributions:

Joint PMF/PDF¶

Discrete:

Continuous:

Marginal PDF:

Independence of Random Variables¶

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

Consequences of Independence:

Covariance & Correlation¶

Covariance:

Correlation Coefficient (normalized Covariance):

Properties:

Conditional Distributions & Expectation¶

Conditional PMF/PDF¶

Discrete:

Continuous:

Conditional Expectation¶

Discrete:

Continuous:

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

Law of Total Expectation¶

For discrete $Y$:

For continuous $Y$:

Conditional Variance¶

Law of Total Variance:

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$:

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$:

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:

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$:

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

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$:

Chebyshev’s Inequality¶

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

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

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

Markov’s Inequality¶

For any non-negative RV $X$:

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:

Characterization¶

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

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

Mean & Correlation Functions¶

Mean Function

Correlation Function

Zero-mean processes: $R_X(t_1, t_2) = \operatorname{Cov}(X_{t_1}, X_{t_2})$

Covariance Function

Stationary Processes¶

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

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¶

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:

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:

1. $N_0 = 0$

2. Independent increments

3. $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:

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

Transition Probabilities¶

One-step:

Transition Matrix:

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

m-step:

Chapman-Kolmogorov Equations:

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:

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:

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:

1. $N_0 = 0$

2. Independent increments

3. $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$:

Variance Calculation¶

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

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}$