Markov Processes

From bio-physics-wiki

Jump to: navigation, search

Random events in simple probability theory are usually independent of each other. Considering a die, the probability to roll a $6$ is independent of the number rolled before. Thus the probability of a sequence of events satisfies the multiplicative property. Markovian Processes represent a generalisation of these independent processes by allowing the future state to depend on the current state. Therefore, we introduce the conditional probability that, when the current state at time $t_1$ is given by the enseble of varibles $\{a_1 \}$, the state $\{ a_2 \}$ at time $t_2$ is reached. \begin{align} P_{1|1}( \{a_2 \}t_2 | \{ a_1\}t_1) \end{align} $P_{1|1}$ is called a stochastic matrix, its entries are the transition probabilities from $\{a_1 \}t_1$ to $\{ a_2\}t_2$. $P_{1|1}$ has the property that the sum over the transition probabilities of each row gives \begin{align} \sum_{ \{a_2 \}} P_{1|1}( \{a_2 \}t_2 | \{ a_1\}t_1)=1 \end{align}

Definition
In a Markov Process the current probability distribution $P_1(\{ a_1\}t_1)$ and the stochastic Matrix $P_{1|1}( \{a_2 \}t_2 | \{ a_1\}t_1)$ uniquely define the probability distribution $P_2(\{a_2 \}t_2;\{ a_1\}t_1)$. In other words $P_{1|1}$ contains all the necessary information of the process. Note, the 'memory' of the system is restricted to only one step backwards. \begin{align} P_2(\{a_2 \}t_2;\{ a_1\}t_1)&=P_{1|1}(\{a_2 \}t_2|\{ a_1\}t_1) \cdot P_1(\{ a_1\}t_1) \end{align}


Example: To illustrate this definition let us discuss the Random Walk problem, which in its essence is a Markovian Process. For simplicity we assume that only $N=10$ discrete positions $i=1,2,\dots ,10$ are available for the molecule and devide the distance $a$ (where the molecule is allowed to walk) by $N-1=9$. At time $t_1$ the particle is placed at a certain initial position characterised by $\{a_1\}$. The particle can then jump to the left with probability $p$ and to the right with probability $q$. We assume that once the particle reaches position $0$ or $a$ it is absorbed by the boundary and cannot leave the position anymore. The matrix $P_{1|1}$ is then given by \begin{align} P_{1|1}= \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ p & 0 & q & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & p & 0 & q & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & p & 0 & q & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & p & 0 & q & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & p & 0 & q & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & p & 0 & q & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & p & 0 & q & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & p & 0 & q \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix} \end{align} Say one particle sits initially at position $i=5$, then $\{a_1\}$ is given by $\{0,0,0,0,1,0,0,0,0,0\}$ and the probability distribution $P_1(\{ a_1\}t_1)=(0,0,0,0,1,0,0,0,0,0)^T$, so the particle sits at $i=5$ with probability $1$. Given this information we can calculate $P_2(\{a_2 \}t_2;\{ a_1\}t_1)$. \begin{align} \begin{pmatrix} 0 \\ 0\\ 0\\ p\\ 0\\ q\\ 0\\ 0\\ 0\\ 0 \end{pmatrix}= \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ p & 0 & q & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & p & 0 & q & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & p & 0 & q & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & p & 0 & q & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & p & 0 & q & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & p & 0 & q & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & p & 0 & q & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & p & 0 & q \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} 0 \\ 0\\ 0\\ 0\\ 1\\ 0\\ 0\\ 0\\ 0\\ 0 \end{pmatrix} \end{align} At a later time step $t_3$ the transition probability $P_3(\{a_3 \}t_3;\{a_2 \}t_2;\{ a_1\}t_1)$ is given by \begin{align} \begin{pmatrix} 0 \\ 0\\ pq\\ 0\\ p^2+q^2\\ 0\\ qp\\ 0\\ 0\\ 0 \end{pmatrix}= \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ p & 0 & q & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & p & 0 & q & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & p & 0 & q & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & p & 0 & q & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & p & 0 & q & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & p & 0 & q & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & p & 0 & q & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & p & 0 & q \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} 0 \\ 0\\ 0\\ p\\ 0\\ q\\ 0\\ 0\\ 0\\ 0 \end{pmatrix} \tag{1} \end{align} Notice, that by the Binomial Theorem the elements of $P_n$ always sum up to $1$. In a more abstract notation we can write (1) as \begin{align} P_3(\{a_3 \}t_3;\{a_2 \}t_2;\{ a_1\}t_1)&= P_{1|1}(\{a_3 \}t_3 | \{ a_2\}t_2 ) \cdot P_{1|1}(\{a_2 \}t_2 | \{ a_1\}t_1 ) \cdot P_1(\{ a_1\}t_1) \\ &= P_{2|1}(\{a_3 \}t_3|\{ a_2\}t_2;\{ a_1\}t_1| ) \cdot P_2(\{a_2 \}t_2;\{ a_1\}t_1) \end{align} we recognise the following property of Markov Processes

\begin{align} P_{2|1}(\{a_3 \}t_3 | \{ a_2\}t_2;\{ a_1\}t_1 )=P_{1|1}(\{a_3 \}t_3 | \{ a_2\}t_2 ) \end{align} Proceeding with the algorithm to get transition probabilities for following times $t_4,t_5, \dots t_n$ we see that the general argument \begin{align} P_{1|n-1}(\{a_n \}t_n;\{ a_{n-1}\}t_{n-1}; \dots ; | \{a_2 \}t_2;\{ a_1\}t_1)=P_{1|1}(\{ a_{n-1}\}t_{n-1}| \{a_n \}t_n) \tag{2} \end{align} is true. This equation restates the fact, that one $P_{1|1}(\{ a_{n-1}\}t_{n-1}| \{a_n \}t_n)$ contains all the necessary information of the markov process (and is independent of preceeding transition probabiliteis $\{ a_1\}t_1;\{a_2 \}t_2 ; \dots$) and that given an initial PDF, the transition probability at all future times can be calculated.


Statonary Markov Processes

The above discussed example, satisfies not only (2), the transition probability also does not explicitly depend on time $P(\{ a_1\}t_1)=P(\{ a_1\})$. The probabilities $p,q$ and hence $P_{1|1}(\{ a_1\}t_1|\{a_n \}t_n)$ only depend on the time difference $\Delta t =t_2-t_1$, but not on time explicitly. Such processies are called Stationary Markov Processies (not to confuse with a stationary random process). We can thus write the transition probability as \begin{align} P_{1|1}(\{ a_1\}t_1|\{a_n \}t_n)=P_{1|1}(\{ a_1\}|\{a_2 \},(t_2-t_1))=P_{1|1}(\{ a_1\}|\{a_2 \},\Delta t) \end{align} and arrive at the Chapman-Kolmogorov equation \begin{align} P_2(\{ a_1\}|\{a_2 \}, t)=\sum_{\{ a\}} P_{1|1}(\{ a\}|\{a_2 \},\Delta t)\, \cdot \,P_{2}(\{ a_1\}|\{a \},t-\Delta t) \end{align} which gives the probability $P_2$ that given a state $\{ a_1\}$, $\{ a\}$ and then $\{ a_2\}$ is reached during $\Delta t$, by summing over all possible ways $\{ a\}$.