CODEWITHSUNDEEP
pythonmarkov-chains
NiPapen
NiPapen

Reputation: 95

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 matrix is 1000 x 1000)

cum_sum

[array([0.3, 0.5, 0.7, 0.9, 1. ]),
array([0.5 , 0.5 , 0.5 , 0.75, 1.  ]),
array([0.66666667, 1.        , 1.        , 1.        , 1.        ]),
array([0.4, 0.6, 0.8, 1. , 1. ]),
array([0.5, 0.5, 0.5, 1. , 1. ])]

  1. Select the initial state i in the matrix randomly

  2. Produce a random value between 0 and 1

  3. The value of the random number is compared with the elements of the i-th row of the cumulative matrix. If the random number value was greater then the cumulative probability of the previous state but less than or equal to the cumulative probability of the following state the followin state is adopted.

Something I tried

def random_walk(cum_sum):
start_point=random.choice([item[0] for item in cum_sum])
random=np.random.uniform(0,1,1)
if random > start_point:

Upvotes: 0

Views: 1578

Answers (1)

Bob
Bob

Reputation: 14654

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 _ in range(10):
    i = np.random.choice(I, p = P[i])
    path.append(i);
print(path)

Upvotes: 3

Related Questions