Markov Property Slides The Markov Property
Theoretical Foundations of Discrete-Time Stochastic Systems
Lesson 1: Formal Definitions & Matrices
The Markov Property
A stochastic process \(\{X_n, n \ge 0\}\) on a countable state space \(S\) is a Markov Chain if for all \(n \ge 0\) and all states \(i_0, i_1, \dots, i, j \in S\):
\[ P(X_{n+1} = j \mid X_n = i, X_{n-1} = i_{n-1}, \dots, X_0 = i_0) = P(X_{n+1} = j \mid X_n = i) \]
The Present
The state at time \(n\) contains all necessary information to predict the future.
The Past
Conditioning on history prior to time \(n\) provides no additional predictive value.
Transition Probabilities
For a time-homogeneous Markov Chain, the transition probability is independent of \(n\):
\( p_{ij} = P(X_{n+1} = j \mid X_n = i) \)
The transition matrix \(P = (p_{ij})\) satisfies:
\( p_{ij} \ge 0 \) for all \(i, j\)
\( \sum_{j \in S} p_{ij} = 1 \) for each \(i\)
Example: Stochastic Matrix
\[ P = \begin{bmatrix} p_{00} & p_{01} & p_{02} \\ p_{10} & p_{11} & p_{12} \\ p_{20} & p_{21} & p_{22} \end{bmatrix} \]
Rows must sum to unity, representing all possible next states.
Case Study: Gambler's Ruin
Consider a gambler starting with fortune \(k\). In each step, they win $1 with probability \(p\) or lose $1 with probability \(q = 1-p\). The game stops when they reach 0 or \(N\).
Transition Structure:
\( p_{i, i+1} = p \quad (0 < i < N) \)
\( p_{i, i-1} = q \quad (0 < i < N) \)
\( p_{0,0} = 1, \quad p_{N,N} = 1 \) (Absorbing states)
State Space Graph
0 i N
Does the history of wins matter, or only the current bankroll?
Next Phase
If we know the 1-step probabilities, how do we calculate the probability of being in state \(j\) after \(n\) transitions?
\[ P^{(n)} = P \cdot P \cdot \dots \cdot P = P^n \]
Linear Algebra
Stochastic Prediction
System Modeling Worksheet Formal Systems Analysis
Random Processes & Stochastic Modeling (GRAD-701)
Problem Set 01
Markov Property & Matrices
Student Name: _________________________________________________
Date: ___________________
Instructions
Provide rigorous mathematical justifications for all proofs. When constructing transition matrices, clearly define the state space \(S\). Use standard matrix notation and ensure all stochastic properties are verified.
Q1
Verifying the Markov Property
Let \(\{Z_n, n \ge 1\}\) be a sequence of independent and identically distributed (i.i.d.) random variables with \(P(Z_n = 1) = p\) and \(P(Z_n = -1) = 1-p\). Define the partial sums \(X_n = \sum_{i=1}^n Z_i\) with \(X_0 = 0\).
(a) Prove that \(\{X_n, n \ge 0\}\) is a Markov Chain. (b) Does \(Y_n = |X_n|\) also satisfy the Markov Property? Justify your answer with a counter-example or proof.
Q2
The Inventory Control Problem
A store maintains an inventory of a specific high-end item. The inventory is checked every Monday morning. If the inventory level is \(x \le 1\), the store orders enough items to bring the stock back to \(M = 3\). If \(x > 1\), no order is placed. Let \(D_n\) be the demand during week \(n\), where \(D_n\) are i.i.d. Poisson random variables with parameter \(\lambda = 1\).
Construct the transition probability matrix \(P\) for the inventory level \(X_n\) at the start of week \(n\). Note: If demand exceeds stock, the inventory becomes 0.
[ Work Area: Calculate \(p_{ij} = P(X_{n+1} = j \mid X_n = i) \) for \(i, j \in \{0, 1, 2, 3\}\) ]
Q3
Stochastic Proofs
Let \(P\) and \(Q\) be two \(N \times N\) stochastic matrices. Prove that their product \(R = PQ\) is also a stochastic matrix. Interpret this result in the context of a two-step transition process.
Stochastic Logic Guide Instructor Guidance
Lesson 1: The Markov Property & Transition Matrices
Key Theoretical Concepts
1. Memoryless Property
The core of this lesson is the shift from "history-dependent" to "state-dependent" logic. Emphasize that \(X_n\) is a sufficient statistic for the future evolution of the process.
Misconception: Students often think Markov means the past has NO influence. Clarify: The past influences the future ONLY THROUGH the current state.
2. Stochastic Matrix Rigor
Ensure students strictly verify the row sum property \(\sum_j p_{ij} = 1\). This is not just a definition but a consequence of the law of total probability applied to the conditional space.
Problem Set Deep-Dive
Q1: The Random Walk and Absolute Value
Part (a) is straightforward induction or direct substitution using \(X_{n+1} = X_n + Z_{n+1}\). Since \(Z_{n+1}\) is independent of \(X_0, \dots, X_n\), the property holds.
Crucial Point: For Part (b), \(Y_n = |X_n|\) is NOT always Markov. In a symmetric walk (\(p=0.5\)), it is. In an asymmetric walk, knowing \(|X_n|\) isn't enough to know the distribution of \(X_{n+1}\) because we don't know the sign of \(X_n\), which affects the probability of moving "closer" to or "further" from zero.
Q2: Inventory Calculations
The transition from state \(i\) to \(j\) depends on the reorder rule.
- If \(i \in \{0, 1\}\), we reorder to 3. So \(X_{n+1} = \max(0, 3 - D_{n+1})\).
- If \(i \in \{2, 3\}\), we don't reorder. So \(X_{n+1} = \max(0, i - D_{n+1})\).
Probabilities involve Poisson sums: \(P(D=k) = e^{-1} / k!\).
Discussion Hooks
Does the stock market have the Markov property? If so, why do technical analysts look at "momentum" (past trends)?
How can we turn a non-Markov process into a Markov one by expanding the state space? (Concept of "State Augmentation")
n-Step Transitions Slides n-Step Transitions
The Chapman-Kolmogorov Equations & Matrix Powers
Lesson 2: Algebraic Dynamics
Defining \(P^{(n)}\)
We define the n-step transition probability as the probability that the process will be in state \(j\) after \(n\) steps, given it is currently in state \(i\):
\[ p_{ij}^{(n)} = P(X_{n+k} = j \mid X_k = i) \]
Crucial Matrix Relation
\[ P^{(n)} = P \times P \times \dots \times P = P^n \]
The probability matrix for \(n\) steps is simply the \(n\)-th power of the 1-step matrix.
Chapman-Kolmogorov
The equations provide a method for computing \(p_{ij}^{(n+m)}\) by breaking the path into two segments of length \(n\) and \(m\):
\[ p_{ij}^{(n+m)} = \sum_{k \in S} p_{ik}^{(n)} p_{kj}^{(m)} \]
Intuition:
To go from \(i\) to \(j\) in \(n+m\) steps, you must pass through some intermediate state \(k\) at step \(n\).
i Step 0
n steps
k Step n
m steps
j Step n+m
This is functionally equivalent to matrix multiplication: \(P^{n+m} = P^n P^m\).
Solving for Large n
Calculating \(P^n\) for large \(n\) is computationally expensive via direct multiplication. Instead, we use Eigenvalue Decomposition:
Step-by-Step Procedure:
1. Find eigenvalues \(\lambda\) and eigenvectors \(v\).
2. Construct \(P = SDS^{-1}\).
3. Observe that \(P^n = S D^n S^{-1}\).
4. Note: \(D^n = \text{diag}(\lambda_1^n, \dots, \lambda_k^n)\).
Theoretical Limit
As \(n \to \infty\), terms with \(|\lambda| < 1\) vanish. Only the principal eigenvalue (\(\lambda = 1\)) remains significant.
\(\lim_{n \to \infty} P^n = \Pi\)
Predicting the Future
"If it rains today, there is a 70% chance it rains tomorrow. If it is clear today, there is only a 40% chance of rain tomorrow."
Transition Matrix
\[ P = \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix} \]
1-Week Prediction
\[ P^{(7)} = P^7 \approx \begin{bmatrix} 0.572 & 0.428 \\ 0.571 & 0.429 \end{bmatrix} \]
System Dynamics Workshop Transitions & Diagonalization
Calculating multi-step dynamics via matrix decomposition.
Workshop 02
Student Name: _________________________________________________
Date: ___________________
Problem Scenario
A simple communication system consists of two nodes. The system can be in two states: State 0 (Functional) or State 1 (Failure). The transition matrix is given by:
\[ P = \begin{bmatrix} 0.8 & 0.2 \\ 0.3 & 0.7 \end{bmatrix} \]
Part I: Spectral Analysis
1. Calculate the eigenvalues \(\lambda_1\) and \(\lambda_2\) of the matrix \(P\). (Hint: Solve \(|P - \lambda I| = 0\)).
2. For each eigenvalue, find the corresponding eigenvector. Normalize the eigenvectors such that the matrix of eigenvectors \(S\) is formed.
Part II: n-Step Derivation
3. Using the decomposition \(P = S D S^{-1}\), derive a general closed-form expression for the probability \(p_{00}^{(n)}\).
Part III: Asymptotic Behavior
4. Take the limit of your expression for \(p_{00}^{(n)}\) as \(n \to \infty\). What value does it approach? Interpret this in the context of the communication system's reliability.
Challenge: Three-State System
Consider a state space \(S = \{0, 1, 2\}\). If \(P\) is a circular transition matrix (0 -> 1 -> 2 -> 0) with probability 1, what are the eigenvalues? Does \(P^n\) converge as \(n \to \infty\)? Why or why not?
System Dynamics Key Detailed Solution Key
Workshop 02: Transitions & Diagonalization
Part I: Spectral Analysis
1. Eigenvalues of \(P\)
Characteristic Equation: \( \det(P - \lambda I) = (0.8 - \lambda)(0.7 - \lambda) - (0.2)(0.3) = 0 \)
2. Eigenvectors and Matrix S
For \(\lambda_1 = 1\): \((P - I)v = 0 \implies \begin{bmatrix} -0.2 & 0.2 \\ 0.3 & -0.3 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = 0 \implies v_1 = \begin{bmatrix} 1 \\ 1 \end{bmatrix} \)
Part II: n-Step Derivation
3. Closed Form for \(p_{00}^{(n)}\)
\( P^n = S D^n S^{-1} = \begin{bmatrix} 1 & 2 \\ 1 & -3 \end{bmatrix} \begin{bmatrix} 1^n & 0 \\ 0 & 0.5^n \end{bmatrix} \begin{bmatrix} 0.6 & 0.4 \\ 0.2 & -0.2 \end{bmatrix} \)
\( P^n = \begin{bmatrix} 1 & 2 \cdot 0.5^n \\ 1 & -3 \cdot 0.5^n \end{bmatrix} \begin{bmatrix} 0.6 & 0.4 \\ 0.2 & -0.2 \end{bmatrix} \)
Calculation for \(p_{00}^{(n)}\):
Part III: Asymptotic Behavior
4. Limiting Interpretation
As \(n \to \infty\), the term \(0.4(0.5)^n \to 0\). Thus, \( \lim_{n \to \infty} p_{00}^{(n)} = 0.6 \).
Interpretation: Regardless of the initial state, the system will be functional 60% of the time in the long run.
State Topology Slides State Topology
Recurrence, Transience, and Decompositions
Lesson 3: Classification of States
Communication Classes
Accessibility
State \(j\) is accessible from \(i\) (\(i \to j\)) if \(p_{ij}^{(n)} > 0\) for some \(n \ge 0\).
Communication
States \(i\) and \(j\) communicate (\(i \leftrightarrow j\)) if \(i \to j\) and \(j \to i\).
Equivalence Relation
Communication is an equivalence relation:
Reflexive: \(i \leftrightarrow i\)
Symmetric: \(i \leftrightarrow j \implies j \leftrightarrow i\)
Transitive: \(i \leftrightarrow j, j \leftrightarrow k \implies i \leftrightarrow k\)
A Markov chain is irreducible if all states communicate (one class).
Recurrence vs. Transience
Let \(f_i\) be the probability that, starting in \(i\), the process will ever return to \(i\).
Recurrent State:
\( f_i = 1 \)
The process returns to state \(i\) with probability 1 (and thus infinitely many times).
Transient State:
\( f_i < 1 \)
There is a non-zero probability that the process never returns to state \(i\).
Spectral Test
State \(i\) is recurrent if and only if:
\[ \sum_{n=1}^\infty p_{ii}^{(n)} = \infty \]
Wait, why? Think about the Borel-Cantelli Lemma.
Periodicity
State \(i\) has period \(d\) if \(p_{ii}^{(n)} > 0\) only when \(n\) is a multiple of \(d\), and \(d\) is the largest such integer.
\[ d(i) = \gcd \{n \ge 1 : p_{ii}^{(n)} > 0\} \]
Aperiodic States
If \(d(i) = 1\), the state is called aperiodic.
1 2
Bipartite systems are periodic (\(d=2\)).
Periodicity is a class property!
Pólya's Theorem
"A drunk man will find his way home, but a drunk bird may get lost forever."
1D Walk
Recurrent
2D Walk
Recurrent
3D Walk
Transient
How does the sum \(\sum p_{ii}^{(n)}\) change with dimension?
State Space Activity State Space Mapping
Topological Analysis of Transition Graphs
Case Study 03
Team Members: _________________________________________________
Date: ___________________
Consider a Markov Chain on the state space \(S = \{1, 2, 3, 4, 5, 6\}\) with the following transition matrix \(P\). Your task is to decompose the system and classify every state.
\[ P = \begin{bmatrix} 0.5 & 0.5 & 0 & 0 & 0 & 0 \\ 0.3 & 0.7 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0.5 & 0 & 0.5 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0.3 & 0.1 & 0.1 & 0.5 \\ 0 & 0 & 0 & 0 & 0.7 & 0.3 \end{bmatrix} \]
1. Visual Mapping
Sketch the transition diagram below. Use directed arrows to show accessibility.
2. Decomposition
Identify the communication classes and determine if they are closed.
Class 1:
Class 2:
Class 3:
3. State Classification Table
State Recurrent? Transient? Period (d) Absorbing? 1 2 3 4 5 6
Deep Theory Challenge
Prove that if \(i \leftrightarrow j\), then \(i\) is recurrent if and only if \(j\) is recurrent.
Recurrence Theory Notes Formal Theory: Recurrence Dynamics
Theoretical Supplement for Lesson 03
1. Return Probabilities
Define \(f_{ij}^{(n)} = P(X_n = j, X_k \neq j \text{ for } 1 \le k < n \mid X_0 = i)\). This is the probability that the first hit on state \(j\) occurs at exactly time \(n\).
The probability of ever visiting state \(j\) starting from \(i\) is: \[ f_{ij} = \sum_{n=1}^\infty f_{ij}^{(n)} \]
Theorem: State \(i\) is recurrent if \(f_{ii} = 1\) and transient if \(f_{ii} < 1\).
2. The Convergence Test
We can relate the probability of recurrence to the expected number of visits to state \(i\). Let \(N_i\) be the number of visits to state \(i\) over infinite time: \[ E[N_i \mid X_0 = i] = \sum_{n=0}^\infty P(X_n = i \mid X_0 = i) = \sum_{n=0}^\infty p_{ii}^{(n)} \]
If Transient:
The process eventually leaves state \(i\) forever with non-zero probability.
\[ \sum p_{ii}^{(n)} < \infty \]
If Recurrent:
The process returns infinitely many times with probability 1.
\[ \sum p_{ii}^{(n)} = \infty \]
3. Proof Sketch: Class Property
Claim: Periodicity is a class property. If \(i \leftrightarrow j\), then \(d(i) = d(j)\).
Reasoning Strategy:
Suppose \(i \leftrightarrow j\). Then there exist \(n, m\) such that \(p_{ij}^{(n)} > 0\) and \(p_{ji}^{(m)} > 0\).
Any path returning to \(i\) in \(k\) steps (i.e., \(p_{ii}^{(k)} > 0\)) can be used to construct a return to \(j\) in \(m+k+n\) steps: \(j \to i \to i \to j\).
Thus, any integer that divides all return times of \(i\) must also relate to the return times of \(j\). Through the symmetry of communication, the greatest common divisors must be identical.
End of Theoretical Supplement
Equilibrium Slides Steady State Behavior
Limiting Probabilities & Stationary Distributions
Lesson 4: Statistical Equilibrium
The Distribution \(\pi\)
"A distribution that, once reached, remains unchanged by the transition matrix."
\[ \pi P = \pi \]
The Equilibrium Equation
Requirement 1
\[ \sum_{j \in S} \pi_j = 1 \]
Requirement 2
\[ \pi_j \ge 0 \]
Fundamental Theorem
For an irreducible and ergodic (recurrent + aperiodic) Markov chain:
Ergodic Interpretation
Mean Reward
\[ \bar{R} = \sum_{j \in S} \pi_j r_j \]
The long-run average reward per step equals the ensemble average over the stationary distribution.
Mean Return Time
\[ m_{jj} = \frac{1}{\pi_j} \]
"If the stationary probability of being in state \(j\) is 0.1, you return to state \(j\) on average every 10 steps."
Ranking the Web
Google's PageRank is the stationary distribution of a random surfer moving between web pages (with a damping factor to ensure ergodicity).
\(\pi = \pi (\alpha P + (1-\alpha) E)\)
Consistency out of chaos.
Equilibrium Worksheet Equilibrium Analysis
Solving for stationary distributions in finite systems.
Problem Set 04
Student Name: _________________________________________________
Date: ___________________
Q1
Direct Matrix Solution
A simple social network model involves three states: Active (A), Lurker (L), and Inactive (I). The transition matrix is:
\[ P = \begin{bmatrix} 0.6 & 0.3 & 0.1 \\ 0.2 & 0.5 & 0.3 \\ 0.0 & 0.2 & 0.8 \end{bmatrix} \]
Find the stationary distribution \(\pi = [\pi_A, \pi_L, \pi_I]\) by solving the system \(\pi P = \pi\) subject to \(\sum \pi_i = 1\).
[ Show all linear equations and substitution steps ]
Q2
Mean Return Time Analysis
Consider an irreducible Markov Chain with stationary distribution \(\pi\). Let \(m_{jj}\) be the expected number of transitions to return to state \(j\) given it starts in \(j\).
Scenario:
A manufacturing robot moves between four stations. If the long-run proportion of time spent at the QC station (State 4) is 0.125, how many steps on average will pass between visits to the QC station?
Q3
The Periodic Challenge
Does the chain with matrix \( P = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \) have a stationary distribution? If so, does \(p_{ij}^{(n)}\) converge to it as \(n \to \infty\)? Prove your answer.
Need help? Reference the Fundamental Theorem of Ergodic Chains in your notes.
MATH-STOCH-4
Equilibrium Key Equilibrium Key
Problem Set 04: Limiting Behavior
Q1 Solution: Network Model
Equations from \(\pi P = \pi\):
(1) \( 0.6\pi_A + 0.2\pi_L = \pi_A \implies 0.2\pi_L = 0.4\pi_A \implies \pi_L = 2\pi_A \)
(2) \( 0.3\pi_A + 0.5\pi_L + 0.2\pi_I = \pi_L \)
(3) \( 0.1\pi_A + 0.3\pi_L + 0.8\pi_I = \pi_I \implies 0.1\pi_A + 0.3\pi_L = 0.2\pi_I \)
(4) \( \pi_A + \pi_L + \pi_I = 1 \)
Substitution:
Substitute (1) into (3): \( 0.1\pi_A + 0.3(2\pi_A) = 0.2\pi_I \implies 0.7\pi_A = 0.2\pi_I \implies \pi_I = 3.5\pi_A \)
Using normalization (4): \( \pi_A + 2\pi_A + 3.5\pi_A = 1 \implies 6.5\pi_A = 1 \)
\(\pi_A \approx 0.1538, \quad \pi_L \approx 0.3077, \quad \pi_I \approx 0.5385\)
Q2 Solution: Robot Mean Return
Given \(\pi_{QC} = 0.125\).
\( m_{jj} = 1 / \pi_j = 1 / 0.125 = 8 \)
Result: The robot returns to the QC station every 8 steps on average.
Q3 Solution: The Periodicity Trap
Solving \(\pi P = \pi\) gives \(\pi = [0.5, 0.5]\). So a stationary distribution exists .
However, the chain is periodic with \(d=2\). The values of \(p_{ij}^{(n)}\) oscillate between 0 and 1.
Conclusion: It does NOT converge to \(\pi\). Limiting probabilities do not exist for periodic chains.
Reversibility Slides Time Reversibility
Detailed Balance & Random Walks on Graphs
Lesson 5: Symmetry in Chaos
Detailed Balance
A stationary distribution \(\pi\) is said to satisfy the detailed balance equations if for all \(i, j\):
\[ \pi_i p_{ij} = \pi_j p_{ji} \]
The Reverse-Path Symmetry
Theorem:
If a distribution \(\pi\) satisfies detailed balance, it is a stationary distribution for the chain. Such a chain is called time-reversible.
The Film Analogy
Imagine filming a Markov chain in equilibrium. If you play the film backward:
Forward Process:
"Prob. of transition \(i \to j\) is \(p_{ij}\)."
Backward Process:
"Prob. of transition \(j \to i\) is \(p^*_{ji} = \frac{\pi_i p_{ij}}{\pi_j}\)."
Statistical Indistinguishability
The chain is reversible if and only if the forward and backward transition probabilities are identical.
\(p_{ij} = p^*_{ji}\)
Walks on Graphs
Consider an undirected graph with edge weights \(w_{ij}\). A random walk moves from \(i\) to \(j\) with probability:
\[ p_{ij} = \frac{w_{ij}}{\sum_k w_{ik}} \]
Stationary Distribution:
\[ \pi_i = \frac{\sum_k w_{ik}}{\sum_a \sum_b w_{ab}} \]
Key Result:
Every random walk on a connected undirected graph is time-reversible.
Proof: Substitute \(\pi\) and \(p_{ij}\) into the detailed balance equation and observe symmetry.
Resistor Networks
The probability that a random walk visits state A before state B is mathematically equivalent to the voltage at node A in an electrical network where edge weights represent conductance.
Probability
Hitting Times
Electricity
Kirchhoff's Laws
Unified Theoretical Framework
Reversibility Workshop Graph Walks & Reversibility
Detailed Balance and Resistance Analogies
Final Workshop 05
Student Name: _________________________________________________
Date: ___________________
Q1
Verification of Detailed Balance
A Markov chain has three states with transition matrix \( P = \begin{bmatrix} 0.5 & 0.4 & 0.1 \\ 0.2 & 0.5 & 0.3 \\ 0.1 & 0.9 & 0.0 \end{bmatrix} \).
(a) Solve for the stationary distribution \(\pi\).
Q2
Walk on a Weighted Graph
A triangle-shaped graph has nodes A, B, and C. The weights of the edges are \(w_{AB} = 2, w_{BC} = 3, w_{AC} = 5\).
Calculate the transition probability \(p_{AB}\) and the stationary probability \(\pi_C\).
Q3
The Resistance Distance
In a graph where edge weights are conductances, the Commute Time between nodes \(i\) and \(j\) (expected time to go from \(i\) to \(j\) and back) is related to the effective resistance \(R_{eff}(i,j)\).
Theoretical Proof:
Prove that for any reversible Markov chain, if we define "distance" between states as \(D(i,j) = -\log(\pi_i p_{ij})\), this distance is symmetric. How does this symmetry facilitate the modeling of physical systems compared to non-reversible chains?
Sequence Synthesis
Reflect on the essential question: Under what conditions does a system reach equilibrium? Consider the roles of Irreducibility (connectivity), Aperiodicity (timing), and Reversibility (symmetry) discussed across these five lessons.
Theory Review Sheet Sequence Review
Discrete-Time Markov Chains: Theoretical Foundations
Foundational Pillars
The Markov Property
Future behavior depends only on the current state, not the sequence of events that preceded it.
State Classification
States are Recurrent (return is certain) or Transient (escape is possible). Chains are Irreducible if all states talk.
Stationarity
The vector \(\pi\) where \(\pi P = \pi\). Represents long-run proportion of time spent in each state.
Reversibility
Detailed balance (\(\pi_i p_{ij} = \pi_j p_{ji}\)) ensures the process looks the same forward and backward.
Equation Reference
n-Step Transition: P^{(n)} = P^n
Chapman-Kolmogorov: p_{ij}^{(n+m)} = \sum p_{ik}^{(n)} p_{kj}^{(m)}
Mean Return Time: m_{jj} = 1 / \pi_j
Recurrence Test: \sum_{n=1}^\infty p_{ii}^{(n)} = \infty
Graph Walk \(\pi\): \pi_i \propto \sum_j w_{ij}
Conditions for Ergodicity
A Markov chain converges to a unique stationary distribution independently of its initial state if and only if it is:
Irreducible
Aperiodic
Positive Recurrent
Discrete-Time Markov Chains • Graduate Theory Series
