# Stochastics: Suggested Problems for Exam 1

Getting things kicked off on the new website. Here is a list of interesting problems to try from Durrett’s book.  Please use the comments feature to ask questions and to start discussions about these problems. I’ll chime in whenever I can.

Stationary distributions and limit distributions
1.20, 1.25, 1.38, 1.41, 1.44

Random walks on graphs
1.49-1.51

Hitting times; hitting probabilities
1.59, 1.60

Infinite state spaces
1.70, 1.73

## 12 thoughts on “Stochastics: Suggested Problems for Exam 1”

1. Alexa Mertens says:

Hey guys! Can someone please explain what problem 1.38(a) is asking for? In general, what is the “long-run fraction of time spent at each state”? I thought it was the stationary distribution but the semantics in this class always confuse me!

1. Scott Alister McKinley says:

Hi Alexa. Any time you read something that says something like “long-run fraction of time spent at each state” think in terms of asymptotic frequency and Theorems 1.22 and 1.23. Taken together they say that if a system is irreducible and all states are recurrent, then $\lim_{n \to _\infty} N_n(y)/n = \pi(y)$ where $N_n(y)$ is the number of visits to $y$ in the first $n$ steps and $\pi$ is the stationary distribution.

1. Alexa Mertens says:

Thank you very much Dr. McKinley, this makes sense!

2. Alexa Mertens says:

Is the first part of 1.59 asking for the average hitting time of each these combinations? I got an answer for HHH and HHT, but for HTT and HTH, I’m getting my (I-Ptilda) matrix has a determinant of 0 and the inverse doesn’t exist. Is anyone else having this issue?

1. Maksim Levental says:

You must be computing something wrong? For {HHH,HHT,HTH,HTT,THH,THT,TTH,TTT} I got {14., 8., 10., 8., 8., 10., 8., 14.} . No zero determinants anywhere. But this isn’t actually how it’s supposed to be solved. http://plus.maths.org/content/os/issue55/features/nishiyama/index

3. William Vebert says:

Maybe you are doing right multiplication instead of left multiplication by accident.. That is you’re computing $P \pi = \pi$ instead of $\pi P - \pi$.

4. William Vebert says:

That should be “=” in the second equation, not “-“

5. Evan Milliken says:

Alexa, for the case of HTH, $I-\overset{\sim}{P}=\begin{bmatrix} .5&-.5&0&0&0&0&0\\ 0&1&0&-.5&0&0&0\\ -.5&-.5&1&0&0&0&0\\ 0&0&0&1&0&-.5&-.5\\ 0&0&0&-.5&1&0&0\\ 0&0&-.5&0&-.5&1&0\\ 0&0&0&0&0&-.5&.5\end{bmatrix}$. Since the diagonal contains all positive entries, the matrix is invertible and $(I-\overset{\sim}{P})^{-1}\cdot\vec{1}$ gives a column vector with the entries 8,6,8,10,6,8,10. Thus, ${\bfseries E}(\tau)=3+\frac{1}{8}(8+6+8+10+6+8+10)=10$

6. Evan Milliken says:

E(tau)=3+1/8(8+6+8+10+6+8+10)=10

7. Alexa Mertens says:

Thank you guys so much for all of the help!! I actually went to office hours yesterday and worked it all out. I had my P matrix all wrong and what I have now is what you’ve posted above. Thank you so much for all the help!! 😀

8. Maksim Levental says:

#1.73: Using the result from #1.70 state 1 is recurrent iff $\sum_{y=1}^\infty \prod_{x=1}^{y-1} \frac{q_x}{p_x} = \infty$ . But $\sum_{y=1}^\infty \prod_{x=1}^{y-1} \frac{q_x}{p_x} = 0 + \frac{1}{2} +\frac{1}{2}\frac{1}{3} + \frac{1}{2}\frac{1}{3}\frac{1}{4} + \cdots$ which converges. So state 1 isn’t recurrent and then by Thm. 1.29 the chain can’t have a stationary distribution. What do you guys think?

1. Maksim Levental says:

Whoops the $y$ index should start at 2.