# 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
```

## 2.1
A Markov chain has transition Matrix
$$
p=\left(\begin{array}{cc} 
0.1 & 0.3&0.6\\
0 & 0.4& 0.6 \\
0.3 & 0.2 &0.5
\end{array}\right)
$$ 
With initial distribution $\alpha =(0.2,0.3,0.5)$. Find the following:

a) $P(X_7=3|X_6=2)$

b) $P(X_9=2|X_1=2,X_5=1,X_7=3)$

c) $P(X_0=3|X_1=1)$

d) $E[X_2]$



```python
a=np.array([0.2,0.3,0.5])
p = np.matrix([[0.1,0.3,0.6],[0,0.4,0.6],[0.3,0.2,0.5]])
p[1,2]
```




    0.6




```python
(p*p)[2,1]
```




    0.27




```python
a[2]*p[2,0]/(a[0]*p[0,0]+a[1]*p[1,0]+a[2]*p[2,0])
```




    0.8823529411764707




```python
e=0
pr = a*p*p
for i in range(pr.shape[1]):
    e += (i+1)*pr[0,i]
e
```




    2.3630000000000004



## 2.1
A Markov chain has transition Matrix
$$
p=\left(\begin{array}{cc} 
0 & 1/2&1/2\\
1 & 0& 0 \\
1/3 & 1/3 &1/3
\end{array}\right)
$$ 
With initial distribution $\alpha =(1/2,0,1/2)$. Find the following:

a) $P(X_2=1|X_1=3)$

b) $P(X_1=3,X_2=1)$

c) $P(X_1=3|X_2=1)$

d) $P(X_9=1|X_1=3, X_4=1, X_7=2)$


```python
a=np.array([1/2,0,1/2])
p = np.matrix([[0,1/2,1/2],[1,0,0],[1/3,1/3,1/3]])
p[2,0]
```




    0.3333333333333333




```python
(a*p)[0,2]*p[2,0]
```




    0.13888888888888887




```python
(a*p)[0,2]*p[2,0]/((a*p)[0,0]*p[0,0]+(a*p)[0,1]*p[1,0]+(a*p)[0,2]*p[2,0])
```




    0.25




```python
(p*p)[1,0]
```




    0.0



## 2.3
Consider the Wright-Fisher model with population k=3. If the initial population has one A allele, what is the probability that there are no alleles at time 3.


```python
def calculate_combinations(n, r):
    from math import factorial
    return factorial(n) // factorial(r) // factorial(n-r)
mat = []
k = 3
for j in range(k+1):
    vec = []
    for i in range(k+1):
        vec.append(calculate_combinations(k, i)*(j/k)**i*(1-j/k)**(k-i))
    mat.append(vec)
