DTMC Transitions Slides Foundations of Discrete-Time Markov Chains
A stochastic process \(\{X_n, n \in \mathbb{N}\}\) is a **Markov Chain** if for any \(n \in \mathbb{N}\) and any states \(i_0, i_1, \dots, i, j \in S\):
\[P(X_{n+1} = j | X_n = i, X_{n-1} = i_{n-1}, \dots, X_0 = i_0)\] \[= P(X_{n+1} = j | X_n = i)\]
"The future is independent of the past, given the present."
Visualizing state transitions as a directed graph where nodes are states and edges represent non-zero probabilities.
Transition Probability Matrix (\(P\))
For a time-homogeneous chain, the transition probability is independent of \(n\):
\(p_{ij} = P(X_{n+1} = j | X_n = i)\)
Properties of Matrix \(P\):
\(p_{ij} \geq 0\) for all \(i, j\)
\(\sum_{j \in S} p_{ij} = 1\) (Stochastic Matrix)
Rows sum to 1; Columns do not necessarily sum to 1.
Matrix Notation
Let \(S = \{1, 2, \dots, N\}\):
\[P = \begin{pmatrix} p_{11} & p_{12} & \dots \\ p_{21} & p_{22} & \dots \\ \vdots & \vdots & \ddots \end{pmatrix}\]
Transitioning from row (from) to column (to).
Chapman-Kolmogorov Equations
\(p_{ij}^{(n+m)} = \sum_{k \in S} p_{ik}^{(n)} p_{kj}^{(m)}\)
Implication for Computation
The \(n\)-step transition probability matrix \(P^{(n)}\) is simply the \(n\)-th power of the one-step transition matrix \(P\):
\(P^{(n)} = P \times P \times \dots \times P = P^n\)
This allows us to calculate probabilities of reaching state \(j\) from state \(i\) in exactly \(n\) steps using standard matrix multiplication.
Theorem Note
The proof relies on the law of total probability, conditioning on the intermediate state at time \(n\).
Case Study: The Gambler's Ruin
A gambler starts with \(i\) dollars and plays until they have \(0\) (ruin) or \(N\) dollars (win).
1 Transitions: \(i \to i+1\) with prob \(p\), \(i \to i-1\) with prob \(q=1-p\).
2 Boundary conditions: States \(0\) and \(N\) are **absorbing** (\(p_{00}=1, p_{NN}=1\)).
3 Goal: Find \(P(\text{Ruin} | X_0 = i)\).
Discussion Question
How does the "fairness" of the coin (\(p=0.5\)) vs. a slight disadvantage (\(p=0.48\)) change the probability of ruin as \(N \to \infty\)?
Key Takeaway: Intuitive linear expectations often break in recursive stochastic systems.
DTMC Transitions Facilitator Guide Facilitator Protocol
PROT-STOCH-001
Lesson 1: DTMC & Transition Probabilities
Instructional Context
This lesson initiates the graduate sequence on stochastic processes. Students at this level should have a firm grasp of undergraduate probability (conditional probability, law of total probability) and linear algebra (matrix multiplication).
Key Proof to Highlight
The derivation of \(P^{(n+m)} = P^{(n)}P^{(m)}\). Emphasize how the Markov property simplifies the conditional expectation at time \(n\).
Common Pitfall
Confusing the row/column orientation of transition matrices. Standard convention is row-to-column (\(p_{ij}\) is transition from \(i\) to \(j\)).
Facilitation Prompts
Opening Hook: The Gambler's Ruin
"If you have $10 and play a fair game against a casino with infinite wealth, what is your probability of ruin? Now, what if the casino only has $1,000?"
Goal: Prime students for recursive thinking and the concept of absorbing states.
Technical Deep-Dive: Memorylessness
"In what real-world scenarios does the Markov property fail? How would we model a system where the transition probability depends on the duration of stay in the current state?"
Goal: Bridge toward non-Markovian processes and hidden Markov models (HMMs).
Lesson Delivery Tips
Matrix Powers: Use computational tools (Python/R) to show how \(P^n\) behaves as \(n\) increases. This provides an organic transition to Lesson 2 (Stationarity).State Diagrams: Always draw the transition graph for 2 or 3-state systems before writing the matrix. It grounds the abstraction.Graduate Rigor: Ensure the difference between "Discrete-Time" and the discrete nature of the "State Space" is clear. A process can have a continuous state space in discrete time.
Key Solution: Gambler's Ruin
Let \(q_i = P(\text{ruin} | X_0 = i)\). Recurrence relation:
\(q_i = p \cdot q_{i+1} + q \cdot q_{i-1}\)
Boundary: \(q_0 = 1, q_N = 0\)
General Solution: \(q_i = \frac{(q/p)^i - (q/p)^N}{1 - (q/p)^N}\) for \(p \neq 0.5\).
DTMC Transitions Worksheet Transitions Problem Set
Stochastic Processes | Graduate Module 01
Name: _____________________
Date: _____________________
Focus: Constructing transition matrices, verifying the Markov property, and applying Chapman-Kolmogorov for multi-step predictions.
1 System Modeling
Consider a simple weather model with three states: \(S = \{1: \text{Sunny}, 2: \text{Cloudy}, 3: \text{Rainy}\}\). The probability of a sunny day following a sunny day is 0.7; a rainy day never follows a sunny day. If it is cloudy, there is a 50% chance the next day will be sunny and a 20% chance it will be rainy. If it is rainy, there is a 50% chance the next day will still be rainy and a 40% chance it will be cloudy.
A) Construct the one-step transition probability matrix \(P\).
Write Matrix P here
B) Draw the transition diagram for this process.
2 Multi-Step Transitions
Using the matrix \(P\) from Problem 1, calculate the probability that it will be Sunny two days from now, given that today is Rainy.
Show your derivation using the Chapman-Kolmogorov equations \(p_{ij}^{(2)} = \sum_{k} p_{ik} p_{kj}\).
3 Formal Proof
Prove that if \(P\) is a stochastic matrix (all rows sum to 1), then \(P^n\) is also a stochastic matrix for all \(n \geq 1\).
Classification Stationarity Slides The Long Run
State Classification and Stationary Distributions
Classification
Are we guaranteed to return? Recurrence vs. Transience.
Stationarity
Does the system reach an equilibrium state \(\pi\)?
Ergodicity
When do time averages equal ensemble averages?
Classifying the State Space
Recurrence
\(P(\text{return to } i | X_0 = i) = 1\)
Positive Recurrent: Finite expected return time.
Null Recurrent: Infinite expected return time.
Transience
\(P(\text{return to } i | X_0 = i) < 1\)
The system eventually leaves the state and never returns.
Communicating Classes
States \(i\) and \(j\) communicate (\(i \leftrightarrow j\)) if they are reachable from each other.
Irreducible: All states communicate.
Stationary Distribution (\(\pi\))
A probability distribution \(\pi\) is **stationary** if:
\[\pi P = \pi\]
Subject to: \(\sum_i \pi_i = 1\)
Theorem: For an irreducible, aperiodic, positive recurrent DTMC, a unique stationary distribution exists and \(\lim_{n \to \infty} P_{ij}^n = \pi_j\).
The PageRank Hook
The internet is a massive Markov chain. Google's PageRank is simply the **stationary distribution** of a random surfer clicking links with an occasional "teleport" probability.
Detailed Balance & Reversibility
A Markov chain is **reversible** if there exists a distribution \(\pi\) such that:
\[\pi_i p_{ij} = \pi_j p_{ji}\]
If detailed balance holds, \(\pi\) is guaranteed to be a stationary distribution.
This is a sufficient but not necessary condition for stationarity.
Classification Stationarity Facilitator Guide Facilitator Protocol
PROT-STOCH-002
Lesson 2: Classification & Stationarity
Instructional Context
This lesson pivots from short-term transitions to long-term asymptotic behavior. The transition from \(\pi P = \pi\) to a system of linear equations is the primary technical hurdle.
Key Concept
Ergodicity: A chain that is irreducible, positive recurrent, and aperiodic.
Mathematical Link
\(\pi\) is the left eigenvector of \(P\) associated with eigenvalue \(\lambda = 1\).
PageRank Deep Dive
Explain the Google Matrix \(G\): \[G = \alpha P + (1-\alpha) \frac{1}{N} E\] where \(E\) is a matrix of all ones.
\(\alpha\) (damping factor) is usually \(\approx 0.85\).
The term \((1-\alpha)\frac{1}{N}E\) ensures the chain is **irreducible** and **aperiodic**, guaranteeing a unique stationary distribution even if the web graph has "dead ends" or cycles.
Facilitation Prompts
Prompt: The Gambler Re-visited
"In the Gambler's Ruin, are there any stationary distributions? What happens if the gambler has an infinite line of credit?"
Prompt: Detailed Balance
"If a chain is reversible, what does that imply about the energy flow in a physical system? (Think thermodynamics and micro-reversibility)."
Worksheet Key: Stationarity
For a 2-state system \(P = \begin{pmatrix} 1-a & a \\ b & 1-b \end{pmatrix}\):
\(\pi_1(1-a) + \pi_2 b = \pi_1 \implies \pi_1 a = \pi_2 b\)
\(\pi_1 + \pi_2 = 1 \implies \pi_1 + \pi_1 \frac{a}{b} = 1\)
Result: \(\pi_1 = \frac{b}{a+b}, \pi_2 = \frac{a}{a+b}\)
Classification Stationarity Worksheet Asymptotic Analysis
Stochastic Processes | Graduate Module 02
Name: _____________________
Date: _____________________
1 State Classification
Identify the communicating classes for the Markov chain defined by the following transition matrix \(P\). For each class, specify if it is recurrent or transient , and determine the period of each state.
\[P = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 0.5 & 0 & 0.5 & 0 \\ 0 & 0 & 1 & 0 \\ 0.5 & 0 & 0 & 0.5 \end{pmatrix}\]
A) Communicating Classes:
B) Class Properties (Recurrence/Period):
2 Stationary Distribution
Consider a 3-state social mobility model where states represent economic classes: 1 (Lower), 2 (Middle), and 3 (Upper). The transition matrix is:
\[P = \begin{pmatrix} 0.6 & 0.3 & 0.1 \\ 0.2 & 0.5 & 0.3 \\ 0.1 & 0.4 & 0.5 \end{pmatrix}\]
Calculate the stationary distribution \(\pi = (\pi_1, \pi_2, \pi_3)\) for this system. Show all steps of the linear system solution.
3 Detailed Balance and Reversibility
A Markov chain with transition matrix \(P\) and stationary distribution \(\pi\) is reversible if \(\pi_i p_{ij} = \pi_j p_{ji}\) for all \(i, j\).
Prove that for any birth-death process (a process where \(p_{ij} = 0\) if \(|i-j| > 1\)), the stationary distribution must satisfy the detailed balance equations, and thus all birth-death processes are reversible.
Poisson Processes Slides The Continuum
Lesson 3: Poisson Processes and Continuous Modeling
Continuous Time
Counting Processes
Defining the Poisson Process
Counting Axioms
\(N(0) = 0\)
Stationary and Independent Increments.
\(P(N(h) = 1) = \lambda h + o(h)\)
\(P(N(h) \geq 2) = o(h)\)
"The number of events in an interval of length \(t\) follows a Poisson distribution with parameter \(\lambda t\)."
\[P(N(t) = k) = \frac{e^{-\lambda t}(\lambda t)^k}{k!}\]
Times Between Events
Exponential Link
If \(\{N(t), t \geq 0\}\) is a Poisson process, the inter-arrival times \(T_n\) are IID Exponential random variables with mean \(1/\lambda\).
The Memoryless Property
\(P(T > t+s | T > s) = P(T > t)\)
The time you've already waited tells you nothing about how much longer you'll wait.
Arrival Paradox
If buses arrive as a Poisson process every 10 mins, why is your expected wait time still 10 mins even if you arrive at a random time?
Process Operations
Superposition
The sum of two independent Poisson processes with rates \(\lambda_1\) and \(\lambda_2\) is a Poisson process with rate \(\lambda_1 + \lambda_2\).
\(\lambda_{sum} = \lambda_1 + \lambda_2\)
Thinning
If events are "kept" with probability \(p\), the resulting process is Poisson with rate \(\lambda p\).
\(\lambda_{new} = \lambda p\)
Poisson Processes Facilitator Guide Facilitator Protocol
PROT-STOCH-003
Lesson 3: Poisson Processes & Continuity
Instructional Context
This lesson marks the transition from discrete "jumps" at fixed time intervals to processes occurring in continuous time. The limit approach is crucial.
Technical Note: Little-o Notation
Remind students that \(f(h) = o(h)\) means \(\lim_{h \to 0} \frac{f(h)}{h} = 0\). This is essential for the axiomatic definition, as it handles the probability of two events occurring "simultaneously."
The Inspection Paradox
This is a common source of confusion. If the mean inter-arrival time is \(1/\lambda\), why is the expected wait time for a random arrival also \(1/\lambda\)?
Step 1: Memorylessness says the time until the next event is independent of the time since the last event.
Step 2: Therefore, regardless of when you arrive, you are starting a "new" exponential wait.
Step 3: Intuition gap: You are more likely to arrive during a longer inter-arrival interval than a shorter one.
Logic of Thinning
"If arrivals at a hospital follow a Poisson process (\(\lambda\)), and 20% of patients require emergency care, do emergency arrivals form a Poisson process?"
Yes. Thinning is the mathematical equivalent of Bernoulli trials on a Poisson process. It demonstrates how independence at the event level preserves the Poisson structure.
Proof Focus: \(T_1 \sim \text{Exp}(\lambda)\)
\(P(T_1 > t) = P(\text{No events in } [0,t])\)
\(P(N(t)=0) = \frac{e^{-\lambda t}(\lambda t)^0}{0!} = e^{-\lambda t}\)
The CDF \(F_{T_1}(t) = 1 - e^{-\lambda t}\), which is the CDF of \(\text{Exp}(\lambda)\).
Poisson Processes Worksheet Event Arrivals
Stochastic Processes | Graduate Module 03
Name: _____________________
Date: _____________________
1 Counting and Inter-arrival Times
Requests arrive at a server according to a Poisson process with rate \(\lambda = 5\) requests per minute.
A) What is the probability that exactly 3 requests arrive in a 1-minute interval?
B) What is the probability that the time between the first and second request is greater than 30 seconds?
2 Superposition and Selection
A support desk receives two types of calls: Technical Support (\(\lambda_T = 4/\text{hr}\)) and Billing Support (\(\lambda_B = 2/\text{hr}\)). Both arrival processes are independent Poisson processes.
A) What is the probability that exactly 10 calls (of any type) arrive in an 8-hour shift?
B) Given that a call has just arrived, what is the probability it is a Billing Support call?
3 Thinning Proof
Let \(\{N(t), t \geq 0\}\) be a Poisson process with rate \(\lambda\). Suppose each event is classified as Type I with probability \(p\) and Type II with probability \(1-p\), independently of all other events.
Using the law of total probability, prove that the process of Type I events, \(\{N_1(t), t \geq 0\}\), is a Poisson process with rate \(\lambda p\).
CTMC Generator Slides The Generator
Lesson 4: Continuous-Time Markov Chains (CTMC)
Rates of Change
Jump Processes
Infinitesimal Generator \(Q\)
In discrete time, we used probabilities \(P\). In continuous time, we use **rates** \(Q\).
Formal Definition
\(q_{ij} = \lim_{h \to 0} \frac{P_{ij}(h)}{h}\) for \(i \neq j\)
\(q_{ii} = \lim_{h \to 0} \frac{P_{ii}(h) - 1}{h} = -\sum_{j \neq i} q_{ij}\)
The Q-Matrix Structure
\[Q = \begin{pmatrix} -q_1 & q_{12} & q_{13} \\ q_{21} & -q_2 & q_{23} \\ q_{31} & q_{32} & -q_3 \end{pmatrix}\]
Rows always sum to zero.
Kolmogorov Equations
How do transition probabilities evolve over time \(t\)?
Forward Equation
Conditioning on the last step.
\[P'(t) = P(t)Q\]
Backward Equation
Conditioning on the first step.
\[P'(t) = QP(t)\]
"Solution: \(P(t) = e^{Qt}\) (Matrix Exponential)"
The Embedded Chain
A CTMC can be decomposed into two parts:
Holding Times: Time spent in state \(i\) follows \(\text{Exp}(q_i)\).
Jump Probabilities: When the chain jumps from \(i\), it goes to \(j\) with probability:
\(r_{ij} = \frac{q_{ij}}{q_i}\)
Biological Application
In population dynamics, \(q_{i,i+1}\) is the birth rate and \(q_{i,i-1}\) is the death rate. The Q-matrix allows us to solve for the extinction probability using differential equations.
CTMC Generator Facilitator Guide Facilitator Protocol
PROT-STOCH-004
Lesson 4: CTMC & Generator Matrices
Instructional Context
This lesson introduces the Infinitesimal Generator Matrix \(Q\) . Students often struggle with the fact that \(Q\) contains rates , not probabilities . The key conceptual anchor is that the diagonal entries \(q_{ii}\) are negative and represent the rate of leaving state \(i\).
"Transitioning from \(\pi P = \pi\) (Discrete) to \(\pi Q = 0\) (Continuous). Explain that zero is the 'rate of change' for a system in equilibrium."
Kolmogorov Derivations
Students should see the derivation of \(P'(t) = P(t)Q\) starting from: \[P(t+h) = P(t)P(h)\] Substitute the linear approximation \(P(h) \approx I + Qh + o(h)\): \[P(t+h) \approx P(t)(I + Qh) = P(t) + P(t)Qh\] \[\frac{P(t+h) - P(t)}{h} \approx P(t)Q\]
Emphasize that the 'Forward' equation fixes the start and moves the end, while 'Backward' fixes the end and moves the start.
The Embedded Chain Strategy
"A continuous-time chain is just a discrete-time chain with random holding times."
Use the Embedded Chain to find stationary distributions when \(Q\) is complex.
Calculate \(\pi^{DTMC}\) of the jump matrix \(R\) where \(r_{ij} = q_{ij}/q_i\).
Relate to the CTMC distribution: \(\pi_i^{CTMC} = \frac{\pi_i^{DTMC}/q_i}{\sum_j \pi_j^{DTMC}/q_j}\).
Solution: Birth-Death Extinction
For state \(i\), let \(a_i\) be extinction probability.
Equation: \(a_i = \frac{\lambda_i}{\lambda_i + \mu_i} a_{i+1} + \frac{\mu_i}{\lambda_i + \mu_i} a_{i-1}\)
This is a discrete-time Gambler's Ruin problem hidden inside a CTMC.
CTMC Generator Worksheet The Infinitesimal Rate
Stochastic Processes | Graduate Module 04
Name: _____________________
Date: _____________________
1 Generator Matrix Design
A chemical reaction system has three states: 1 (Reactants), 2 (Intermediate), 3 (Product). The reaction from 1 to 2 happens at rate \(\alpha\). From 2, the system can go back to 1 at rate \(\beta\) or proceed to 3 at rate \(\gamma\). State 3 is an absorbing state.
A) Construct the generator matrix \(Q\) for this system.
[Write matrix Q here]
B) What is the expected time the system stays in the Intermediate state (State 2)?
2 Steady State in Continuous Time
For a 2-state CTMC with generator matrix \(Q = \begin{pmatrix} -\lambda & \lambda \\ \mu & -\mu \end{pmatrix}\), solve the system \(\pi Q = 0\) and \(\pi_1 + \pi_2 = 1\) to find the stationary distribution.
3 Transition Evolution
Let \(P(t)\) be the transition probability matrix for a CTMC. Using the Kolmogorov Backward Equation , derive a system of ordinary differential equations for \(P_{i1}(t)\) and \(P_{i2}(t)\) for the 2-state process defined in Problem 2.
Recall: \(P'(t) = QP(t)\)
Monte Carlo Slides Simulated Realities
Lesson 5: Monte Carlo and Inference of Stochastic Processes
Computational Sampling
Parameter Estimation
The Gillespie Algorithm
How do we simulate a single "sample path" of a continuous-time process?
The Recipe
Initialize system state \(i\) and time \(t=0\).
Calculate total rate \(q_i = \sum_{j \neq i} q_{ij}\).
Generate Time to Jump: \(\tau \sim \text{Exp}(q_i)\).
Generate Next State \(j\) with probability \(p_{ij} = q_{ij}/q_i\).
Update: \(t \leftarrow t + \tau\), \(i \leftarrow j\). Repeat.
Sample Path Realization
"Stochastic simulation doesn't predict what will happen; it predicts the distribution of what might happen."
Essential for systems where the Kolmogorov equations are analytically intractable.
Convergence and Dependency
Autocorrelation Function (ACF)
How much does the state at time \(t\) depend on the state at time \(t-k\)?
\[\rho(k) = \text{Corr}(X_t, X_{t+k})\]
In a Markov chain, \(\rho(k)\) typically decays exponentially with \(k\).
Burn-in and Mixing
When using simulation to estimate \(\pi\), we must discard the initial "burn-in" period where the chain hasn't reached its stationary distribution.
Burn-in | Steady State
Parameter Estimation
MLE for DTMC
Given a sequence of states \(x_0, x_1, \dots, x_n\):
\[\hat{p}_{ij} = \frac{n_{ij}}{\sum_k n_{ik}}\]
\(n_{ij}\) is the number of observed transitions from \(i\) to \(j\).
MLE for CTMC
Given holding times \(t_i\) and jump counts \(n_{ij}\):
\[\hat{q}_{ij} = \frac{n_{ij}}{\sum \text{holding time in } i}\]
The estimator is simply (Total Jumps) / (Total Time in State).
Monte Carlo Facilitator Guide Facilitator Protocol
PROT-STOCH-005
Lesson 5: Monte Carlo & Inference
Instructional Context
This capstone lesson transitions from theoretical "closed-form" solutions to computational approximations. Focus on the Law of Large Numbers as the theoretical justification for Monte Carlo.
"Remind students that simulation is not just for finding probabilities, but for understanding the variability and sample path behavior of a system."
"Stress the difference between the 'True' parameter \(p\) and the 'Estimated' parameter \(\hat{p}\)."
Explaining Gillespie
The Gillespie algorithm is statistically exact because it samples holding times from the true exponential distribution of the process. Contrast this with fixed-time-step Euler methods, which introduce discretization error.
"Why not use a fixed \(\Delta t\)? If \(\Delta t\) is too large, you might miss multiple jumps. If it's too small, it's computationally wasteful. Gillespie is event-driven."
Inference Strategy
"How do we know if our model is any good?"
Maximum Likelihood Estimation (MLE): The most common way to 'fit' a Markov chain to data. The estimators are intuitive (frequencies and averages).Autocorrelation: Use this to check for 'mixing' in MCMC. If autocorrelation stays high for large lags, the simulation hasn't explored the state space well.
Final Project Overview
Queueing Network Simulation
Challenge: Simulate a multi-server queue (M/M/s). Estimate the probability that the queue length exceeds \(K\). Compare the simulated result with the theoretical Erlang-C formula from previous lessons.
Monte Carlo Worksheet Computational Inference
Stochastic Processes | Graduate Module 05
Name: _____________________
Date: _____________________
1 Gillespie Algorithm Synthesis
Write the pseudo-code for the Gillespie algorithm to simulate a sample path for a 3-state CTMC with a given generator matrix \(Q\) from \(t=0\) to \(T=10\).
# Define state and time variables # Loop until T=10...
2 Maximum Likelihood Estimation
You observe a sample path of a 2-state DTMC (States 1 and 2) over 10 steps: 1, 1, 2, 2, 2, 1, 2, 2, 1, 1
A) Calculate the MLE transition matrix \(\hat{P}\).
[Show your count table and the resulting matrix]
B) Estimate the stationary distribution \(\hat{\pi}\) based on your estimated matrix.
3 Autocorrelation and Mixing
Consider a sample path \(X_1, X_2, \dots, X_N\). The lag-1 autocorrelation is defined as: \[\hat{\rho}(1) = \frac{\sum_{i=1}^{N-1} (X_i - \bar{X})(X_{i+1} - \bar{X})}{\sum_{i=1}^{N} (X_i - \bar{X})^2}\]
If you simulate a symmetric 2-state Markov chain (\(p_{11} = p_{22} = p\)), derive an expression for the theoretical autocorrelation \(\rho(1)\) in terms of \(p\).
Hint: Use the fact that \(E[X_i X_{i+1}] = \sum_j \sum_k j \cdot k \cdot P(X_{i+1}=k | X_i=j) P(X_i=j)\).
