Stochastic Processes & Markov Chains: Definitions, Models & Applications

TAKEAWAYS:

• Stochastic processes model random phenomena over time/space, classified by time (discrete/continuous) and state space (discrete/continuous).
• Markov chains are memoryless stochastic processes where future states depend only on the current state (Markov property).
• Transition matrices encode state probabilities and determine long-term behavior (steady-state distributions).
• Steady-state analysis finds equilibrium probabilities using balance equations and matrix methods.
• Applications include queueing theory, weather forecasting, and Markov decision processes (MDPs).
• Exam focus: Definitions, transition matrices, steady-state calculations, and real-world interpretations.

---

1. Stochastic Processes: Definitions and Classifications

1.1 Definition

A stochastic process is a collection of random variables $\{X_t\}$, indexed by time $t\in T$ (where $T$ can be discrete or continuous), representing the evolution of a system over time or space. Examples:

• Stock prices over days (discrete time).
• Temperature readings at fixed locations (continuous time).

1.2 Key Components

• Index set ($T$): Time or space parameter (e.g., $t=0,1,2,\dots$ for discrete time).
• State space ($S$): Possible values of $X_t$ (e.g., $\{0,1\}$ for binary outcomes like "sunny/rainy").
• Probability laws: Joint distributions $P(X_{t_1}=x_1,X_{t_2}=x_2,\dots )$.

1.3 Classification of Stochastic Processes

1.4 Example: Weather Process

Problem: In a town, each day is either sunny (S) or rainy (R). Given:

• $P(S_{t+1}|S_t)=0.8$ (sunny day followed by sunny day with 80% probability).
• $P(S_{t+1}|R_t)=0.4$ (rainy day followed by sunny day with 40% probability).

Solution: This is a discrete-time, discrete-state stochastic process. The transition probabilities define the system’s behavior:

• $P(R_{t+1}|S_t)=1-0.8=0.2$.
• $P(R_{t+1}|R_t)=1-0.4=0.6$.

---

2. Markov Chains: Definitions and Properties

2.1 Definition

A Markov chain is a stochastic process with the Markov property:

The future state depends only on the current state, not on the sequence of events that preceded it. Mathematically: $$P(X_{n+1}=x|X_n=x_n,X_{n-1}=x_{n-1},\dots )=P(X_{n+1}=x|X_n=x_n).$$

2.2 Characteristics of Markov Chains

1. Memoryless property: Future states are conditionally independent of past states given the present.
2. Homogeneity: Transition probabilities do not change over time (stationary).
3. Finite/mountable state space: Often assumed for tractability (though not required).
4. Transition probabilities: Defined by a transition matrix $P$, where: $$P_{ij}=P(X_{n+1}=j|X_n=i).$$
5. Initial distribution: ${\pi }_0=[{\pi }_0(1),{\pi }_0(2),\dots ,{\pi }_0(k)]$, where ${\pi }_0(i)=P(X_0=i)$.

2.3 Transition Matrix

For the weather example, the transition matrix $P$ is: $$P=\left[\begin{array}{cc}P(S_{t+1}|S_t)& P(R_{t+1}|S_t)\\ P(S_{t+1}|R_t)& P(R_{t+1}|R_t)\end{array}\right]=\left[\begin{array}{cc}0.8& 0.2\\ 0.4& 0.6\end{array}\right].$$ Properties of $P$:

• Each row sums to 1 (probability conservation).
• $P_{ij}\ge 0$ for all $i,j$.

2.4 Example: Two-State Markov Chain

Problem: A factory has two states:

• Working (W): Produces 100 units/day.
• Broken (B): Produces 0 units/day. Given:
• $P(W_{t+1}|W_t)=0.9$ (90% chance to stay working).
• $P(W_{t+1}|B_t)=0.3$ (30% chance to repair and switch to working).

Transition Matrix: $$P=\left[\begin{array}{cc}0.9& 0.1\\ 0.3& 0.7\end{array}\right].$$

Question: What is the probability the factory is working on day 3, given it was working on day 0? Solution: Use the Chapman-Kolmogorov equations: $$P(X_n=j)=\sum _{i}P(X_{n-1}=i)P_{ij}.$$ For $n=3$: $${\pi }_3={\pi }_0{P}^3.$$ Assuming ${\pi }_0=[1,0]$ (starts working): $$P^2={\left[\begin{array}{cc}0.9& 0.1\\ 0.3& 0.7\end{array}\right]}^2=\left[\begin{array}{cc}0.84& 0.16\\ 0.42& 0.58\end{array}\right],$$ $$P^3=P^2\cdot P=\left[\begin{array}{cc}0.802& 0.198\\ 0.462& 0.538\end{array}\right].$$ Thus, $P(X_3=W)=0.802$.