p=np.matrix(mat)
(p**3)[1,0]
```




    0.5166895290352083



## 2.4
For the Generalñ two-state chain with transformation matrix 
$$\boldsymbol{P}=\left(\begin{array}{cc} 
1-p & p\\
q & 1-q
\end{array}\right)$$

And initial distribution $\alpha=(\alpha_1,\alpha_2)$, find the following:

(a) the two step transition matrix

(b) the distribution of $X_1$

### Answer
(a)

For this case the result comes from doing the matrix multiplication once i.e. finding $\boldsymbol{P}*\boldsymbol{P}$ that is:
$$\boldsymbol{P}*\boldsymbol{P}=\left(\begin{array}{cc} 
(1-p)^2+pq & (1-p)p+(1-q)p\\
(1-p)q+(1-q)q & (1-q)^2+pq
\end{array}\right)$$

(b) 
in this case we need to take into account alpha which would be $X_0$ and then multiply with the transition matrix, then:

$\boldsymbol{\alpha}*\boldsymbol{P}$ that is:
$$\boldsymbol{\alpha}*\boldsymbol{P}=( 
(1-p)\alpha_1+q\alpha_2 , p\alpha_1+(1-q)\alpha_2)$$

## 2.5
Consider a random walk on $\{0,...,k\}$, which moves left and right with respective probabilities q and p. If the walk is at 0 it transitions to 1 on the next step. If the walk is at k it transitions to k-1 on the next step. This is calledrandom walk with reflecting bounderies. Assume that $k=3,q=1/4, p =3/4$ and the initial distribution is uniform. For the following, use technology if needed.

(a) Exhibit the transition Matrix

(b) Find $P(X_7=1|X_0=3,X_2=2,X_4=2)$

(c) Find $P(X_3=1,X_5=3)$

### Answer
(a) $$\boldsymbol{Pr}=\left(\begin{array}{cc}
0 & 1 & 0 & 0 \\
1/4 & 0 & 3/4 & 0\\
0 & 1/4 & 0 & 3/4 \\
0 & 0 & 1 & 0
\end{array}\right)$$

(b) since it is a Markov Chain, then $P(X_7=1|X_0=3,X_2=2,X_4=2)=P(X_7=1|X_4=2)=\boldsymbol{Pr}^3_{2,1}$



```python
p = np.matrix([[0,1,0,0],[1/4,0,3/4,0],[0,1/4,0,3/4],[0,0,1,0]])
(p**3)[2,1]
```




    0.296875



(c) $P(X_3=1,X_5=3)=(\alpha \boldsymbol{Pr}^3)_{1}*\boldsymbol{Pr}^2_{1,3}$


```python
a=np.matrix([1/4,1/4,1/4,1/4])
(a*p**3)[0,1]*(p**2)[1,3]
```




    0.103271484375



## 2.6
A tetrahedron die has four faces labeled 1,2,3 and 4. In repeated independent rolls of the die $R_0, R_1,...,$ let $X_n=max\{R_0,...,R_n\}$ be the maximum value after $n+1$ rolls, for $n\geq0$

(a) Give an intuitive argument for why $X_0, X_1, ... $ is a Markov Chain and exhibit its transition Matrix

(b) find P(X_3 \geq 3)

### Answer
(a) This is a Markov Chain since the value of the maximum in all the rolls does only depend on the last value given of the throw this is because the max value should not changhe based on past rolls of this given event, then $P(X_n=i|X_{n-1}=j,...)=P(X_n=i|X_{n-1}=j)$
and the transition matrix is:
$$\boldsymbol{Pr}=\left(\begin{array}{cc}
1/4 & 1/4 & 1/4 & 1/4 \\
0 & 1/2 & 1/4 & 1/4 \\
0 & 0 & 3/4 & 1/4 \\
0 & 0 & 0 & 1
\end{array}\right)$$


(b) We know that the tetrahedron has unoiform probability to get the initial value, then $\alpha=(1/4,1/4,1/4,1/4)$
then we want $\alpha*\boldsymbol{Pr}^3$


```python
p = np.matrix([[1/4,1/4,1/4,1/4],[0,1/2,1/4,1/4],[0,0,3/4,1/4],[0,0,0,1]])
a=np.matrix([1/4,1/4,1/4,1/4])
(a*p**3)[0,2:].sum()
```




    0.9375



## 2.7
Let $X_0, X_1,...$ be a Markov chain with transition matrix $P$. Let $Y_n=X_{3n}$, for $n = 0,1,2,...$ Show that $Y_0,Y_1,...$ is a Markov chain and exhibit its transition Matrix.

### Answer
Let's unravel $P(Y_k|Y_{k-1},...,Y_0)$

$$P(Y_k|Y_{k-1},...,Y_0)=P(X_{3k}|X_{3k-3},...,X_0)$$

But since $X_0, X_1,...$ is a Markov Chain, then $P(X_{3k}|X_{3k-3},...,X_0) = P(X_{3k}|X_{3k-3}) = P(Y_k|Y_{k-1})$
This means that $Y_0,Y_1,...$ is also a Markov chain.

and then the transition matrix for Y is $P_Y=P_X^3$

## 2.8
Give the Markov transition matrix for a random walk on the weighted graph in the next figure:
<div>

</div>

### Answer 
$$\boldsymbol{Pr}=\left(\begin{array}{cc}
0 & 1/3 & 0 & 0 & 2/3 \\
1/10 & 1/5 & 1/5 & 1/10 & 2/5 \\
1/2 & 1/3 & 0 & 1/6 & 0\\
0 & 1/2 & 1/2 & 0 & 0\\
1/3 & 2/3 & 0 & 0 & 0
\end{array}\right)$$

## 2.8
Give the Markov transition matrix for a random walk on the weighted graph in the next figure:
<div>

</div>

### Answer 
$$\boldsymbol{Pr}=\left(\begin{array}{cc}
0 & 0 & 3/5 & 0 & 2/5 \\
1/7 & 2/7 & 0 & 0 & 4/7 \\
0 & 2/9 & 2/3 & 1/9 & 0\\
0 & 1 & 0 & 0 & 0\\
3/4 & 0 & 0 & 1/4 & 0
\end{array}\right)$$

## 2.10
Consider a Markov Chain with transition Matrix

$$\boldsymbol{Pr}=\left(\begin{array}{cc}
0 & 3/5 & 1/5 & 2/5 \\
3/4 & 0 & 1/4 & 0 \\
1/4 & 1/4 & 1/4 & 1/4\\
1/4 & 0 & 1/4 & 1/2
\end{array}\right)$$
(a) Exhibit the directed, weighted transition graph for the chain

(b) The transition graph for this chain can be given as a weighted graph without directed edges. Exhibit the graph

(a)
<div>

</div>

(b)
<div>

</div>

## 2.11
You start with five dice. Roll all the dice and put aside those dice that come up 6. Then roll the remaining dice, putting aside thise dice that come up 6. and so on. Let $X_n$ be the number of dice that are sixes after n rolls. 

(a)  Describe the transition matrix $\boldsymbol{Pr}$ for this Markov chain

(b) Find the probability of getting all sixes by the third play.

(c) what do you expect $\boldsymbol{Pr}^{100}$ to look like? Use tech to confirm your answer **(Good that we are doing this in jupyter notebook haha)**

(a) Note that the space for $X_n$ is $0,1,2,3,4,5$

$$\boldsymbol{Pr}=\left(\begin{array}{cc}
1 & 0 & 0 & 0 & 0 & 0 \\
1/6 & 5/6 & 0 & 0 & 0 & 0\\
\frac{1^2}{6^2}{2\choose 2} & \frac{5*1}{6^2}{2\choose 1} & \frac{5^2}{6^2}{2\choose 0} & 0 & 0 & 0\\
\frac{1^3}{6^3}{3\choose 3} & \frac{5*1^2}{6^3}{3\choose 2} & \frac{5^2*1}{6^3}{3\choose 1} & \frac{5^3}{6^3}{3\choose 0} & 0 & 0\\
\frac{1^4}{6^4}{4\choose 4} & \frac{5*1^3}{6^4}{4\choose 3} & \frac{5^2*1^2}{6^4}{4\choose 2} & \frac{5^3*1}{6^4}{4\choose 1} & \frac{5^4}{6^4}{4\choose 0} & 0\\
\frac{1^5}{6^5}{5\choose 5} & \frac{5*1^4}{6^5}{5\choose 4} & \frac{5^2*1^3}{6^5}{5\choose 3} & \frac{5^3*1^2}{6^5}{5\choose 2} & \frac{5^4*1}{6^5}{5\choose 1} & \frac{5^5}{6^5}{5\choose 0}\\
\end{array}\right) = \left(\begin{array}{cc}
1 & 0 & 0 & 0 & 0 & 0 \\
\frac{1}{6} & \frac{5}{6} & 0 & 0 & 0 & 0\\
\frac{1}{36} & \frac{10}{36} & \frac{25}{36} & 0 & 0 & 0\\
\frac{1}{216} & \frac{15}{216} & \frac{75}{216} & \frac{125}{216} & 0 & 0\\
\frac{1}{1296} & \frac{20}{1296} & \frac{150}{1296} & \frac{500}{1296} & \frac{625}{1296} & 0\\
\frac{1}{7776} & \frac{25}{7776} & \frac{250}{7776} & \frac{1250}{7776} & \frac{3125}{7776} & \frac{3125}{7776}\\
\end{array}\right)$$

It is interesting that the distribution when $X_n=i$ is the components of the binomial expansion $(1/6+5/6)^i$

(b)


```python
p = np.matrix([[1, 0, 0, 0, 0, 0],
                      [1/6, 5/6, 0, 0, 0, 0], [1/36, 10/36, 25/36, 0, 0, 0], 
                      [1/216, 15/216, 75/216, 125/216, 0, 0], 
                      [1/1296, 20/1296, 150/1296, 500/1296, 625/1296, 0],
                      [1/7776, 25/7776, 250/7776, 1250/7776 ,3125/7776, 3125/7776]])
