# Chapter 2 Exercises
In this notebook we will go through the exercises of chapter 2 of Introduction to Stochastic Processes with R by Robert Dobrow.


```python
import numpy as np
```

## 3.1
Consider a Markov chain with transition Matrix
$$P=\left(\begin{array}{cc}
1/2 & 1/4 & 0 & 1/4 \\
0 & 1/2 & 1/2 & 0\\
1/4 & 1/4 & 1/2 & 0 \\
0 & 1/4 & 1/2 & 1/4
\end{array}\right)$$
Find the stationary distribution without using technology

### Answer
We have 5 equations with 4 variables:
$$\begin{align}
1/2 \pi_1 +1/4\pi_3 &= \pi_1 \\
1/4 \pi_1 +1/2\pi_2+1/4\pi_3+1/4\pi_4 &= \pi_2 \\
1/2\pi_2+1/2\pi_3+1/2\pi_4 &= \pi_3 \\
1/4 \pi_1 +1/4\pi_4 &= \pi_4 \\
\pi_1+\pi_2+\pi_3+\pi_4=1
\end{align}$$
$=>$
$$\begin{align}
\pi_1  &= 3\pi_4 \\
\pi_3 &= 6\pi_4 \\
\pi_2 &= 5\pi_4 \\
\pi_4 &= 1/15 \\
\pi_2 &= 1/3 \\
\pi_3 &= 2/5 \\
\pi_1 &= 1/5 \\
\end{align}$$
then $\pi = (1/5, 1/3, 2/4, 1/15)$


```python
pi = np.array([1/5, 1/3, 2/5, 1/15])
P = np.matrix([[1/2 , 1/4 , 0 , 1/4],
[0 , 1/2 , 1/2 , 0],
[1/4 , 1/4 , 1/2 , 0],
[0 , 1/4 , 1/2 , 1/4]])
pi*P, pi
```




    (matrix([[0.2       , 0.33333333, 0.4       , 0.06666667]]),
     array([0.2       , 0.33333333, 0.4       , 0.06666667]))



## 3.2
A stochastic matrix is called *doubly stochastic* if its rows and columns sum to 1. Show that a Markov chain whose transition matrix is doubly stochastic has a stationary distribution, which is uniform on the state space.

### Answer
Let's remember that then the distribution at $X_n$ is $\alpha P^n$, let's see what happens at $n=1$

$n=1$
$$X_1=\alpha P = \left(\begin{array}{cc}
1/k &1/k&...& 1/k
\end{array}\right)\left(\begin{array}{cc}
p_{1,1} & p_{1,2} & ... & p_{1,k} \\
p_{2,1} & p_{2,2} & ... & p_{2,k} \\
...  \\
p_{k,1} & p_{k,2} & ... & p_{k,k} \\
\end{array}\right)=\left(\begin{array}{cc}
p_{1,1}*1/k + p_{2,1}*1/k + ... + p_{k,1}*1/k \\
p_{1,2}*1/k + p_{2,2}*1/k + ... + p_{k,2}*1/k \\
...  \\
p_{1,k}*1/k + p_{2,k}*1/k + ... + p_{k,k}*1/k \\
\end{array}\right)^T=\left(\begin{array}{cc}
(p_{1,1} + p_{2,1} + ... + p_{k,1})*1/k\\
(p_{1,2} + p_{2,2} + ... + p_{k,2})*1/k \\
...  \\
(p_{1,k} + p_{2,k} + ... + p_{k,k})*1/k \\
\end{array}\right)^T = \left(\begin{array}{cc}
(1)*1/k\\
(1)*1/k \\
...  \\
(1)*1/k \\
\end{array}\right)^T=\alpha
$$
This last step is due to the matrix being double stochastic

## 3.3
Consider a Markov chain with transition Matrix. Determine if they are regular.
$$P=\left(\begin{array}{cc}
0.4 & 0.6 & 0 & 0 \\
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0
\end{array}\right)$$


$$Q=\left(\begin{array}{cc}
0 & 1 \\
p & 1-p 
\end{array}\right)$$


$$R=\left(\begin{array}{cc}
0 & 1 & 0 \\
0.25 & 0.5 & 0.25 \\
1 & 0 & 0 
\end{array}\right)$$

### Answer
Since all the values have probability of existing in matrices P and R at all times, then these are regular. For $Q$ then it is regular for $0<p<1$ since when this happens the movement is certain and when $p=0$, it does not change from state 2.

## 3.4
Consider the Markov Chain with transition Matrix:
$$R=\left(\begin{array}{cc}
1-a & a & 0 \\
0 & 1-b & b \\
c & 0 & 1-c 
\end{array}\right)$$
with $0< a,b,c <1$. Find the stationary distribution

### Answer
We have 4 equations with 3 variables:
$$\begin{align}
(1-a) \pi_1 + c \pi_3 &= \pi_1 \\
(1-b)\pi_2+a\pi_1 &= \pi_2 \\
b \pi_2 +(1-c)\pi_3 &= \pi_3 \\
\pi_1+\pi_2+\pi_3=1
\end{align}$$
$=>$
$$\begin{align}
\pi_3  &= a/c\pi_1 \\
\pi_2 &= a/b\pi_1 \\
\pi_1+a/b\pi_1+a/c\pi_1 &= 1 \\
=>  \\
\pi_1 &= \frac{bc}{ab+ac+bc} \\
\pi_2 &= \frac{ac}{ab+ac+bc} \\
\pi_3 &= \frac{ab}{ab+ac+bc} \\
\end{align}$$
then $\pi = (\frac{bc}{ab+ac+bc}, \frac{ac}{ab+ac+bc}, \frac{ab}{ab+ac+bc})$


