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

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

  2. 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?

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

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

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s