(p**3)[5,0]
```




    0.013272056011374654



(c) I would expect that there is basically 100 percent posibility that there are 0 dices left without regarding how many dices you started with.


```python
(p**100).round()
```




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



## 2.12
two urns contain k balls each. At the beginning of the experiment the urn on the left countains k red balls and the one on the right contains k blue balls. At each step, pick a ball at random from each urn and excange them. Let $X_n$ be the number of blue balls left in the urn on the left (Note that $X_0=0, X_1 = 1$). Argue the process is a Markov Chain. Find the transition matrix. This model is called the Bernoulli - Laplace process. 

### Answer
This process has to be a random process because the only thing that matters at step n is to know how many blue balls are in the urn on the left. This means that even if you know all the history only the last state is the one that matters to know the probability for the next step.

$$P = \left(\begin{array}{cc}
0 & 1 & 0 & ... &0 & 0 & 0 \\
\frac{1}{k} & 0 & \frac{k-1}{k} & ... & 0 & 0 & 0\\
0 & \frac{2}{k} & 0 & ... & 0 & 0 & 0\\
... & ... & ... & ... & ... & ... & ...\\
0 & 0 & 0 & ... & \frac{k-1}{k} & 0 & \frac{1}{k}\\
0 & 0 & 0 & ... & 0 & 1 & 0\\
\end{array}\right)$$

## 2.13
see the move-to-front process in Example 2.10. Here is anorher way to organize the bookshelf. when a book is returned it is put bacl on the library shelf one position forward from where it was originally. If the book at the fron of the shelf is returned it is put back at the front of the shelf. This, if the order of books is (a,b,c,d,e) and the book d is picjed, the new order is (a,b,d,c,e). This reorganization method us called the *transposition* or *move-ahead-1* scheme. Give the transition matrix for the transportation scheme for a shelf with three books.

### Answer
remember the states are $(abc, acb, bac,bca, cab, cba)$
$$P = \left(\begin{array}{cc}
0 & p_c & p_b &p_a & 0 & 0 \\
p_b & 0 & 0 & 0 & p_c & p_a\\
p_a & p_b & 0 & p_c & 0 & 0\\
0 & 0 & p_a & 0 & p_b & p_c\\
p_c & p_a & 0 & 0 & 0 & p_b\\
0 & 0 & p_c & p_b & p_a & 0
\end{array}\right)$$

## 2.14
There are k songs in Mary's music player. The player is set to *Shuffle* mode, which plays songs uniformly at random, sampling with replacement. Thus, repeats are possible. Let $X_n$ denote the number of *unique* songs that have been heard after the nth play. 

(a) show that $X_0,X_1, ...$ is a Markov chain and give the transition matrix

(b) if Mary has four songs on her music player, find the probability that all songs are heard after six plays.

### Answer
(a) 
imagine that you have $P(X_n|X_{n-1},...,X_0)$ note that $X_{n+1}=max\{\xi_{n+1},X_n\}$ where $\xi_{n+1}$ is the result of the n+1 and it is independent to all $X_i$, $0\leq i\leq n$, then this means that $X_0,...,X_n$ is a Markov chain with transition matrix:
$$P = \left(\begin{array}{cc}
1/k & (k-1)/k & 0 & ... &0 & 0 & 0 \\
0 & 2/k & (k-2)/k & ... & 0 & 0 & 0\\
0 & 0 & 3/k & ... & 0 & 0 & 0\\
... & ... & ... & ... & ... & ... & ...\\
0 & 0 & 0 & ... & 0 & (k-1)/k & 1/k\\
0 & 0 & 0 & ... & 0 & 0 & 1\\
\end{array}\right)$$

## 2.15
Assume that $X_0,X_1,...$ is a two state Markov chain in $\mathcal{S}=\{0,1\}$ with transition matrix:

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

The present state of the chain only depends on the previous state. We can create a bivariate process that looks back two time periods by the following contruction. Let $Z_n=(X_{n-1},X_n)$, for $n\geq1$. The sequence $Z_1,Z_2,...$ is a Markov chain with state space $\mathcal{S}X\mathcal{S}={(0,0),(1,0),(0,1),(1,1)}$ Give the transition matrix of the new chain. 

### Answer
$$P = \left(\begin{array}{cc}
1-p & p & 0 & 0 \\
0 & 0 & q & 1-q \\
1-p & p & 0 & 0 \\
0 & 0 & q & 1-q 
\end{array}\right)$$

## 2.16
Assume that  $P$  is a stochastic matrix with equal rows. Show that $P^n=P$, for all $n\geq1$

### Answer
let's then see $P$ as:
$$P = \left(\begin{array}{cc}
p_1 & p_2 & ... & p_k \\
p_1 & p_2 & ... & p_k \\
p_1 & p_2 & ... & p_k \\
... & ... & ... & ... \\
p_1 & p_2 & ... & p_k \\
p_1 & p_2 & ... & p_k \\
\end{array}\right)$$

First let's calculate $P^2$, then

$$P^2 = \left(\begin{array}{cc}
p_1*p_1+p_2*p_1+...+p_k*p_1 & p_1*p_2+p_2*p_2+...+p_k*p_2 & ... & p_1*p_k+p_2*p_k+...+p_k*p_k \\
p_1*p_1+p_2*p_1+...+p_k*p_1 & p_1*p_2+p_2*p_2+...+p_k*p_2 & ... & p_1*p_k+p_2*p_k+...+p_k*p_k \\
p_1*p_1+p_2*p_1+...+p_k*p_1 & p_1*p_2+p_2*p_2+...+p_k*p_2 & ... & p_1*p_k+p_2*p_k+...+p_k*p_k \\
... & ... & ... & ... \\
p_1*p_1+p_2*p_1+...+p_k*p_1 & p_1*p_2+p_2*p_2+...+p_k*p_2 & ... & p_1*p_k+p_2*p_k+...+p_k*p_k \\
p_1*p_1+p_2*p_1+...+p_k*p_1 & p_1*p_2+p_2*p_2+...+p_k*p_2 & ... & p_1*p_k+p_2*p_k+...+p_k*p_k \\
\end{array}\right)=
\left(\begin{array}{cc}
p_1*(p_1+p_2+...+p_k) & ... & p_k(p_1+p_2+...+p_k) \\
p_1*(p_1+p_2+...+p_k) & ... & p_k(p_1+p_2+...+p_k) \\
p_1*(p_1+p_2+...+p_k) & ... & p_k(p_1+p_2+...+p_k) \\
... & ... & ...  \\
p_1*(p_1+p_2+...+p_k) & ... & p_k(p_1+p_2+...+p_k) \\
p_1*(p_1+p_2+...+p_k) & ... & p_k(p_1+p_2+...+p_k) \\
\end{array}\right)=
\left(\begin{array}{cc}
p_1*(1) & ... & p_k(1) \\
p_1*(1) & ... & p_k(1) \\
p_1*(1) & ... & p_k(1) \\
... & ... & ...  \\
p_1*(1) & ... & p_k(1) \\
p_1*(1) & ... & p_k(1) \\
\end{array}\right) = P$$

Then let's see what happens for $P^3$, then 
$$P^3=P^2*P=P*P=P^2=P$$

Assume it is true for $P^n$ and see what happens at $P^{n+1}$
$$P^{n+1}=P^n*P=P*P=P^2=P$$
Then this means that  $P^n=P$, for all $n\geq1$

## 2.17
Let **$P$** be the stochastic matrix. Show that $\lambda = 1$ is an eigenvalue of **$P$**. What is the associated eigenvector?

## Answer 
Let's first think that it is clear that the rows all sum to one, and remember that an eigenvector asociated to an eigen value looks of the form:
$$A\overline{x}=\lambda \overline{x}$$

it is easy to note that the eigenvector we are looking at is the vector $\overline{x}=(1,1,...,1)^T$ this means that the eigenvalue asociated to this is also one

we can check this by doing the multiplication. Say we have
$$A= \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)$$
where A is an stochastic matrix. Then:
$$Ax= \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}
1 \\
1 \\
...  \\
1\\
\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}
1 \\
1 \\
...  \\
1\\
\end{array}\right)$$

The way to prove this is to remember that if $A$ is an square matrix, then the eigenvalues of A are the same as its transpose's. Then, let's check if 1 is an eigenvalue by doing $det(A^T-\lambda I)$ where $\lambda$ is the eigenvalue (in this case 1) and $I$ is the identity matrix, when doing this we get that:
$$A-I= \left(\begin{array}{cc}
p_{1,1} -1 & p_{1,2} & ... & p_{1,k} \\
p_{2,1} & p_{2,2}- 1 & ... & p_{2,k} \\
... & ... & ... & ... \\
p_{k,1} & p_{k,2} & ... & p_{k,k}-1 \\
\end{array}\right)$$

And since we are dealing with the transpose, then if we sum all rows to the first row (i.e. $R_1 -> R_1+R_2+...+R_k$), then all values in the first row are zero, which means that the matrix is linearly dependand and $det(A^T- 1I)=0$, which means that 1 is an eigenvalue for $A$

## 2.18
A stochastic matrix is called *doubly* stochastic if its columns sum to 1. Let $X_0,X_1,...$ be a Markov chain on $\{ 1,...,k \}$ with doubly stochastic transition matrix and initial distribution that is uniform on $\{ 1,...,k \}$. Show that the distribution of $X_n$ is uniform on $\{ 1,...,k \}$, for all $n\geq0$

### 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

Now let's $n=2$
$$X_1=\alpha P^2 = (\alpha P)*P=\alpha*p=\alpha$$

Then we assume it happens for $n$, let's see then for $n+1$
$$X_{n+1}=\alpha P^{n+1} = (\alpha P^n)*P=\alpha*p=\alpha$$

## 2.19
Let **$P$** be the transition matrix of a Markov chain on $k$ states. Let **$I$** denote the $kXk$ identity matrix. consider the matrix

$$\boldsymbol{Q}=(1-p)\boldsymbol{I}+p\boldsymbol{P}\text{  , for }0<p<1$$
show that **$Q$** is a stochastic matrix. Give the probabilistic interpretation for the dynamics of a markov chain governed by the **$Q$** matrix in terms of the original Markov chain.

### Answer
Let's construct $(1-p)\boldsymbol{I}+p\boldsymbol{P}$ and we need to check for two main things. First, $0\leq p_{i,j}\leq 1$, this is clear, since $P$ already holds this property and you are just multiplying it by two numbers that sum 1 and are less than 1. Now we need to check if $\sum_j p_{i,j}=1$, then seing the matrix:
$$(1-p)\boldsymbol{I}+p\boldsymbol{P}=\left(\begin{array}{cc}
p_{1,1}*p +(1-p) & p_{1,2}*p & ... & p_{1,k}*p \\
p_{2,1}*p & p_{2,2}*p+(1-p) & ... & p_{2,k}*p \\
... & ... & ... & ... \\
p_{k,1}*p & p_{k,2}*p & ... & p_{k,k}*p+(1-p) \\
\end{array}\right)$$
we have for row i 

$p_{i,1}*p + p_{1,2}*p + ...+ p_{i,i}p+(1-p)+...+ p_{1,k}*p = p*(p_{i,1} + p_{1,2} + ...+ p_{1,k})+1-p=p*(1)+1-p=1 $

then $Q$ is a stochastic matrix.

As I see it this matrix $Q$ the only value it is modifying is the probability of transitioning from state $i$ to state $i$. so this linear combination could be used when you want to give more probability to return to the same state you are at step $n$. you can notice that the probability of going back to state $i$ when you are at state $i$ is due to the fact that is the only other state that has a real value greater than zero being added to it.


## 2.20
Let $X_0,X_1,...$ be a Markov chain with transition matrix 

$$P=\left(\begin{array}{cc}
0 & 1 & 0 \\
0 & 0 & 1 \\
p & 1-p & 0
\end{array}\right)$$
for $0<p<1$. Let $g$ be the function defined by:

$$
  g(x) =
  \begin{cases}
                                   0 & \text{if $x=1$} \\
                                   1 & \text{if $x=2,3$} 
  \end{cases}
$$

Let $Y_n=g(X_n)$ for $n\geq0$. Show that $Y_0,Y_1,...$ is not a Markov chain

### Answer

Let's proof this by contradiction. if we assume $Y_n$ is a Markov chain, then $P(Y_n|Y_{n-1},...,Y_0)=P(Y_n|Y_{n-1})$, but let's check this next two scenarios

## 2.21
Let $P$ and $Q$ be two transition matricies on the same state space processes, both started in some initial state $i$.

In the process $\#1$ a coin is flipped, then if it lands head, the process unfolds according to $P$. If it lands tails, the process unfolds according to $Q$. 

In process $\#2$, at each step a coin is flipped. If it lands heads, the next step is chosen from $P$. If it lands tails, the next step is chosen from $Q$.

Thus, in $\#1$, one coin is initially flipped, which governsthe entire evolution of the process and in $\#2$ a coin is flipped at each step to decide the next step in the process.

Decide whether either of these processes is a Markov chain, if it is exhibit its transition matrix, if not, then explain why not.

### Answer
$#1$

For example 1 we have that it is not a Markov chain and the reason for this is because in the first step the this means that the distribution of $X_0$ is different from the distribution of $X_1$ which means that we cannot have a transition matrix for all states, although it is nice to see that once the heads is chosen, then the next steps do follow a Markov chain with either $P$ or $Q$ as their matrices.

$#2$

For example 2 we have that it is a Markov chain and the reason for this is because we can define the transition Matrix $M=0.5P+0.5Q$ as the new matrix that follows this process. 


```python
## This could be a class.
def ChooseNextStep(x, mat):
    tmp_x = x*mat
    return tmp_x, np.random.choice(tmp_x.shape[1],p=np.array(tmp_x).reshape(-1))