```python
# An example with a=0.4, b=0.2, c=0.7
pi = np.array([.2*.7/(.4*.2+.2*.7+.4*.7), .4*.7/(.4*.2+.2*.7+.4*.7), .2*.4/(.4*.2+.2*.7+.4*.7)])
P = np.matrix([
[.6 , .4 , 0],
[0 , .8 , .2 ],
[.7 , 0 , .3]])
pi*P, pi
```




    (matrix([[0.28, 0.56, 0.16]]), array([0.28, 0.56, 0.16]))



## 3.5
Consider a Markov chain with transition Matrix
$$P=\left(\begin{array}{cc}
0 & 1/4 & 0 & 0 & 3/4 \\
3/4 & 0 & 0 & 0 & 1/4\\
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 \\
1/4 & 3/4 & 0 & 0 & 0
\end{array}\right)$$
(a) Describe the set of the stationary distributions for  the chain.

(b) Use technology to find the $lim_{n\to \infty}P^n$. Explain the long-term behavior of the chain.

(c) Explain why the chain does not have a limiting distribution, and why this does not contradict the existence of a limiting matrix as in (b)

### Answer
(a)

There is the same probability of catching into state 1,2 and 5 (because of the transition matrix is a double stochastic matrix), so the set of all stationary distributions are:
$(a,a,b,c,a)$ where 3a+b+c=1, although it is necessary to state that you can never reach any other state if you start at state b or c so if you start on this states then these are 1 since you do not move on those states.


```python
# (b)
P = np.matrix([[0 , 1/4 , 0 , 0 , 3/4],
[3/4 , 0 , 0 , 0 , 1/4],
[0, 0 , 1 , 0 , 0],
[0, 0 , 0 , 1 , 0],
[1/4 , 3/4 , 0 , 0 , 0]])
P**100
```




    matrix([[0.33333333, 0.33333333, 0.        , 0.        , 0.33333333],
            [0.33333333, 0.33333333, 0.        , 0.        , 0.33333333],
            [0.        , 0.        , 1.        , 0.        , 0.        ],
            [0.        , 0.        , 0.        , 1.        , 0.        ],
            [0.33333333, 0.33333333, 0.        , 0.        , 0.33333333]])



This means that if the chain starts at state 3 or 4, then you are stuck in there, whereas if you start on position 1,2 or 5, then you can be at any of these 3 states in a probability of 1/3 (since the matrix is a double stochastic matrix)

(c) There is no limit distribution since the limit distribution will bepend on which state you start on, but there is an stationary matrix because it shows you the limiting distribution for starting at state x (with x=1,2,3,4 or 5). This is because there exist 3 different commuinication classes.

## 3.6 
Consider a Markov Chain with transition matirx
$$P=\left(\begin{array}{cc}
1/2 & 1/2 & 0 & 0 & .. \\
2/3 & 0 & 1/3 & 0 & ..\\
3/4 & 0 & 0 & 1/4 & .. \\
4/5 & 0 & 0 & 0 & .. \\
. & . & . & . & .
\end{array}\right)$$

defined by
    $$ P_{i,j}=   \left\{
\begin{array}{ll}
      i/(i+1) & \text{if j = 1} \\
      1/(i+1) & \text{if j = i+1} \\
      0& \text{otherwise} \\
\end{array} 
\right.  $$
(a) Does the chain have an stationary distribution? If yes, exhibit its behavior, if no, explain why

(b) Classify the states of the chain

(c) Repeat part (a) with the row entries of $\textbf{P}$ switched. That is, let 
    $$ P_{i,j}=   \left\{
\begin{array}{ll}
      1/(i+1) & \text{if j = 1} \\
      i/(i+1) & \text{if j = i+1} \\
      0& \text{otherwise} \\
\end{array} 
\right.  $$

### Answer
(a) The chain does not have an stationary distribution, this because it does not matter how far it is down the line it would always be able to go back to state 0 and start over again. This means that after an infinity amount of jumps it can always go back to the beginning and start all over again 

(b) The chain is an infinite, irreducible and recurrent chain. 

(a) the same case as A applyies, eventhough the probability of going back to the beginning, this chain does not have a limiting distribution. 

## 3.7
A Markov chain has n states. If the chain is at state k, a coin is flipped, whose heads probability is $p$. If the coin lands heads, the chain stays at $k$. if the coin lands tails, the chaiin moves to a different state uniformly at random. Exhibit the transition matrix and find the stationary distribution.

### Answer
Let's see the matrix:
$$P=\left(\begin{array}{cc}
p & q/n & q/n & q/n & .. \\
q/n & p & q/n & q/n & .. \\
q/n & q/n & p & q/n & .. \\
q/n & q/n & q/n & p & .. \\
.&.&.&.&.
\end{array}\right)$$
It is clear that the rows and columns are equal, hence, double stochastic. Then the stationary distribution is uniform.

c9d1d0ca25f353ab2be72ffd60a665fbba8e12c3
ipynb
Jupyter Notebook
Chapter03_py.ipynb
larispardo/StochasticProcessR
a2f8b6c41f2fe451629209317fc32f2c28e0e4ee
MIT
Chapter03_py.ipynb
larispardo/StochasticProcessR
a2f8b6c41f2fe451629209317fc32f2c28e0e4ee
MIT
Chapter03_py.ipynb
larispardo/StochasticProcessR
a2f8b6c41f2fe451629209317fc32f2c28e0e4ee
MIT
Qwen/Qwen-72B
1. YES
2. YES