Random Walk On Markov Chain Transition Matrix

I have a cumulative transition matrix and need to build a simple random walk algorithm to generate let's say 500 values from the matrix as efficiently as possible (the actual matri

Solution 1:

You can use numpy random choice at each stage to simulate a transition.

You can give the probability as the argument p, and the first positional argument define the sample space. In order to convert the cumulative probability distribution to a probability distribution what I do is to insert a zero at the beginning and use numpy diff to compute the increase at each step.

Preparing your example probabilities

P = np.array([
    [0.3, 0.5, 0.7, 0.9, 1. ],
    [0.5 , 0.5 , 0.5 , 0.75, 1.  ],
    [0.66666667, 1.        , 1.        , 1.        , 1.        ],
    [0.4, 0.6, 0.8, 1. , 1. ],
    [0.5, 0.5, 0.5, 1. , 1. ]])
P = np.diff(np.hstack([np.zeros((len(P), 1)), P]), axis=1)

Then run a few steps

i = 0;
path = [0]
I = np.arange(len(P))
for _ inrange(10):
    i = np.random.choice(I, p = P[i])
    path.append(i);
print(path)