IB/IIA — Michaelmas 2000 GRG

                                         g.r.grimmett@statslab.cam.ac.uk

MARKOV CHAINS

Example Sheet 1

1.1 Let X = (X_{n}) be a Markov chain. Suppose that we are given that X_{m} = i. Show that Z_{k} = X_{m+k}, k ≥ 0, is a Markov chain with starting state i.

1.2 Show that any sequence of independent random variables taking values in the countable set S is a Markov chain. Under what condition is this chain homogeneous?

1.3 Let X_{n} be the maximum reading obtained in the first n throws of a fair die. Show that X is a Markov chain, and find the transition probabilities p_{ij}(n).

1.4 Let {S_{n} : n ≥ 0} be a simple random walk with S_{0} = 0, and show that X_{n} = |S_{n}| defines a Markov chain; find the transition probabilities of this chain. Let M_{n} = max{S_{k} : 0 ≤ k ≤ n}, and show that Y_{n} = M_{n} − S_{n} defines a Markov chain.

1.5 Let X be a Markov chain and let {n_{r} : r ≥ 0} be an unbounded increasing sequence of positive integers. Show that Y_{r} = X_{n_{r}} constitutes a (possibly inhomogeneous) Markov chain. Find the transition matrix of Y when n_{r} = 2r and X is a simple random walk.

1.6 Let X and Y be Markov chains on the set ℤ of integers. Is the sequence Z_{n} = X_{n} + Y_{n} necessarily a Markov chain? Explain.

1.7 A flea hops about at random on the vertices of a triangle (i.e., each hop is from the currently occupied vertex to one of the other two vertices each with probability \frac{1}{2}). Find the probability that after n hops the flea is back where it started.

A second flea also hops about on the vertices of a triangle, but this flea is twice as likely to jump clockwise as anticlockwise. What is the probability that after n hops this second flea is back where it started?

[Hint: \frac{1}{2} ± \frac{i}{2\sqrt{3}} = \frac{1}{\sqrt{3}} e^{±iπ/6}.]

1.8 A die is ‘fixed’ so that when it is rolled the score cannot be the same as the previous score, all other scores having probability \frac{1}{5}. If the first score is 6, what is the probability p that the nth score is 6? What is the probability that the nth score is j, where j ≠ 6?

Suppose instead that the die cannot score one greater (mod 6) than the previous score, all other five scores having equal probability. What is the new value of p? [Hint: Think about the relationship between the two dice.] 1.9 Let (X_{n})_{n≥0} be a Markov chain on {1, 2, 3} with transition matrix

P = ( \begin{matrix}0 & 1 & 0 \\ 0 & \frac{2}{3} & \frac{1}{3} \\ p & 1 − p & 0 \end{matrix} ) .

Calculate ℙ(X_{n} = 1 | X_{0} = 1) in each of the following cases (a) p = \frac{1}{16}, (b) p = \frac{1}{6}, (c)^{∗} p = \frac{1}{12}.

1.10 Identify the communicating classes of the transition matrix

P = ( \begin{matrix}\frac{1}{2} & 0 & 0 & 0 & \frac{1}{2} \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} \\ \frac{1}{2} & 0 & 0 & 0 & \frac{1}{2} \end{matrix} ) .

Which of the classes are closed?

1.11 Show that every transition matrix on a finite state-space has at least one closed communicating class. Find an example of a transition matrix with no closed communicating class.

1.12 A gambler has £2 and needs to increase it to £10 in a hurry. He can play a game with the following rules: a fair coin is tossed; if a player bets on the side which actually turns up, he wins a sum equal to his stake, and his stake is returned; otherwise he loses his stake. The gambler decides to use a bold strategy in which he stakes all his money if he has £5 or less, and otherwise stakes just enough to increase his capital, if he wins, to £10.

Let X_{0} = 2 and let X_{n} (n ≥ 1) be his capital after n throws. Prove that the gambler will achieve his aim with probability \frac{1}{5}.

What is the expected number of tosses until the gambler either achieves his aim or loses his capital?

1.13 Let (X_{n})_{n≥0} be a Markov chain on {0, 1, … } with transition probabilities given by

p_{0,1} = 1, p_{i,i+1} + p_{i,i−1} = 1, p_{i,i+1} = (\frac{i + 1}{i})^{2} p_{i,i−1}, i ≥ 1.

Show that if X_{0} = 0 the probability that X_{n} ≥ 1 for all n ≥ 1 is 6/π^{2}.

1.14 Let Y_{1}, Y_{2}, … be independent identically distributed random variables with ℙ(Y_{1} = 1) = ℙ(Y_{1} = −1) = \frac{1}{2} and set X_{0} = 1, X_{n} = X_{0} + Y_{1} + ⋯ + Y_{n} for n ≥ 1. Define

H_{0} = inf{n ≥ 0 : X_{n} = 0} .

Find the probability generating function ϕ(s) = 𝔼(s^{H_{0}}).

Suppose the distribution of Y_{1}, Y_{2}, … is changed to ℙ(Y_{1} = 2) = ℙ(Y_{1} = −1) = \frac{1}{2}. Show that ϕ now satisfies

sϕ^{3} − 2ϕ + s = 0.