---

3. Steady-State Analysis

3.1 Definition

A Markov chain reaches steady-state (or equilibrium) when the state probabilities $\pi =[\pi (1),\pi (2),\dots ,\pi (k)]$ satisfy: $$\pi =\pi P,$$ and ${\sum }_i\pi (i)=1$.

3.2 Balance Equations

For each state $j$: $$\pi (j)=\sum _i\pi (i)P_{ij}.$$ This ensures flow conservation: probability entering state $j$ equals probability leaving it.

3.3 Example: Weather Process (Continued)

Find the steady-state probabilities for the weather Markov chain. Solution: Let $\pi =[\pi (S),\pi (R)]$. The balance equations are: $$\pi (S)=\pi (S)\cdot 0.8+\pi (R)\cdot 0.4,$$ $$\pi (R)=\pi (S)\cdot 0.2+\pi (R)\cdot \mathrm{0.6.}$$ With $\pi (S)+\pi (R)=1$, solve: $$\pi (S)=0.8\pi (S)+0.4(1-\pi (S))⟹0.2\pi (S)=0.4⟹\pi (S)=2.$$ This is invalid, so we use the matrix method: $$\pi =\pi P⟹\pi \left[\begin{array}{cc}-0.2& 0.2\\ 0.4& -0.4\end{array}\right]=\left[\begin{array}{cc}0& 0\end{array}\right].$$ Solving: $$-0.2\pi (S)+0.4\pi (R)=0⟹\pi (S)=2\pi (R).$$ With $\pi (S)+\pi (R)=1$: $$\pi (S)=\frac{2}{3},\pi (R)=\frac{1}{3}.$$ Interpretation: In the long run, the town is sunny 66.7% of the time.

3.4 General Solution for Steady-State

For an irreducible Markov chain (all states communicate), the steady-state distribution exists and is unique. Solve: $$\pi P=\pi ,$$ with ${\sum }_i\pi (i)=1$.

Method:

1. Write $k-1$ balance equations (drop one due to normalization).
2. Solve the system of linear equations.

---

4. Classification of States and Chains

4.1 State Classification

4.2 Types of Markov Chains

1. Finite Markov Chains: Finite state space (e.g., weather, factory).
2. Countable Markov Chains: Countably infinite states (e.g., queue lengths).
3. Continuous-Time Markov Chains (CTMC): Time is continuous (e.g., exponential waiting times).
   • Defined by transition rates $q_{ij}$ instead of probabilities.
   • Example: Poisson process (arrivals in a queue).

---

5. Applications of Markov Chains

5.1 Real-World Examples

5.2 Example: Queueing System (M/M/1)

Assumptions:

• Arrivals: Poisson process (rate $\lambda$).
• Service times: Exponential distribution (rate $\mu$). Transition Rates: $$q_{n,n+1}=\lambda ,q_{n,n-1}=\mu ,q_{n,n}=-(\lambda +\mu ).$$ Steady-State Probabilities: $${\pi }_n={\left(\frac{\lambda }{\mu }\right)}^n{\pi }_0,{\pi }_0=1-\frac{\lambda }{\mu }(\text{if }\lambda <\mu ).$$

---

6. Comparison: Stochastic Processes vs. Markov Chains

---

7. Common Pitfalls and Exam Tips

7.1 Common Mistakes

1. Ignoring the Markov Property: Assuming dependence on past states when only the current state matters.
   • ❌ Incorrect: $P(X_{n+1}|X_n,X_{n-1})$.
   • ✅ Correct: $P(X_{n+1}|X_n)$.
2. Misapplying Transition Matrices: Forgetting rows sum to 1 or mixing up $P_{ij}$ (probability from $i$ to $j$).
3. Steady-State Errors: Not normalizing probabilities ($\sum \pi (i)=1$) or solving balance equations incorrectly.
4. Confusing Discrete/Continuous Time: Applying Markov chain methods to continuous-time processes without using rates.

7.2 Exam Strategies