def Simulation_21(case, P=np.matrix([[0.2,0.8],[0.2,0.8]]),Q=np.matrix([[0.8,0.2],[0.8,0.2]]),
                  simulations=1000, steps = 5, p=0.5):
    '''
    This is a function for the simulation stated in 2.21 from the book, it receives the 
    two matrices and the case you are talking for either one or two and calculates its state matrices for the first
    steps we assume initial distributions uniform
    '''
    rows = P.shape[0]
    cols = P.shape[1]
    initial_dis = np.matrix([1/cols]*cols)
    sim = []
    for i in range(simulations):
        res = []
        tmp_x=initial_dis
        for j in range(steps):
            if case == 1:
                if j == 0:
                    coin = np.random.random()
                    if coin < p:
                        # Follows P
                        dist = "P"
                        tmp_x, xi = ChooseNextStep(tmp_x,P)
                    else:
                        dist = "Q"
                        tmp_x, xi = ChooseNextStep(tmp_x,Q)
                else:
                    if dist=="P":
                        tmp_x, xi = ChooseNextStep(tmp_x,P)
                    else:
                        tmp_x, xi = ChooseNextStep(tmp_x,Q)
            elif case == 2:
                coin = np.random.random()
                if coin < p:
                    # Follows P
                    tmp_x, xi = ChooseNextStep(tmp_x,P)
                else:
                    tmp_x, xi = ChooseNextStep(tmp_x,Q)
            res.append(xi)
        sim.append(res)
    return np.array(sim)

