Chapter 1: Fundamental Theory of Markov Processes

Haiyue
9min

Chapter 1: Fundamental Theory of Markov Processes

1.1 Basic Concepts of Markov Processes

1.1.1 Definition

A Markov process is a special type of stochastic process whose core characteristic is memorylessness (Markov property).

Mathematical Definition: Let {Xt,t≥0}\{X_t, t \geq 0\} be a stochastic process defined on the probability space (Ω,F,P)(\Omega, \mathcal{F}, P) with state space SS. If for any 0≤t0<t1<⋯<tn<t0 \leq t_0 < t_1 < \cdots < t_n < t, we have:

P(Xt∈A∣Xt0,Xt1,…,Xtn)=P(Xt∈A∣Xtn)P(X_t \in A | X_{t_0}, X_{t_1}, \ldots, X_{t_n}) = P(X_t \in A | X_{t_n})

where A⊆SA \subseteq S, then {Xt}\{X_t\} is called a Markov process.

1.1.2 Meaning of the Markov Property

  • Memorylessness: Future states depend only on the current state, independent of past history
  • Conditional Independence: Given the present, the future is conditionally independent of the past
  • First-order Dependence: The next state depends only on the current state

1.1.3 Classification of Markov Processes

🔄 正在渲染 Mermaid 图表...

1.2 State Space and Transition Probabilities

1.2.1 State Space

Definition: The set of all possible values that a Markov process can take is called the state space, denoted as SS.

Classification:

  • Finite state space: S={1,2,…,N}S = \{1, 2, \ldots, N\}
  • Countably infinite state space: S={0,1,2,…}S = \{0, 1, 2, \ldots\} or S=ZS = \mathbb{Z}
  • Continuous state space: S=RS = \mathbb{R} or S=RdS = \mathbb{R}^d

1.2.2 Transition Probabilities

For discrete-time Markov chains, the transition probability is defined as:

pij(m,n)=P(Xn=j∣Xm=i),m<np_{ij}(m,n) = P(X_n = j | X_m = i), \quad m < n

Homogeneous Markov Chain: If the transition probability is independent of the initial time, i.e.: pij(m,n)=pij(0,n−m)p_{ij}(m,n) = p_{ij}(0, n-m)

We usually denote: pij(n)=P(Xm+n=j∣Xm=i)p_{ij}^{(n)} = P(X_{m+n} = j | X_m = i)

In particular, the one-step transition probability: pij=pij(1)=P(Xn+1=j∣Xn=i)p_{ij} = p_{ij}^{(1)} = P(X_{n+1} = j | X_n = i)

1.2.3 Properties of Transition Probabilities

  1. Non-negativity: pij≥0p_{ij} \geq 0 for all i,j∈Si, j \in S
  2. Normalization: ∑j∈Spij=1\sum_{j \in S} p_{ij} = 1 for all i∈Si \in S

1.3 Transition Matrix

1.3.1 Definition

For a finite state space S={1,2,…,N}S = \{1, 2, \ldots, N\}, the transition matrix PP is defined as:

p_{11} & p_{12} & \cdots & p_{1N} \\ p_{21} & p_{22} & \cdots & p_{2N} \\ \vdots & \vdots & \ddots & \vdots \\ p_{N1} & p_{N2} & \cdots & p_{NN} \end{pmatrix}$$ ### 1.3.2 Properties of Transition Matrix 1. **Stochastic Matrix**: Each row has non-negative elements that sum to 1 2. **$n$-step Transition Matrix**: $P^{(n)} = P^n$ 3. **Chapman-Kolmogorov Equation**: $$p_{ij}^{(m+n)} = \sum_{k \in S} p_{ik}^{(m)} p_{kj}^{(n)}$$ ## 1.4 Initial Distribution and Finite-dimensional Distributions ### 1.4.1 Initial Distribution The initial distribution $\mu$ of a Markov chain is defined as: $$\mu_i = P(X_0 = i), \quad i \in S$$ Satisfying: $\mu_i \geq 0$ and $\sum_{i \in S} \mu_i = 1$ ### 1.4.2 Finite-dimensional Distributions The joint distribution of a Markov chain at times $0, 1, \ldots, n$ is: $$P(X_0 = i_0, X_1 = i_1, \ldots, X_n = i_n) = \mu_{i_0} \prod_{k=0}^{n-1} p_{i_k i_{k+1}}$$ ## 1.5 Python Implementation - Basic Example ```python import numpy as np import matplotlib.pyplot as plt from scipy.linalg import matrix_power class MarkovChain: """Basic Markov Chain Class""" def __init__(self, transition_matrix, initial_distribution=None): """ Initialize Markov Chain Parameters: ----------- transition_matrix : array-like Transition matrix initial_distribution : array-like, optional Initial distribution, defaults to uniform distribution """ self.P = np.array(transition_matrix) self.n_states = self.P.shape[0] # Validate transition matrix self._validate_transition_matrix() # Set initial distribution if initial_distribution is None: self.pi0 = np.ones(self.n_states) / self.n_states else: self.pi0 = np.array(initial_distribution) def _validate_transition_matrix(self): """Validate transition matrix""" # Check if matrix is square if self.P.shape[0] != self.P.shape[1]: raise ValueError("Transition matrix must be square") # Check if all elements are non-negative if np.any(self.P < 0): raise ValueError("All elements in transition matrix must be non-negative") # Check if each row sums to 1 row_sums = np.sum(self.P, axis=1) if not np.allclose(row_sums, 1.0): raise ValueError("Each row in transition matrix must sum to 1") def simulate(self, n_steps, initial_state=None): """ Simulate Markov chain path Parameters: ----------- n_steps : int Number of simulation steps initial_state : int, optional Initial state, defaults to random selection based on initial distribution Returns: -------- path : list State path """ if initial_state is None: current_state = np.random.choice(self.n_states, p=self.pi0) else: current_state = initial_state path = [current_state] for _ in range(n_steps): # Choose next state based on current state's transition probabilities next_state = np.random.choice(self.n_states, p=self.P[current_state]) path.append(next_state) current_state = next_state return path def n_step_transition_matrix(self, n): """Calculate n-step transition matrix""" return matrix_power(self.P, n) def state_distribution(self, n): """Calculate state distribution after n steps""" return self.pi0 @ self.n_step_transition_matrix(n) # Example: Weather Model def weather_example(): """Weather Markov Chain Example""" # States: 0-Sunny, 1-Rainy # Transition matrix: If sunny today, 80% sunny tomorrow, 20% rainy; If rainy today, 60% sunny tomorrow, 40% rainy P = np.array([ [0.8, 0.2], # Sunny -> [Sunny, Rainy] [0.6, 0.4] # Rainy -> [Sunny, Rainy] ]) # Initial distribution: Sunny today pi0 = np.array([1.0, 0.0]) # Create Markov chain weather_chain = MarkovChain(P, pi0) # Simulate 30 days of weather weather_path = weather_chain.simulate(30, initial_state=0) # Print results weather_names = ['Sunny', 'Rainy'] print("30-day weather simulation:") for i, state in enumerate(weather_path): print(f"Day {i}: {weather_names[state]}") # Calculate long-term distribution print("\nLong-term weather distribution:") for n in [1, 5, 10, 50]: dist = weather_chain.state_distribution(n) print(f"After {n} days: Sunny probability={dist[0]:.3f}, Rainy probability={dist[1]:.3f}") return weather_chain, weather_path # Run example if __name__ == "__main__": weather_chain, path = weather_example() ``` ## 1.6 Chapter Summary This chapter covered the fundamental theory of Markov processes, including: 1. **Core Concept**: The Markov property (memorylessness) is the fundamental characteristic of Markov processes 2. **Mathematical Definition**: Precisely defined Markov processes through conditional probabilities 3. **Classification System**: Classified Markov processes by time and state space 4. **Transition Probabilities**: Probability mechanisms describing transitions between states 5. **Transition Matrix**: Matrix representation of finite-state Markov chains 6. **Python Implementation**: Implemented basic Markov chain simulation through programming **Key Formulas**: - Markov Property: $P(X_t \in A | X_{t_0}, \ldots, X_{t_n}) = P(X_t \in A | X_{t_n})$ - Chapman-Kolmogorov Equation: $p_{ij}^{(m+n)} = \sum_k p_{ik}^{(m)} p_{kj}^{(n)}$ - Finite-dimensional Distribution: $P(X_0 = i_0, \ldots, X_n = i_n) = \mu_{i_0} \prod_{k=0}^{n-1} p_{i_k i_{k+1}}$ These fundamental theories lay a solid foundation for subsequent learning of more complex Markov models and financial applications.