1. Definitions:

   • Stochastic process: "A collection of random variables indexed by time."
   • Markov chain: "A stochastic process with the Markov property."
   • Steady-state: "Probabilities that do not change over time ($\pi =\pi P$)."

2. Transition Matrices:

   • Always verify rows sum to 1.
   • For $n$-step transitions, compute $P^n$ (use matrix multiplication or software).

3. Steady-State Calculations:

   • Write balance equations: $\pi (j)={\sum }_i\pi (i)P_{ij}$.
   • Solve with $\sum \pi (i)=1$.
   • For 2-state chains, use the shortcut: $$\pi (S)=\frac{P(R\to S)}{P(S\to R)+P(R\to S)}.$$

4. Real-World Interpretation:

   • Link abstract problems to scenarios (e.g., weather, queues).
   • Explain steady-state probabilities in context (e.g., "long-term fraction of sunny days").

5. Short Notes (for past exam questions):

   • Stochastic process: "A mathematical model describing random phenomena evolving over time/space."
   • Markov chain: "A stochastic process where future states depend only on the current state (memoryless)."
   • Applications: Queueing, finance, weather, biology.

7.3 Worked Example for Exams

Question: A Markov chain has transition matrix: $$P=\left[\begin{array}{cc}0.5& 0.5\\ 0.3& 0.7\end{array}\right].$$ Find the steady-state distribution. Solution:

1. Write balance equations: $${\pi }_1=0.5{\pi }_1+0.3{\pi }_2,$$ $${\pi }_2=0.5{\pi }_1+0.7{\pi }_2.$$
2. Simplify: $$0.5{\pi }_1=0.3{\pi }_2⟹{\pi }_1=0.6{\pi }_2.$$
3. Normalize: $${\pi }_1+{\pi }_2=1⟹0.6{\pi }_2+{\pi }_2=1⟹{\pi }_2=0.625,{\pi }_1=\mathrm{0.375.}$$ Answer: $\pi =[0.375,0.625]$.

---

8. Summary Table for Quick Revision

---

9. Practice Problems

1. Define: What is a stochastic process? Classify the following:
   • Stock prices at closing time each day.
   • Temperature at a fixed location every hour.
2. Markov Chain: For the transition matrix: $$P=\left[\begin{array}{cc}0.6& 0.4\\ 0.2& 0.8\end{array}\right],$$ find $P^2$ and interpret $P_{12}^2$.
3. Steady-State: A Markov chain has states {A, B} with:
   • $P(A\to A)=0.7$, $P(A\to B)=0.3$,
   • $P(B\to A)=0.4$, $P(B\to B)=0.6$. Find the long-run probability of being in state A.
4. Application: Model a simple queueing system where:
   • Arrivals: Poisson with rate $\lambda =2$ customers/hour.
   • Service: Exponential with rate $\mu =3$ customers/hour. Write the transition rate matrix for states $n=0,1,2,\dots$.

---

10. References for Further Study

• Books:
  • Ross, S. M. (2014). Stochastic Processes (3rd ed.). Wiley.
  • Norris, J. R. (1998). Markov Chains. Cambridge University Press.
• Online Resources:
  • Khan Academy: Markov Chains.
  • MIT OpenCourseWare: Probabilistic Systems Analysis.
• Software:
  • Python: numpy for matrix operations, scipy.stats for distributions.
  • R: markovchain package for Markov chain analysis.

---

Exam Tip

• For definitions: Use precise language. For example:
  • ❌ "Markov chain is a process where future depends on past."
  • ✅ "A Markov chain is a stochastic process with the Markov property: $P(X_{n+1}=x|X_n=x_n,X_{n-1}=x_{n-1},\dots )=P(X_{n+1}=x|X_n=x_n)$."
• For calculations:
  • Show all steps in steady-state problems (balance equations, normalization).
  • For transition matrices, explicitly state the interpretation of entries (e.g., "$P_{12}=0.4$ means a 40% chance to move from state 1 to state 2").
• For applications:
  • Always relate abstract problems to real-world scenarios (e.g., "This models a factory that breaks down and repairs itself").
• Short notes:
  • Focus on key differences (e.g., parametric vs. non-parametric tests in other units) or required assumptions (e.g., linearity, independence in regression). For this unit, prioritize:
    • Stochastic process vs. Markov chain.
    • Transition matrix vs. steady-state.
    • Discrete vs. continuous time/state.