def CalcMatrixForStep(sim, step=1):
    res0 = sim[sim[:,(step-1)]==0]
    res1 = sim[sim[:,(step-1)]==1]
    prob0 = np.unique(res0[:,step], return_counts=True)[1]/res0.shape[0]
    prob1 = np.unique(res1[:,step], return_counts=True)[1]/res1.shape[0]
    return np.array([prob0,prob1])

def GetTransitionMatrix(results):
    matrices = []
    for i in range(1,results.shape[1]):
        matrices.append(CalcMatrixForStep(results,i))
    return matrices
```


```python
sim = Simulation_21(1, simulations=10000)
for elem in GetTransitionMatrix(sim):
    print(elem)
```

    [[0.68071928 0.31928072]
     [0.32472472 0.67527528]]
    [[0.6699145  0.3300855 ]
     [0.31824583 0.68175417]]
    [[0.67865078 0.32134922]
     [0.32442068 0.67557932]]
    [[0.68607443 0.31392557]
     [0.32906837 0.67093163]]



```python
sim = Simulation_21(1, simulations=100000)
for elem in GetTransitionMatrix(sim):
    print(elem)
```

    [[0.68024935 0.31975065]
     [0.32288256 0.67711744]]
    [[0.68171683 0.31828317]
     [0.32311927 0.67688073]]
    [[0.68055638 0.31944362]
     [0.32225466 0.67774534]]
    [[0.68082058 0.31917942]
     [0.32163319 0.67836681]]



```python
sim = Simulation_21(2, simulations=100000)
for elem in GetTransitionMatrix(sim):
    print(elem)
