# 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

1. Alexa Mertens

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!

February 22, 2014
• Scott Alister McKinley

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.

February 22, 2014
• Alexa Mertens

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

February 22, 2014
2. Alexa Mertens

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?

February 22, 2014
• 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

February 24, 2014
3. William Vebert

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$.

February 24, 2014
4. William Vebert

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

February 24, 2014
5. Evan Milliken

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$

February 25, 2014
6. Evan Milliken

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

February 25, 2014
7. Alexa Mertens

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!! 😀

February 25, 2014
8. #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?

February 25, 2014
• Whoops the $y$ index should start at 2.

February 25, 2014