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

Solution:

### 2 responses to this post.

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

thanks