```

    [[0.50320229 0.49679771]
     [0.50051641 0.49948359]]
    [[0.49590515 0.50409485]
     [0.50063234 0.49936766]]
    [[0.50008028 0.49991972]
     [0.5005182  0.4994818 ]]
    [[0.49978013 0.50021987]
     [0.49673804 0.50326196]]



```python
sim = Simulation_21(2, simulations=100000)
for elem in GetTransitionMatrix(sim):
    print(elem)
```

    [[0.49948298 0.50051702]
     [0.50138799 0.49861201]]
    [[0.5002298  0.4997702 ]
     [0.49796825 0.50203175]]
    [[0.50042076 0.49957924]
     [0.50405271 0.49594729]]
    [[0.50585378 0.49414622]
     [0.50204918 0.49795082]]


## 2.22 
Show by induction:

(a) $1+3+5+...+(2n-1)=n^2$

(b) $1^2+2^2+...+n^2=n(n+1)(2n+1)/6$

(c) for all real $x>-1$, $(1+x)^n\geq 1+nx$

### Answer
$#a$

For $n=1$

$$
\begin{align}
2(1)-1 &= 1 \\&=1^2 
\end{align}$$

Assume it works for $n-1$

$$
\begin{align}
1+3+...+(2n-3)  &= (n-1)^2 \\
                &=n^2 -2n+1
\end{align}$$

Then for $n$
$$
\begin{align}
1+3+...+(2n-3)+(2n-1)  &= n^2 -2n+1 +2n-1\\
                &=n^2 
\end{align}$$

Therefore is proved.

$#b$

For $n=1$

$$
\begin{align}
1(1+1)(2*1+1)/6 &= 6/6 \\&=1^2 
\end{align}$$

Assume it works for $n-1$

$$
\begin{align}
1^2+2^2+...+(n-1)n^2&=(n-1)(n)(2n-1)/6
\end{align}$$

Then for $n$
$$
\begin{align}
1^2+2^2+...+n^2 &=\frac{(n-1)(n)(2n-1)}{6}+n^2\\
                &=\frac{2n^-3n^2+n+6n^2}{6}\\
                &=\frac{n(2n^2+3n+1)}{6}\\
                &=\frac{n(n+1)(2n+1)}{6}
\end{align}$$

Therefore is proved.

$#c$


For this is important to notice that for $x>-1$ means that $(1+x)>0$ for all $x$. Now let's see what happens for $n=1$

$$
\begin{align}
(1+x)^1 &= (1+1*x)\\
1+x &\geq 1+x
\end{align}$$

Assume it works for $n-1$

$$
\begin{align}
(1+x)^{n-1}&\geq1+(n-1)x
\end{align}$$

Then for $n$
$$
\begin{align}
(1+x)^{n} &= (1+x)^{n-1}*(1+x)\\
          &\geq 1+(n-1)x*(1+x)\\
\\ \text{this last step because $1+x > 0$} \\ \\
1+(n-1)x*(1+x)    &=1+(n-1)x+x+(n-1)x^2\\
                  &=1+n*x+ (n-1)x^2\\
\\ \text{but since $(n-1)x^2\geq 0$ for all $x>1$}\\ \\
1+n*x+ (n-1)x^2 &\geq 1+n*x \\
\\ \text{=>} \\ \\
(1+x)^{n} &\geq 1+n*x+ (n-1)x^2 \\
          &\geq 1+n*x \\
\\ \text{by transitivity relation} \\ \\
(1+x)^{n} &\geq 1+n*x \\
\end{align}$$

Therefore is proved.


## 2.23
Simulate the first 20 letters (vowel/consonant) of the Pushkin poem Markov chain of Example 2.2.

$$P=\left(\begin{array}{cc}
0.175 & 0.825 \\
0.526 & 0.474
\end{array}\right)$$

### Answer


```python
class PushkinLetters():
    def __init__(self, P=np.matrix([[0.175,0.825],[0.526,0.474]]), init= np.array([8.638/20, 11.362/20])):
        self.P=P
        self.init = init
    def sample(self, simlist, dist):
        vowel = 0
        consonant = 1
        if (np.random.random()<dist[0]):
            simlist.append(vowel)
        else:
            simlist.append(consonant)
    def parseSimulation(self, toParse):
        return ["vowel" if x == 0 else "consonant" for x in toParse]
    def OneSimulation(self, steps = 20):
        sim = []
        self.sample(sim, self.init)
        for i in range(1,steps):
            self.sample(sim, np.array(self.P[sim[i-1]]).reshape(-1))
        return self.parseSimulation(sim)
    def Simulation(self, simulations):
        vowel = 0
        consonant = 1
        results = []
        for i in range(0,simulations):
            results.append(self.OneSimulation())
        return results
