CODEWITHSUNDEEP
algorithmmath
Evo510
Evo510

Reputation: 173

Most efficient Markov Chain algorithm

My current side project requires the use of a 3x3x3 Markov Chain. The first implementation I came up with is to have each position in the matrix be the chance to move to that position (where the values of all positions sum to 1). Depending on the values in the matrix this would lead to:

My next idea would be to store the sum of each row and layer as an extra class variable array. This would allow it to find the correct position in:

We can see already this is a much better implementation comparison wise but also has some extra data that it needs to store.

Is there a better way to implement this?

Upvotes: 0

Views: 282

Answers (1)

Stochastically
Stochastically

Reputation: 7846

A Markov chain evolves via a transition matrix, which would presumably be a 27x27 matrix in your case. However, the way you ask the question implies that you're not dealing with the general case, and that there are some special conditions that apply.

If I was going this, my first thought would be that computers these days are so fast that it's not worth worrying about efficiency for an initial version, and that it's better to get some preliminary results. So I'd only start worrying about efficiency for a subsequent version. In particular, your more efficient version is obviously going to be a bit harder to get right, and perhaps a bit dangerous in case some of your saved variables get out of sync with the underlying state of your Markov chain. So an important tool to test such a more efficient implementation would be the brute force inefficient implementation that you first thought of.

Upvotes: 1

Related Questions