Markov Chain Calculator

Understanding Markov Chains

Core Concepts

• States: The possible conditions or configurations the system can be in.
• Transition Matrix: A square matrix that defines the probabilities of moving from one state to another.
• Initial State Vector: Represents the starting probabilities for each state.
• Steady State: The long-term probabilities of being in each state when the system stabilizes.

Formula for State Transitions

The formula for calculating the next state in a Markov Chain is:

• \(S_n\): Current state vector.
• \(P\): Transition matrix.
• \(S_{n+1}\): Next state vector.

Key Properties

• Row-Stochastic Matrix: Each row in the transition matrix must sum to 1.
• Stationary Distribution: A probability vector that remains unchanged after further transitions.

Applications of Markov Chains

• Finance: Modeling stock price movements and credit ratings.
• Genetics: Analyzing DNA sequences and mutation rates.
• Search Engines: Google's PageRank algorithm uses Markov Chains to rank web pages.
• Queueing Theory: Predicting customer flow in service systems.

Example Calculation

Suppose we have a transition matrix and an initial state vector:

To calculate the probabilities after 2 steps:

• Step 1: \[ S_1 = S_0 \cdot P = \begin{bmatrix} 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix} = \begin{bmatrix} 0.7 & 0.3 \end{bmatrix} \]
• Step 2: \[ S_2 = S_1 \cdot P = \begin{bmatrix} 0.7 & 0.3 \end{bmatrix} \cdot \begin{bmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{bmatrix} = \begin{bmatrix} 0.61 & 0.39 \end{bmatrix} \]

Steady State Calculation

For steady state, solve \( S \cdot P = S \) with the constraint that \(\sum S = 1\). For the above matrix:

The steady state indicates that over time, the probabilities of being in each state stabilize at 57.14% and 42.86%, respectively.

Limitations of Markov Chains

• Memoryless Property: Assumes the next state depends only on the current state.
• Transition Probabilities: Must be precisely known, which can be challenging in real-world scenarios.
• Stationarity: Assumes the probabilities remain constant over time, which might not hold in dynamic systems.

Markov Chain Implementation in Python, R, and JavaScript

Python Implementation

import numpy as np

def calculate_markov_chain(initial_state, transition_matrix, steps):
    """
    Calculate Markov Chain state vectors.

    Parameters:
        initial_state (list): Initial state vector.
        transition_matrix (list of lists): Transition matrix.
        steps (int): Number of steps to compute.

    Returns:
        list of lists: State vectors at each step.
    """
    # Convert to NumPy arrays for easier calculations
    state = np.array(initial_state)
    matrix = np.array(transition_matrix)
    results = [state.tolist()]

    # Compute state vectors for the specified steps
    for _ in range(steps):
        state = state @ matrix
        results.append(state.tolist())

    return results

# Example Usage
initial_state = [1, 0]  # 100% probability in state 1
transition_matrix = [
    [0.7, 0.3],
    [0.4, 0.6],
]
steps = 5

results = calculate_markov_chain(initial_state, transition_matrix, steps)
for i, state in enumerate(results):
    print(f"Step {i}: {state}")

R Implementation

calculate_markov_chain <- function(initial_state, transition_matrix, steps) {
    # Initialize state vector and store results
    state <- initial_state
    results <- list(state)

    # Compute state vectors for the specified steps
    for (i in 1:steps) {
        state <- state %*% transition_matrix
        results[[i + 1]] <- state
    }

    return(results)
}

# Example Usage
initial_state <- c(1, 0)  # 100% probability in state 1
transition_matrix <- matrix(c(0.7, 0.3, 0.4, 0.6), nrow = 2, byrow = TRUE)
steps <- 5

results <- calculate_markov_chain(initial_state, transition_matrix, steps)
for (i in 0:steps) {
    cat(sprintf("Step %d: %s\n", i, toString(results[[i + 1]])))
}

JavaScript Implementation

function calculateMarkovChain(initialState, transitionMatrix, steps) {
    let state = [...initialState]; // Clone initial state to avoid modifying the original
    const results = [state.slice()]; // Store the initial state

    // Compute state vectors for the specified steps
    for (let step = 0; step < steps; step++) {
        const nextState = new Array(state.length).fill(0);

        // Perform matrix-vector multiplication
        for (let i = 0; i < transitionMatrix.length; i++) {
            for (let j = 0; j < transitionMatrix[i].length; j++) {
                nextState[i] += state[j] * transitionMatrix[j][i];
            }
        }

        state = nextState;
        results.push([...state]);
    }

    return results;
}

// Example Usage
const initialState = [1, 0]; // 100% probability in state 1
const transitionMatrix = [
    [0.7, 0.3],
    [0.4, 0.6],
];
const steps = 5;

const results = calculateMarkovChain(initialState, transitionMatrix, steps);
results.forEach((state, step) =>
    console.log(`Step ${step}: [${state.map(x => x.toFixed(4)).join(', ')}]`)
);

Key Points

• Python: Leverages NumPy for matrix operations, making the implementation concise and efficient.
• R: Uses matrix multiplication to compute state vectors, with results stored as a list of vectors.
• JavaScript: Implements matrix-vector multiplication using nested `map` and `reduce` functions for flexibility in web-based environments.

References for Python, R, JavaScript Implementations

• NumPy Matrix Multiplication – Learn more about matrix operations in Python.
• R Matrix Documentation – Detailed guide on matrix operations in R.
• JavaScript Array.reduce() – Understand how `reduce` is used for matrix-vector multiplication.

Further Reading

• Wikipedia: Markov Chains
• University of Cambridge: Markov Chains Lecture Notes
• The Research Scientist Pod Calculators – Explore more calculators for statistical and mathematical modeling.