```


```python
PushkinLetters().OneSimulation()
```




    ['vowel',
     'consonant',
     'vowel',
     'consonant',
     'consonant',
     'consonant',
     'vowel',
     'consonant',
     'vowel',
     'consonant',
     'vowel',
     'consonant',
     'vowel',
     'vowel',
     'consonant',
     'consonant',
     'vowel',
     'consonant',
     'consonant',
     'consonant']



## 2.24
Simulate 50 steps of the random walk on the graph in Figure2.1. Repeat the simulation 10 times. How many of your simulations end at vertex c? Compare with the exact long-term probability the walk visits c.
<div>

</div>

With transition matrix uniform across vertex as described in the frog example, then:
$$P=\left(\begin{array}{cc}
0 & 1 & 0 & 0 & 0 & 0\\
1/4 & 0 & 1/4 & 1/4 & 1/4 & 0\\
0 & 1/4 & 0 & 1/4 & 1/4 & 1/4\\
0 & 1/4 & 1/4 & 0 & 1/4 & 1/4\\
0 & 1/3 & 1/3 & 1/3 & 0 & 0\\
0 & 0 & 1/2 & 1/2 & 0 & 0
\end{array}\right)$$

### Answer


```python
class FrogJump():
    def __init__(self, P=np.matrix([[0 , 1 , 0 , 0 , 0 , 0],
                        [1/4 , 0 , 1/4 , 1/4 , 1/4 , 0],
                        [0 , 1/4 , 0 , 1/4 , 1/4 , 1/4],
                        [0 , 1/4 , 1/4 , 0 , 1/4 , 1/4],
                        [0 , 1/3 , 1/3 , 1/3 , 0 , 0],
                        [0 , 0 , 1/2 , 1/2 , 0 , 0]]), 
                 init= np.array([1/6]*6)):
        self.P=P
        self.init = init
    def sample(self, simlist, dist):
        simlist.append(np.random.choice(len(dist),p=dist))
    def OneSimulation(self, steps = 50):
        sim = []
        self.sample(sim, self.init)
        for i in range(1,steps):
            self.sample(sim, np.array(self.P[sim[i-1]]).reshape(-1))
        return sim
    def Simulation(self, simulations):
        vowel = 0
        consonant = 1
        results = []
        for i in range(0,simulations):
            results.append(self.OneSimulation())
        return results
```


```python
np.array(FrogJump().Simulation(10))[:,-1]
```




    array([3, 2, 4, 2, 3, 4, 1, 2, 3, 3])




```python
P=np.matrix([[0 , 1 , 0 , 0 , 0 , 0],
            [1/4 , 0 , 1/4 , 1/4 , 1/4 , 0],
            [0 , 1/4 , 0 , 1/4 , 1/4 , 1/4],
            [0 , 1/4 , 1/4 , 0 , 1/4 , 1/4],
            [0 , 1/3 , 1/3 , 1/3 , 0 , 0],
            [0 , 0 , 1/2 , 1/2 , 0 , 0]])
