** Continuous Time Markov Chain (Continuous Time Markov Chain) state transition simulation is implemented. The algorithm used is the Gillespie Algorithm. After posting the implementation, I will briefly explain the outline.
** Discrete time ** For the Markov chain state transition simulation, refer to this article. Python --Markov chain state transition simulation
Consider a Markov chain in the case of three states (state = 0,1,2).
CTMC.py
import numpy as np
import math
import random
import matplotlib.pyplot as plt
#Number of states
N=3
#Transition rate matrix
TRANSITION_MATRIX = [[-0.3, 0.1, 0.2],
[0.2, -0.9, 0.7],
[0.7, 0.2, -0.9]]
initial_state = 0 #initial state
current_state = initial_state #Current state
next_state = 0 #Next state
dt = 0 #State stay time
state_list = [] #State storage list
dt_list=[] #Storage list of staying time
state_list.append(current_state)
dt_list.append(dt)
time = 0
T=15 #Observation time
#Gillespie algorithm(Gillespie Algorithm)
while(time <= T):
rand_s = random.random() #Random numbers that determine the state
rand_t = random.random() #Random number that determines the length of stay
q = -TRANSITION_MATRIX[current_state][current_state] #propensity function
total = 0
#Determine the next transition state
for i in range(N):
if(i == current_state):
continue
total += TRANSITION_MATRIX[current_state][i]
if(rand_s < total/q):
next_state = i
break;
current_state = next_state
state_list.append(current_state)
#Determine the length of stay in the current state
dt = 1/q * math.log(1/rand_t)
time += dt
dt_list.append(dt)
#plot
arr_state = np.array(state_list)
arr_dt = np.array(dt_list)
arr_cumsum = np.cumsum(arr_dt)
arr_state_repeat = np.repeat(arr_state,2)
arr_time_repeat = np.repeat(arr_cumsum,2)
plt.plot(arr_time_repeat[1:],arr_state_repeat[:-1],label="state")
plt.xlabel("time")
plt.ylabel("state")
plt.title("DTMC")
plt.legend()
plt.grid(color='gray')
It is a graph of the result.
It can be seen that the transition is repeated between the states [0,1,2] until time T = 15. (In this graph, it transitions to around 17.5, but this is a specification. It can be removed by removing the end of the list, but it is not removed here because the code becomes complicated. )
The main idea of this algorithm is according to the transition rate