0
$\begingroup$

I am trying to learn a little bit of Markov Chains through Dobrow's "Introduction to Stochastic Processes with R", but i am struggling with the following:

The entries of every Markov transition matrix P are nonnegative, and each row sums to 1.

I am trying to understand why the rows sum to 1. The author argues as follows: $$ \sum_{j} P_{i j}=\sum_{j} P\left(X_{1}=j \mid X_{0}=i\right)=\sum_{j} \frac{P\left(X_{1}=j, X_{0}=i\right)}{P\left(X_{0}=i\right)} $$

Finally, since (I can't figure out the first equality below) $$ \sum_{j} \frac{P\left(X_{1}=j, X_{0}=i\right)}{P\left(X_{0}=i\right)}=\frac{P\left(X_{0}=i\right)}{P\left(X_{0}=i\right)}=1 $$ the results follows.

What have i tried so far? Since $$ P\left(X_{1}=j \mid X_{0}=i\right)P\left(X_{0}=i\right) = P\left(X_{1}=j, X_{0}=i\right) $$

we have that: $$\sum_{j} \frac{P\left(X_{1}=j, X_{0}=i\right)}{P\left(X_{0}=i\right)} = \sum_{j} P\left(X_{1}=j \mid X_{0}=i\right)$$

and the last sum should equal 1, but i cannot argue as to why that is true. I am afraid i am missing something simple.

Observations: $P_{ij} = P\left(X_{1}=j \mid X_{0}=i\right)$ and the Markov Chain is discrete and time-homogeneous.

Can someone help? Thanks in advance, Lucas

$\endgroup$
1
$\begingroup$

Finally, since (I can't figure out the first equality below) $$ \sum_{j} \frac{P\left(X_{1}=j, X_{0}=i\right)}{P\left(X_{0}=i\right)}=\frac{P\left(X_{0}=i\right)}{P\left(X_{0}=i\right)}=1 $$

$$ \sum_{j} \frac{P\left(X_{1}=j, X_{0}=i\right)}{P\left(X_{0}=i\right)}= \frac{\sum_{j}P\left(X_{1}=j, X_{0}=i\right)}{P\left(X_{0}=i\right)} =\frac{P\left(X_{0}=i\right)}{P\left(X_{0}=i\right)}=1 $$

If the rows sum up to 1 then $\sum_{j}P\left(X_{1}=j, X_{0}=i\right) = P\left(X_{0}=i\right)$


The reason why each row (or each column depending on how you consider the matrix) needs to sum up to 1 is because in this way the total probability (which needs to sum up to 1) remains preserved.

Example:

For

$$(\tilde{p}_1,\tilde{p}_2,\tilde{p}_3) = \left( p_1,p_2,p_3 \right) \cdot\left( \begin{array}{} t_{1,1} & t_{2,1} & t_{3,1} \\ t_{1,2} & t_{2,2} & t_{3,2} \\ t_{1,3} & t_{2,3} & t_{3,3} \\ \end{array} \right)$$

You have

$$\tilde{p}_1+\tilde{p}_2+\tilde{p}_3 = \underbrace{p_1\cdot t_{1,1} + p_2\cdot t_{1,2} + p_3\cdot t_{1,3}}_{\tilde{p}_1} + \underbrace{p_1\cdot t_{2,1} + p_2\cdot t_{2,2} + p_3\cdot t_{2,3}}_{\tilde{p}_2} + \underbrace{p_1\cdot t_{3,1} + p_2\cdot t_{3,2} + p_3\cdot t_{3,3}}_{\tilde{p}_3}$$

a rearrangement of terms gives

$$\tilde{p}_1+\tilde{p}_2+\tilde{p}_3 = p_1 \cdot \underbrace{ (t_{1,1}+t_{2,1}+t_{3,1})}_{\text{sum of 1st row}} + p_2 \cdot \underbrace{ (t_{1,2}+t_{2,2}+t_{3,2})}_{\text{sum of 2nd row}} + p_3 \cdot \underbrace{ (t_{1,3}+t_{2,3}+t_{3,3})}_{\text{sum of 3rd row}} $$

If the rows sum up to 1, and if $p_1+p_2+p_3$ sums up to 1, then this becomes

$$\tilde{p}_1+\tilde{p}_2+\tilde{p}_3 = p_1 + p_2 + p_3 = 1 $$

Intuition:

The transition frequencies/rates in the $i$-th row describe where the present amount of $p_i$ will be distributed among the new vector. If these transition rates sum up to 1 then this means that the sum of the amounts of probability distributed in the new vector per amount of probability $p_i$ is exactly equal to $p_i$. Thus there is no probability created or destroyed during the transition.

For every $p_i$ there will be the terms $p_i \cdot t_{j,i}$ in the final sum. When the $t_{j,i}$ sum up to 1 (for all different $j$, which is the different terms in a row) then we know that for every $p_i$ there will be the same amount in the sum of the $\tilde p_i$ (but redistributed according to the $t_{j,i}$).

Simple analogy

Say you have three bins filled with water. Every transition step you redistribute the water from the bins according to some redistribution formula. This redistribution formula describes which fraction of bin '1' goes to bins '2','3' and which fraction remains in bin '1'; which fraction of bin '2' goes to bins '1','3' and which fraction remains in bin '2'; which fraction of bin '3' goes to bins '1','2' and which fraction remains in bin '3'.

Say, if you have x Liters in bin '1' then the amount that you redistribute from bin '1' into other bins needs to sum up to those x liters.

For instance, if you have x Liters of water in bin '1', then you can not put x liters from bin '1' into bin '2' and put x liters from bin '1' into '3'. This would mean that you got 2 times x liters of water from bin '1' while it only contained x liters.

$\endgroup$
2
  • $\begingroup$ Nice! But i am afraid i am missing something. What does \left(\tilde{p}_{1}, \tilde{p}_{2}, \tilde{p}_{3}\right) exactly stands for? Also, what did you think of my approach? Is there any way of finishing my reasoning? $\endgroup$
    – Lucas
    Nov 19 '20 at 15:00
  • 1
    $\begingroup$ @Lucas the $\tilde{}$ denotes the next/transformed vector. I think your reasoning is correct (and also elegant). I have handled your question at the beginning of my answer. This is how you can figure out the first equality $$\sum_{j} \frac{P\left(X_{1}=j, X_{0}=i\right)}{P\left(X_{0}=i\right)}= \frac{\sum_{j}P\left(X_{1}=j, X_{0}=i\right)}{P\left(X_{0}=i\right)} =\frac{P\left(X_{0}=i\right)}{P\left(X_{0}=i\right)}=1$$ The rest, the longer story, is how I intuitively think of it. $\endgroup$ Nov 19 '20 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.