(P**30)[0,:]
```




    matrix([[0.05555595, 0.22222121, 0.22222273, 0.22222273, 0.16666667,
             0.11111072]])



## 2.25 
The behavior of dolphins in the presence of tour boats in Patagonia, Argentina is studied in Dans et al. (2012). A Markov chain model is developed, with state space consisting of five primary dolphin activities (socializing, traveling, milling, feeding, and resting). The following transition matrix is
obtained.

$$P=\left(\begin{array}{cc}
0.84 & 0.11 & 0.01 & 0.04 & 0 \\
0.03 & 0.8 & 0.04 & 0.1 & 0.03 \\
0.01 & 0.15 & 0.7 & 0.07 & 0.07 \\
0.03 & 0.19 & 0.02 & 0.75 & 0.01 \\
0.03 & 0.09 & 0.05 & 0 & 0.83 
\end{array}\right)$$

### Answer


```python
(np.matrix([
[0.84 , 0.11 , 0.01 , 0.04 , 0],
[0.03 , 0.8 , 0.04 , 0.1 , 0.03],
[0.01 , 0.15 , 0.7 , 0.07 , 0.07],
[0.03 , 0.19 , 0.02 , 0.75 , 0.01],
[0.03 , 0.09 , 0.05 , 0 , 0.83]
])**100)[0]
```




    matrix([[0.14783582, 0.41492537, 0.0955597 , 0.2163806 , 0.1252985 ]])



## 2.26 
In computer security applications, a honeypot is a trap set on a network to detect and counteract computer hackers. Honeypot data are studied in Kimou et al. (2010) using Markov chains. The authors obtain honeypot data from a central database and observe attacks against four computer ports—80, 135, 139, and 445—over 1 year. The ports are the states of a Markov chain along with a state corresponding to no port is attacked. Weekly data are monitored, and the port most often attacked during the week is recorded. The estimated Markov transition matrix for weekly attacks is
$$P=\left(\begin{array}{cc}
0 & 0 & 0 & 0 & 1 \\
0 & 8/13 & 3/13 & 1/13 & 1/13 \\
1/16 & 3/16 & 3/8 & 1/4 & 1/8 \\
0 & 1/11 & 4/11 & 5/11 & 1/11 \\
0 & 1/8 & 1/2 & 1/8 & 1/4 
\end{array}\right)$$
with initial distribution $\alpha = (0, 0, 0, 0, 1)$.

(a) Which are the least and most likely attacked ports after 2 weeks? 

(b) Find the long-term distribution of attacked ports.

### Answer


```python
P=np.matrix([
[0 , 0 , 0, 0 , 1],
[0 , 8/13 , 3/13 , 1/13, 1/13 ],
[1/16 , 3/16 , 3/8 , 1/4, 1/8 ],
[0 , 1/11 , 4/11 , 5/11 , 1/11],
[0 , 1/8 , 1/2 , 1/8 , 1/4 ]])
a=np.array([0,0,0,0,1])
parser=[80,135, 139, 445, 'No attack']
```


```python
print("the most likely port to be attacked after two weeks is:",parser[(a*P**2).argmax()],"\n"+
      "the least likely port to be attacked after two weeks is:",parser[(a*P**2).argmin()])
```

    the most likely port to be attacked after two weeks is: 139 
    the least likely port to be attacked after two weeks is: 80



```python
print("the long last distribution is:",(P**100)[0])
```

    the long last distribution is: [[0.02146667 0.26693333 0.34346667 0.22733333 0.1408    ]]


## 2.27 
See gamblersruin.R. Simulate gambler’s ruin for a gambler with initial stake $\$2$, playing a fair game.

(a) Estimate the probability that the gambler is ruined before he wins $\$5$.

(b) Construct the transition matrix for the associated Markov chain. Estimate
the desired probability in (a) by taking high matrix powers. 

(c) Compare your results with the exact probability.

### Answer


```python
class GamblingWalk():
    '''
    This class is used to simulate a random walk, it is flexible to take different 
    outcomes for the results of throwing the coin and you can have different limits to when stop the experiment
    The plotting functions are handy to see the final results.
    '''
    def __init__(self, initial_money=50, prob=1/2, min_state=0, max_state=100, outcomes = [-1,1]):
        self.prob = prob
        self.init_money = initial_money
        self.walk = []
        self.min_state = min_state
        self.max_state = max_state
        self.outcomes = outcomes
    def P_w(self, sim=100):
        results = []
        for i in range(sim):
            res = self.randomWalk()
            results.append(res[1])
        return sum(results)/len(results)
    def randomWalk(self):
        money = self.init_money
        self.walk = [int(money)]
        win = False
        while True:
            money += np.random.choice(self.outcomes,1,p=[1-self.prob,self.prob])
            self.walk.append(int(money))
            if (money <= self.min_state) or (money >= self.max_state):
                win=(money >= self.max_state)
                break
        return len(self.walk), win
    def plotWalk(self):
        if(len(self.walk)==0):
            self.randomWalk()
        plt.plot(range(len### Answer(self.walk)), self.walk)
        plt.xlabel("Time")
        plt.ylabel("Money")
        plt.show()
```


```python
wlk = GamblingWalk(initial_money=2, max_state=5)
1-wlk.P_w(10000)
```




    array([0.5985])



(b) The transition Matrix is given by:

$$P=\left(\begin{array}{cc}
1 & 0 & 0 & 0 & 0 & 0 \\
1/2 & 0 & 1/2 & 0 & 0 & 0 \\
0 & 1/2 & 0 & 1/2 & 0 & 0 \\
0 & 0 & 1/2 & 0 & 1/2 & 0 \\
0 & 0 & 0 & 1/2 & 0 & 1/2 \\ 
0 & 0 & 0 & 0 & 0 & 1 \\
\end{array}\right)$$


```python
P=np.matrix([[1 , 0 , 0 , 0 , 0 , 0],
            [1/2 , 0 , 1/2 , 0 , 0 , 0],
            [0 , 1/2 , 0 , 1/2 , 0 , 0],
            [0 , 0 , 1/2 , 0 , 1/2 , 0],
            [0 , 0 , 0 , 1/2 , 0 , 1/2],
            [0 , 0 , 0 , 0 , 0 ,1]])
a=np.array([0,0,1,0,0,0])
(a*P**100).round(4)
```




    array([[0.6, 0. , 0. , 0. , 0. , 0.4]])



(c) As seen from the results from (a) and (b) we can see that the simulation is a bit off, even after 10,000 simulations.

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