Stochastics: Suggested Problems for Exam 1

Scott Alister McKinleyFebruary 21, 2014January 7, 2016Intro to Stochastic Processes, Stochastics Homework

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”

Alexa Mertens says:

February 22, 2014 at 2:30 pm

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!

Reply
1. Scott Alister McKinley says:
  
  February 22, 2014 at 2:41 pm
  
  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.
  
  Reply
  1. Alexa Mertens says:
    
    February 22, 2014 at 3:00 pm
    
    Thank you very much Dr. McKinley, this makes sense!
Alexa Mertens says:

February 22, 2014 at 5:01 pm

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?

Reply
1. Maksim Levental says:
  
  February 24, 2014 at 8:30 am
  
  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
  
  Reply
William Vebert says:

February 24, 2014 at 7:57 pm

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

Reply
William Vebert says:

February 24, 2014 at 7:58 pm

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

Reply
Evan Milliken says:

February 25, 2014 at 10:43 am

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$

Reply
Evan Milliken says:

February 25, 2014 at 10:43 am

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

Reply
Alexa Mertens says:

February 25, 2014 at 5:25 pm

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

Reply
Maksim Levental says:

February 25, 2014 at 6:00 pm

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

Reply
1. Maksim Levental says:
  
  February 25, 2014 at 6:05 pm
  
  Whoops the $y$ index should start at 2.
  
  Reply