Linear Algebra

10.4 Markov Chains: Modeling Systems That Change

Imron Rosyadi

10.4 Markov Chains: Modeling Systems That Change

Introduction to Markov Processes

A Markov Chain or Markov Process models a system that changes from state to state over time.

Example States:

• Weather: Sunny, Cloudy, Rainy
• Traffic signal: Green, Yellow, Red
• Digital circuit: High, Low
• Communication Channel: Good, Noisy

• Memoryless Property: This is crucial. It simplifies modeling as we only need the current state to predict the next, not the entire history. This is often applicable in real-world engineering systems where exact past sequences are too complex to track.
• In ECE, think of device states (e.g., working, failed), network node status (busy, idle), or process control (above threshold, below threshold).

Transition Probabilities and Matrices

If a Markov chain has \(k\) possible states, labeled \(1, 2, \ldots, k\):

Transition Probability (\(p_{ij}\)):

• The probability that the system is in state \(i\) at the next observation, given it was in state \(j\) at the preceding observation.

Transition Matrix (\(P\)):

• \(P = [p_{ij}]\)
• Columns represent preceding states.
• Rows represent next states.

\[ P = \left[ \begin{array}{llll} p_{11} & p_{12} & \dots & p_{1k} \\ p_{21} & p_{22} & \dots & p_{2k} \\ \vdots & \vdots & \ddots & \vdots \\ p_{k1} & p_{k2} & \dots & p_{kk} \end{array} \right] \begin{array}{l} \longleftarrow \text{ Next State 1} \\ \longleftarrow \text{ Next State 2} \\ \longleftarrow \vdots \\ \longleftarrow \text{ Next State k} \end{array} \] \[\uparrow \uparrow \quad \uparrow\] \[\text{Prev. State 1} \quad \text{Prev. State 2} \quad \text{Prev. State k}\]

• Emphasize that the columns sum to 1 because from any given preceding state \(j\), the system must transition to some state (could be itself).
• This structure of \(P\) is vital for understanding how probabilities propagate through the system.
• \(p_{32}\) is the probability to go FROM state 2 TO state 3.

Example 1: Car Rental Agency

A car rental agency has three locations (1, 2, 3). The manager finds customer return patterns:

• From Location 1:
  • Return to 1: 80%
  • Return to 2: 10%
  • Return to 3: 10%
• From Location 2:
  • Return to 1: 30%
  • Return to 2: 20%
  • Return to 3: 50%
• From Location 3:
  • Return to 1: 20%
  • Return to 2: 60%
  • Return to 3: 20%

Transition Matrix (\(P\)): \[ P = \left[ \begin{array}{ccc} .8 & .3 & .2 \\ .1 & .2 & .6 \\ .1 & .5 & .2 \end{array} \right] \] This matrix is a Stochastic Matrix: all entries are non-negative, and columns sum to 1. \[ p_{1j} + p_{2j} + \dots + p_{kj} = 1 \]

• Walk through how the percentages map to the matrix entries. For example, the first column corresponds to cars rented from Location 1. 80% return to 1 (\(p_{11}=.8\)), 10% to 2 (\(p_{21}=.1\)), 10% to 3 (\(p_{31}=.1\)). Sum is \(0.8+0.1+0.1 = 1\).
• Explain the term “Stochastic matrix” and its importance. It’s a fundamental property of valid transition matrices.

State Vectors

Definition 2: State Vector (\(\mathbf{x}\)) A column vector \(\mathbf{x}\) whose \(i\)-th component \(x_i\) is the probability that the system is in the \(i\)-th state at a given time.

Example for a 3-state system: \[ \mathbf{x} = \left[ \begin{array}{l} x_{1} \\ x_{2} \\ x_{3} \end{array} \right] \]

• \(x_i \ge 0\) for all \(i\).
• \(\sum x_i = 1\) (the system must be in some state).
• A vector with these properties is called a probability vector.

Theorem 10.4.1: Future State Prediction If \(P\) is the transition matrix of a Markov chain and \(\mathbf{x}^{(n)}\) is the state vector at the \(n\)-th observation, then: \[ \mathbf{x}^{(n+1)} = P \mathbf{x}^{(n)} \] This implies: \[ \mathbf{x}^{(n)} = P^n \mathbf{x}^{(0)} \]

