Markov Chain

What is it?

In Probability and Reinforcement Learning, a Markov Chain represents dynamic stochastic processes which changes with time, which assumes the Markov Property. Markov Chains care about the states of an environment, instead of performing actions (this is the job for the Markov Decision Process.

---

How does it work?

Given a set of states $q_1,q_2,\dots ,q_n$ , which the transition between states are non-deterministic and stochastic, the probability of transitioning from current state $q_i$ to $q_j$ is:

$$P(S_t=q_j|S_{t-1}=q_j)$$

Given also : a vector of probabilities of occurrence of each state $\Gamma =\{{\gamma }_1,{\gamma }_2,\dots ,{\gamma }_n\}$, where ${\gamma }_i=P(S_o=q_i)$ and; a matrix of transition probabilities (probabilities of change from a state to another) $A=\{a_{ij}\},i=[1\dots n],j=[1\dots n]$ and $a_{ij}=P(S_t=q_j|S_{t-1}=q_i)$;

One can model a Markov Chain similar to the one in the image above.