Probability and Computing: Chapter 7 Exercises

Exercise 7.12: Let X_{n} be the sum of n independent rolls of a fair dice. Show that, for any k > 2, \lim_{n \rightarrow \infty}(X_{n} \text{is divisible by k}) = \frac{1}{k}.

Solution: Let (Y_{n})_{n \ge 0} be a Markov chain on state space I consist of k states: 0,1,..., k -1, where the chain reaches state i if and only if X_{n}\equiv i \pmod{k}.
The transition matrix P is p_{i,(i + j) \bmod k} = \frac{1}{6} for 0 \le i \le k-1 and 1 \le j \le 6. The claim is equivalent to

\lim_{n \rightarrow \infty}(Y_{n} = 0) = \frac{1}{k}

We know that if a Markov chain (Y_{n})_{n \ge 0} has an irreducible, aperiodic transition matrix and an invariant distribution \pi, then \lim_{n \rightarrow \infty}(Y_{n} = j) = \pi_{j} for all j of the state space.

We will prove the defined above P is irreducible, aperiodic and then find the invariant distribution \pi of P(it will turn out that \pi_{0} = \frac{1}{k} as we need).

Exercise 7.21: Consider a Markov chain on the states \{ 0,1,\ldots , n\}, where for i < n we have P_{i,i+1} = \frac{1}{2} and P_{i,0} = \frac{1}{2}. Also, P_{n,n} = \frac{1}{2} and P_{n,0} = \frac{1}{2}. This process can be viewed as a random walk on a directed graph with vertices \{ 0,1, \ldots ,n\}, where each vertex has two directed edges: one that returns to 0 and one that moves to the vertex with the next higher number(with a self-loop at vertex n). Find the stationary distribution of this chain.(This example shows that random walks on directed graphs are very different than random walks on undirected graph).



2 responses to this post.

  1. Can you give solution of 5.10 exercise? urgent!



  2. Posted by haya on June 12, 2013 at 2:42 am

    Can you give a solution for exercise 7.21?


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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: