Markov Chains In C++

Introduction to Markov Chains in C++

Markov chains are mathematical structures that move between different states within a specific state space. They represent a unique form of probabilistic model in which the future state is determined solely by the current state, independent of the past sequence of events. This characteristic is referred to as the Markov property.

In C++, Markov chains can be applied to simulate different real-life situations, like forecasting weather conditions, analyzing financial trends, and predicting user interactions on websites. Proficiency in implementing and utilizing Markov chains in C++ can greatly aid in creating predictive algorithms and running simulations.

Approach 1: Basic Approach

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
enum Weather {Sunny, Rainy, Cloudy};
int main() {
    // Seed for random number generation
    std::srand(std::time(0));
    // Transition matrix for the weather example
    std::vector<std::vector<double>> transitionMatrix = {
        {0.8, 0.1, 0.1},  // Probabilities from Sunny to Sunny, Rainy, Cloudy
        {0.2, 0.6, 0.2},  // Probabilities from Rainy to Sunny, Rainy, Cloudy
        {0.3, 0.3, 0.4}   // Probabilities from Cloudy to Sunny, Rainy, Cloudy
    };
    // Initial state
    Weather currentState = Sunny;
    // Number of days to simulate
    int days = 10;
    // Simulate the Markov chain
    for (int day = 0; day < days; ++day) {
        std::cout << "Day " << day + 1 << ": ";
        switch (currentState) {
            case Sunny: std::cout << "Sunny"; break;
            case Rainy: std::cout << "Rainy"; break;
            case Cloudy: std::cout << "Cloudy"; break;
        }
        std::cout << std::endl;
        // Generate a random number between 0 and 1
        double randomValue = (double) std::rand() / RAND_MAX;
        // Determine the next state based on the transition probabilities
        double cumulativeProbability = 0.0;
        for (int nextState = 0; nextState < 3; ++nextState) {
            cumulativeProbability += transitionMatrix[currentState][nextState];
            if (randomValue < cumulativeProbability) {
                currentState = static_cast<Weather>(nextState);
                break;
            }
        }
    }
    return 0;
}

Output:

Day 1: Sunny
Day 2: Cloudy
Day 3: Cloudy
Day 4: Cloudy
Day 5: Sunny
Day 6: Sunny
Day 7: Sunny
Day 8: Sunny
Day 9: Sunny
Day 10: Rainy

Explanation:

• ✅ Step 1: Define the States Firstly, you need to define the possible states of your system. In this example, the states represent different types of weather: Sunny, Rainy, and Cloudy. Each state is assigned a unique identifier, often using an enumerated type (enum) for clarity and ease of use.
• ✅ Step 2: Create the Transition Matrix Next, you create a transition matrix. This matrix is a table that shows the probabilities of moving from one state to another. For instance if you're currently experiencing sunny weather, the matrix will indicate the likelihood of it remaining sunny, changing to rainy, or becoming cloudy the next day. Each row in this matrix represents a current state, and each column represents a potential next state.
• ✅ Step 3: Set the Initial State You then choose an initial state for your system. In this example, the simulation starts with sunny weather. This initial state serves as the starting point for the simulation.
• ✅ Step 4: Simulate the Markov Chain To simulate the Markov chain, follow these steps: Loop Through Each Day: The simulation runs for a predetermined number of days. Print Current State: For each day, display the current weather state. Generate a Random Number: Use a random number generator to produce a number between 0 and 1. This number will help determine the next state based on the transition probabilities. Determine the Next State: Compare the random number with the cumulative transition probabilities for the current state. The cumulative probability is calculated by summing the probabilities from the transition matrix until the random number falls within a specific range, indicating the next state. Update the State: Once the next state is determined, update the current state to this new state and proceed to the next day in the simulation.
• ✅ Loop Through Each Day: The simulation runs for a predetermined number of days.
• ✅ Print Current State: For each day, display the current weather state.
• ✅ Generate a Random Number: Use a random number generator to produce a number between 0 and 1. This number will help determine the next state based on the transition probabilities.
• ✅ Determine the Next State: Compare the random number with the cumulative transition probabilities for the current state. The cumulative probability is calculated by summing the probabilities from the transition matrix until the random number falls within a specific range, indicating the next state.
• ✅ Update the State: Once the next state is determined, update the current state to this new state and proceed to the next day in the simulation.

Complexity analysis:

Time Complexity

The time efficiency of a Markov chain simulation is mainly influenced by the quantity of iterations and the computations carried out in each iteration.

Initialization:

Defining different states and establishing the transition matrix occurs only once, making these operations O(1) complexity.

Simulation Loop:

• ✅ The loop runs for n iterations, where n is the number of time steps (or days in the weather example).
• ✅ Within each iteration, generating a random number and determining the next state involves:
• ✅ Generating a random number: O(1).
• ✅ Checking the transition probabilities: If there are m states, you may need to check up to m probabilities in the worst case. This is O(m).
• ✅ Overall, each iteration involves O(m) operations.
• ✅ Therefore, the total time complexity is O(n⋅m)

Space Complexity

The space complexity pertains to the amount of memory allocated for storing the states, the transition matrix, and any extra variables.

States:

• ✅ The quantity of states is denoted by m, which is usually a compact, constant value. As a result, the space complexity is O(m).

Transition Matrix:

• ✅ The transition matrix is a square matrix with dimensions m x m, necessitating storage space that scales with the square of the number of states. This complexity is denoted as O(m²).

Variables:

• ✅ Other variables encompass the present condition, arbitrary number, and total likelihood. These demand consistent memory allocation, O(1).
• ✅ Consequently, the overall spatial efficiency amounts to: O(m2)

Approach 2: Using Classes and Object-Oriented Programming

Organize the Markov Chain functionality within a class to enhance modularity and reusability. This strategy enhances code cleanliness and simplifies maintenance.

Implementation:

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
class State {
public:
    int id;
    std::vector<double> transitions;
    State(int id, std::vector<double> trans) : id(id), transitions(trans) {}
};
class MarkovChain {
private:
    std::vector<State> states;
    int currentState;
public:
    MarkovChain(std::vector<State> st, int initialState) : states(st), currentState(initialState) {}
    void simulate(int days) {
        std::srand(std::time(0));
        for (int day = 0; day < days; ++day) {
            std::cout << "Day " << day + 1 << ": State " << currentState << std::endl;
            double randomValue = (double) std::rand() / RAND_MAX;
            double cumulativeProbability = 0.0;
            for (int i = 0; i < states[currentState].transitions.size(); ++i) {
                cumulativeProbability += states[currentState].transitions[i];
                if (randomValue < cumulativeProbability) {
                    currentState = i;
                    break;
                }
            }
        }
    }
};
int main() {

    std::vector<State> states = {
        State(0, {0.8, 0.1, 0.1}), // State 0 transitions
        State(1, {0.2, 0.6, 0.2}), // State 1 transitions
        State(2, {0.3, 0.3, 0.4})  // State 2 transitions
    };
    MarkovChain mc(states, 0);
    mc.simulate(10);
    return 0;
}

Output:

Day 1: State 0
Day 2: State 0
Day 3: State 0
Day 4: State 0
Day 5: State 2
Day 6: State 2
Day 7: State 0
Day 8: State 0
Day 9: State 0
Day 10: State 2

Explanation:

• ✅ Step 1: Define the State Class Create a State Class: The State class represents a single state in the Markov chain. Each state has an identifier (id) and a list of transition probabilities (transitions). The transition probabilities are stored in a vector where each element corresponds to the probability of moving to a specific state from the current state.
• ✅ Step 2: Define the MarkovChain Class Create a MarkovChain Class: The MarkovChain class manages the states and the transitions between them. It contains a list of State objects and keeps track of the current state of the chain. Initialize the MarkovChain Class: The constructor of the MarkovChain class takes a vector of State objects and an initial state. This sets up the initial configuration of the Markov chain.
• ✅ Step 3: Simulate the Markov Chain Simulation Method: The simulation method of the MarkovChain class simulates a specified number of days. It uses a loop to iterate through each day of the simulation. Print the Current State: Within each iteration (each day), the current state of the system is printed. Generate a Random Number: A random number between 0 and 1 is generated to determine the next state based on the transition probabilities. Determine the Next State: The method iterates through the list of transition probabilities for the current state. It accumulates these probabilities until the random number falls within a specific range, indicating the next state. The current state is then updated to this next state.

Complexity analysis:

Time Complexity:

The time complexity of the simulation is primarily influenced by the quantity of states (m) and the total number of iterations (n) that are being simulated.

Initialization:

Generating the State instances and setting up the MarkovChain object requires looping through the states and configuring data structures. This process generally operates at O(m) complexity, with 'm' representing the count of states.

Simulation Loop:

The simulation operates over n iterations, with each iteration corresponding to a day or a time step.

During each iteration, the process of updating the present state includes cycling through the transition probabilities associated with that state. In the worst-case scenario, this task has a time complexity of O(m), where m represents the total number of states in the system.

Thus, the total time complexity for simulating n days is: O(n⋅m)

Space Complexity:

The space complexity pertains to the amount of memory allocated for storing states, transition probabilities, and any other variables required.

States:

The amount of storage space needed to hold m State objects is influenced by the characteristics of each state, such as its identifier and transition probabilities. This storage requirement is O(m) in size.

Transition Probabilities:

Each State object includes an array or vector that stores transition probabilities to other states. In cases where the state space is densely populated with numerous transitions per state, this data structure may occupy a considerable amount of memory.

Current State and Variables:

Extra memory is essential for variables such as the present state index and any temporary variables employed in the simulation loop. This usually amounts to O(1) space complexity.

Thus, the overall space complexity is mainly influenced by the state entities and their transition information, estimated at: O(m)

Approach 3: Using Dynamic State Space with Hash Maps

When dealing with scenarios where the state space is constantly changing or exceptionally vast, employing hash maps can offer superior efficiency.

Implementation:

#include <iostream>
#include <unordered_map>
#include <cstdlib>
#include <ctime>
int main() {
    std::srand(std::time(0));
    // Transition matrix using nested unordered_map
    std::unordered_map<std::string, std::unordered_map<std::string, double>> transitionMatrix;
    transitionMatrix["Sunny"]["Sunny"] = 0.8;
    transitionMatrix["Sunny"]["Rainy"] = 0.1;
    transitionMatrix["Sunny"]["Cloudy"] = 0.1;
    // Add remaining transitions...
    std::string currentState = "Sunny";
    int days = 10;
    for (int day = 0; day < days; ++day) {
        std::cout << "Day " << day + 1 << ": " << currentState << std::endl;
        double randomValue = (double) std::rand() / RAND_MAX;
        double cumulativeProbability = 0.0;
        for (const auto& transition : transitionMatrix[currentState]) {
            cumulativeProbability += transition.second;
            if (randomValue < cumulativeProbability) {
                currentState = transition.first;
                break;
            }
        }
    }
    return 0;
}

Output:

Day 1: Sunny
Day 2: Sunny
Day 3: Sunny
Day 4: Sunny
Day 5: Sunny
Day 6: Cloudy
Day 7: Cloudy
Day 8: Cloudy
Day 9: Cloudy
Day 10: Cloudy

Explanation:

• ✅ Step 1: Define States Dynamically Use of Hash Maps: Instead of predefined enums or integers, states are represented dynamically using strings or other identifiers. Each state is stored as a key in a hash map (std::unordered_map), allowing for efficient lookup and management.
• ✅ Step 2: Create a Transition Matrix with Nested Hash Maps Transition Matrix: Use a nested std::unordered_map to represent the transition probabilities. The outer hash map maps each state (key) to an inner hash map. The inner hash map maps each possible next state to its corresponding transition probability.
• ✅ Step 3: Simulation Process Initialize States and Transitions: Populate the outer hash map with states and their respective transition probabilities. This can be done dynamically as states and transitions are defined or updated. Run the Simulation: Iterate over a specified number of days or time steps. For each iteration: Print or record the current state. Use random number generation to select the next state based on transition probabilities stored in the hash maps. Update the current state accordingly.

Complexity analysis:

Time Complexity

The time complexity of the simulation is mainly influenced by the quantity of states (m) and the number of iterations (n) involved in the simulation process.

Initialization:

Introducing states and setting up the transition probabilities requires adding entries into hash tables. This process generally maintains an average time complexity of O(1) for insertion.

If states and transitions are set up dynamically at runtime, the complexity could fluctuate depending on the insertion processes.

Simulation Loop:

The simulation operates for a number of iterations denoted as n, with each iteration corresponding to a specific time increment such as days.

Within each iteration:

Accessing the present condition from the hash map typically has an average time complexity of O(1).

Calculating a random number and deciding the subsequent state requires iterating through the transition probabilities associated with the current state.

Updating the existing state using the chosen subsequent state also demands an average constant time complexity of O(1).

Consequently, the time complexity for simulating a span of n days with m states is represented as: O(n⋅(1+k))

Where k represents the mean quantity of state transitions.

Space Complexity:

The space complexity encompasses the memory allocated for storing states, transition probabilities, and any other necessary variables.

States:

Each individual state is saved as a key within the outer hash map, necessitating storage that scales in proportion to the total number of states, denoted as O(m).

Transition Probabilities:

Transition probabilities assigned to each state are stored within the inner hash maps.

If the state space contains numerous transitions per state, the memory occupied by the hash maps may expand considerably.

In the most unfavorable scenario, where each state is connected to every other state, the space complexity related to transition probabilities could reach up to O(m^2).

Additional Variables:

Variables like the current index of the state and temporary variables utilized within the simulation loop demand consistent space of O(1).

Therefore, the overall space complexity is mainly influenced by the states and their transition information, which amounts to: O(m+m2).