• The state vector provides a probabilistic snapshot of the system’s distribution across its states.
• This theorem is the core engine of Markov chain dynamics: matrix-vector multiplication propagates uncertain states through time.
• Highlight the power of linear algebra: complex probabilistic evolution reduces to repeated matrix multiplication.

Example 2: Alumni Donation (Probabilistic Evolution)

An alumni office finds:

• 80% of contributors contribute next year.
• 30% of non-contributors contribute next year.

States:

1. Contributor
2. Non-contributor

Transition Matrix: \[ P = \left[ \begin{array}{ll} .8 & .3 \\ .2 & .7 \end{array} \right] \]

Let’s track a new graduate who did not contribute initially.

Initial state \(\mathbf{x}^{(0)}\): certainty in state 2 (non-contributor). \[ \mathbf{x}^{(0)} = \left[ \begin{array}{l} 0 \\ 1 \end{array} \right] \]

• Explain derivation of \(P\):
  • Col 1 (from Contributor): 80% stay Contributor (\(p_{11}=.8\)), 20% become Non-contributor (\(p_{21}=.2\)).
  • Col 2 (from Non-contributor): 30% become Contributor (\(p_{12}=.3\)), 70% stay Non-contributor (\(p_{22}=.7\)).
• The initial state vector \(\mathbf{x}^{(0)}\) captures the starting condition. Since the person did not contribute, probability of being in state 1 is 0, probability of being in state 2 is 1.

Example 2: Alumni Donation (Interactive Simulation)

Let’s simulate the state vector evolution for the alumni example over several years.

• Pyodide interaction: This is a live Python simulation. Students can interact with it, change x0, or P to see the effect.
• Observe how the probabilities shift and eventually stabilize. This hints at a “long-term” behavior.
• For ECE, this relates to steady-state analysis of dynamic systems or iterative algorithms converging.

Example 4: Car Rental Agency (Interactive Simulation)

Revisiting Example 1 (\(P\) is 3x3). Let’s simulate if a car is initially rented from Location 2.

Initial state \(\mathbf{x}^{(0)}\): \[ \mathbf{x}^{(0)} = \left[ \begin{array}{l} 0 \\ 1 \\ 0 \end{array} \right] \]

• Again, observe the convergence. Even with a different starting state (car rented from location 2), the system still approaches a stable distribution.
• This suggests that the long-term behavior might be independent of the initial conditions for certain types of Markov chains.

Example 5: Traffic Officer (Network Flow)

A traffic officer moves between 8 intersections. They remain at the current intersection or move to an adjacent one, choosing randomly (equally likely).

graph LR
    subgraph Intersections
        1 --- 2
        1 --- 3
        2 --- 4
        2 --- 5
        3 --- 6
        4 --- 7
        4 --- 8
        5 --- 6
        5 --- 8
        6 --- 7
        7 --- 8
    end
    style 1 fill:#f9f,stroke:#333,stroke-width:2px
    style 2 fill:#f9f,stroke:#333,stroke-width:2px
    style 3 fill:#f9f,stroke:#333,stroke-width:2px
    style 4 fill:#f9f,stroke:#333,stroke-width:2px
    style 5 fill:#f9f,stroke:#333,stroke-width:2px
    style 6 fill:#f9f,stroke:#333,stroke-width:2px
    style 7 fill:#f9f,stroke:#333,stroke-width:2px
    style 8 fill:#f9f,stroke:#333,stroke-width:2px

If at intersection 5 (neighbors 2, 4, 8), she can go to 2, 4, 5, or 8, each with probability \(1/4\). The transition matrix \(P\) is 8x8.

• Mermaid diagram visualizes the “connectivity” of states. In engineering, this could represent communication network nodes, power grid connections, or process flow paths.
• Challenge students: how would you construct the 8x8 matrix based on this rule? For example, the 5th column would have \(p_{25}=.25, p_{45}=.25, p_{55}=.25, p_{85}=.25\), and others zero.
• This is a good example of how graph theory (network diagram) and linear algebra (transition matrix) are intertwined in practical problems.

Example 5: Transition Matrix

\(P_{8\times8}\) is given. If the officer starts at Intersection 5, initial state \(\mathbf{x}^{(0)}\) is: \[ \mathbf{x}^{(0)} = \left[ \begin{array}{l} 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{array} \right] \]

Example 5: Transition Matrix

Let’s see how her location probabilities evolve.

• Why Transpose? The given problem text’s \(P\) matrix (image) implicitly follows a row-stochastic convention or has columns summing to 1 by chance. The common definition of a transition matrix (\(P_{ij}\) from \(j\) to \(i\)) makes it column-stochastic. I’ve explicitly transposed the numpy array initialization to ensure it’s column-stochastic for \(P \mathbf{x}\).
• The results show a distribution of probabilities across intersections, not just for intersection 5. This signifies the probable location over time.
• Notice how the probabilities converge to very specific values, regardless of the initial starting point. This is the crucial characteristic of a “regular” Markov chain.
• This type of analysis is relevant in ECE for resource allocation, load balancing, or network traffic routing.

Visualization (1)

Visualization (2)

Visualizing a Markov Chain - Will Hipson

Limiting Behavior and Steady-State Vectors

Does \(\mathbf{x}^{(n)}\) always converge to a fixed vector?

• No! Example 6 shows it can oscillate.

  • \(P = \left[ \begin{array}{cc} 0 & 1 \\ 1 & 0 \end{array} \right]\), \(\mathbf{x}^{(0)} = \left[ \begin{array}{c} 1 \\ 0 \end{array} \right]\)
  • \(\mathbf{x}^{(0)} = \left[ \begin{array}{c} 1 \\ 0 \end{array} \right]\), \(\mathbf{x}^{(1)} = \left[ \begin{array}{c} 0 \\ 1 \end{array} \right]\), \(\mathbf{x}^{(2)} = \left[ \begin{array}{c} 1 \\ 0 \end{array} \right], \ldots\)

Definition 3: Regular Transition Matrix A transition matrix \(P\) is regular if some integer power of it, \(P^m\), has all positive entries (no zeros). * Examples 1, 2, 5 were regular (\(m=1\) or \(m=4\)). This ensures convergence.

Limiting Behavior and Steady-State Vectors

Theorem 10.4.3: Behavior of \(P^n \mathbf{x}\) as \(n \rightarrow \infty\) If \(P\) is a regular transition matrix and \(\mathbf{x}\) is any probability vector, then as \(n \rightarrow \infty\): \[ P^n \mathbf{x} \rightarrow \mathbf{q} \] where \(\mathbf{q}\) is a fixed probability vector, called the steady-state vector.

• \(\mathbf{q}\) is independent of the initial state \(\mathbf{x}^{(0)}\).
• All entries of \(\mathbf{q}\) are positive.

• The oscillation example shows why the “regular” condition is necessary. If \(P\) can prevent transitions to certain states over many steps, it might not converge.
• The term “steady-state” is very familiar in ECE (e.g., in circuit analysis, control systems). Here, it applies to the long-term probability distribution of states.
• This means that given enough time, the system will settle down into a predictable long-term distribution of probabilities across its states, regardless of how it started.

Calculating the Steady-State Vector (\(\mathbf{q}\))

Theorem 10.4.4: Steady-State Vector Property The steady-state vector \(\mathbf{q}\) of a regular transition matrix \(P\) is the unique probability vector that satisfies the equation: \[ P \mathbf{q} = \mathbf{q} \] This is an eigenvector problem! \(\mathbf{q}\) is an eigenvector of \(P\) corresponding to the eigenvalue \(\lambda = 1\).

Rearranging the equation: \[ (I - P) \mathbf{q} = \mathbf{0} \] This is a homogeneous linear system. We need to find the unique probability vector (entries sum to 1) in the null space of \((I-P)\).

• This connection to eigenvectors is a powerful application of linear algebra in probability theory.
• Since matrices describing physical systems often have stable long-term behaviors, finding the steady-state vector is a common task in various ECE fields, from queueing theory to network analysis.
• The matrix \((I-P)\) will be singular, meaning it has a non-trivial null space. We are looking for a specific vector in that null space.

Example 7: Alumni Donation (Steady-State Calculation)

Recall \(P = \left[ \begin{array}{ll} .8 & .3 \\ .2 & .7 \end{array} \right]\). We want to solve \((I - P) \mathbf{q} = \mathbf{0}\) \[ \left( \left[ \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right] - \left[ \begin{array}{cc} .8 & .3 \\ .2 & .7 \end{array} \right] \right) \left[ \begin{array}{c} q_{1} \\ q_{2} \end{array} \right] = \left[ \begin{array}{c} 0 \\ 0 \end{array} \right] \] \[ \left[ \begin{array}{cc} .2 & -.3 \\ -.2 & .3 \end{array} \right] \left[ \begin{array}{c} q_{1} \\ q_{2} \end{array} \right] = \left[ \begin{array}{c} 0 \\ 0 \end{array} \right] \] This gives \(.2q_1 - .3q_2 = 0 \implies q_1 = 1.5 q_2\).

Also, \(q_1 + q_2 = 1\). Substitute \(q_1\): \(1.5q_2 + q_2 = 1 \implies 2.5q_2 = 1 \implies q_2 = 0.4\).

Then \(q_1 = 1.5 \times 0.4 = 0.6\).

Thus, \(\mathbf{q} = \left[ \begin{array}{c} .6 \\ .4 \end{array} \right]\).

Example 7: Alumni Donation (Steady-State Calculation)

• The solution shows that in the long run, 60% of alumni will contribute and 40% will not. This provides valuable insight for fundraising strategies.
• Explain the augmented system trick: since \((I-P)\) is singular, we add the condition that components sum to 1 to make the system uniquely solvable. This is a common numerical technique.

Example 8: Car Rental Agency (Steady-State)

\(P = \left[ \begin{array}{ccc} .8 & .3 & .2 \\ .1 & .2 & .6 \\ .1 & .5 & .2 \end{array} \right]\) The system \((I - P) \mathbf{q} = \mathbf{0}\) is: \[ \left[ \begin{array}{ccc} .2 & -.3 & -.2 \\ -.1 & .8 & -.6 \\ -.1 & -.5 & .8 \end{array} \right] \left[ \begin{array}{c} q_{1} \\ q_{2} \\ q_{3} \end{array} \right] = \left[ \begin{array}{c} 0 \\ 0 \\ 0 \end{array} \right] \]

Interpretation for ECE / Facility Design:

• \(q_1 \approx 0.5573\): % of cars at Location 1.
• \(q_2 \approx 0.2295\): % of cars at Location 2.
• \(q_3 \approx 0.2131\): % of cars at Location 3.

If the agency has 1000 cars, roughly 557 will be at Location 1, 230 at Location 2, and 213 at Location 3 in the long run. This informs optimal parking space allocation.

• Here, linear algebra directly informs real-world engineering decisions. Facility planning, resource allocation, and inventory management can all benefit from this long-term probabilistic insight.
• This example demonstrates how mathematical models simplify seemingly complex real-world dynamics into actionable numbers.

Example 9: Traffic Officer (Steady-State)

Let’s find the long-term probability distribution for the traffic officer’s location.

The resulting steady-state vector shows the proportion of time the officer spends at each intersection over the long term. Are these proportions equal? Why or why not?

• The results show uneven distribution: some intersections (e.g., 4 and 5, 7 and 8) have higher probabilities. This is because these intersections are more “central” or have more connections in the network.
• Discussion Point: If the objective was to spend equal time at each intersection, this “random movement with equal probabilities to neighbors” strategy is not optimal. This highlights how complex systems behave, and mathematical analysis can reveal non-intuitive results.
• This has applications in load balancing in distributed systems, or resource allocation in networks. You might want to deliberately create an uneven distribution or aim for a perfectly even one, and Markov chains can model this.

Summary and Key Takeaways

Linear Algebra in Markov Chains:

• Transition Matrix (P): Describes state-to-state probabilities.
• State Vector (\(\mathbf{x}\)): Represents probability distribution across states.
• Time Evolution: \(\mathbf{x}^{(n+1)} = P \mathbf{x}^{(n)}\) (Matrix-vector multiplication).
• Steady-State Vector (\(\mathbf{q}\)): Long-term, stable probability distribution.
  • Found by solving \(P \mathbf{q} = \mathbf{q}\) or \((I-P) \mathbf{q} = \mathbf{0}\).
  • An eigenvector corresponding to eigenvalue \(\lambda=1\).

Summary and Key Takeaways

ECE Applications:

• System Reliability: Modeling component failure and repair states.
• Network Performance: Analyzing packet routing, queueing, node status.
• Control Systems: Describing controller states or system mode transitions.
• Resource Allocation: Optimizing resource distribution based on usage patterns.
• Signal Processing: Analyzing state transitions in digital filters or communication channels.

• Reinforce the interdisciplinary nature: probability and linear algebra combine to powerful modeling tools.
• Encourage students to think of other systems in ECE that could be modeled as Markov chains (e.g., a finite state machine, a sensor in different modes, a memory cell).
• Emphasize the practical utility of understanding long-term behavior (steady-state) in system design and optimization.