Skip to content

Instantly share code, notes, and snippets.

@Kevinpgalligan
Created August 28, 2022 14:56
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save Kevinpgalligan/8c1065e1c7f61caf7d048d96e3c5076f to your computer and use it in GitHub Desktop.
J code for analysing Markov processes.
NB. Functions for analysing Markov processes through
NB. their transition matrices.
NB. Takes transition matrix as x, number of rounds as y.
calcMarkovDistribution =: dyad define
P =. x
n =. # P
matmul =. +/ . *
((] ,. ((P&matmul @: ,. @: ({:"1))) ) ^: y) ,. 1 , (n-1)$0
)
NB. Takes transition matrix as y, returns average steps to end
NB. up in an absorbing state, from each non-absorbing state.
NB. Reference: Understanding Probability.
NB. (Although, it doesn't show how to express the equations
NB. in matrix form, I had to do that myself).
calcAvgMarkovSteps =: monad define
P =. y
NB. Find absorbing states.
Sa =. I. (1: = {{ (< y ; y) { P }})"0 i. (# P)
if. 0 = (# Sa) do.
NB. If there are no absorbing states, the process will
NB. continue forever. So return infinity for all states.
(# P) $ _ return.
end.
NB. Extract submatrix with probabilities of non-absorbing states.
S =. (i. (# P)) -. Sa
Ps =. (< S ; S) { Ps
I =. e. i. (# Ps)
result =. (# P) $ 0
NB. Add average steps for non-absorbing states to the result!
NB. Comes from the equation (Ps^T-I)[u] = [-1], where [u] is the
NB. average from each non-absorbing state.
(((# Ps) $ _1) %. ((|: Ps) - I)) (S }) result
)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment