IB/IIA — Michaelmas 2000 GRG

MARKOV CHAINS

Remarks on Example Sheet 1

1.1 We have that

ℙ(Z_{k+1} = i_{k+1} | Z_{r} = i_{r} for 0 ≤ r ≤ k) = ℙ(X_{m+k+1} = i_{k+1} | X_{m+r} = i_{r} for 0 ≤ r ≤ k, X_{m} = i)
= ℙ(X_{m+k+1} = i_{k+1} | X_{m+k} = i_{k})

by the Markov property. The last probability does not depend on i_{r} for r < k. Small step now required.

1.2 The sequence X_{1}, X_{2}, … of independent random variables satisfies

ℙ(X_{n+1} = j | X_{1} = i_{1}, …, X_{n} = i_{n}) = ℙ(X_{n+1} = j),

whence the sequence is a Markov chain. The chain is homogeneous if the X_{i} are identically distributed.

1.3 With Y_{n} the outcome of the nth throw, X_{n+1} = max{X_{n}, Y_{n+1}}, so that

p_{ij} = \{ \begin{matrix}0 & if j < i \\ \frac{1}{6}i & if j = i \\ \frac{1}{6} & if j > i, \end{matrix}

for 1 ≤ i, j ≤ 6. Similarly,

p_{ij}(n) = \{ \begin{matrix}0 & if j < i \\ (\frac{1}{6}i)^{n} & if j = i. \end{matrix}

If j > i, then p_{ij}(n) = ℙ(Z_{n} = j), where Z_{n} = max{Y_{1}, Y_{2}, …, Y_{n}}, and an elementary calculation yields

p_{ij}(n) = (\frac{j}{6})^{n} − (\frac{j − 1}{6})^{n} , i < j ≤ 6.

1.4 (i) There is probably an easier way than the following. If X_{n} = i, then X_{n+1} ∈ {i − 1, i + 1}. Now, for i ≥ 1,

(∗)  ℙ(X_{n+1} = i + 1 | X_{n} = i, B) = ℙ(X_{n+1} = i + 1 | S_{n} = i, B)ℙ(S_{n} = i | X_{n} = i, B)
+ ℙ(X_{n+1} = i + 1 | S_{n} = −i, B)ℙ(S_{n} = −i | X_{n} = i, B)

where B = {X_{r} = i_{r} for 0 ≤ r < n} and i_{0}, i_{1}, …, i_{n−1} are integers. Clearly

ℙ(X_{n+1} = i + 1 | S_{n} = i, B) = p, ℙ(X_{n+1} = i + 1 | S_{n} = −i, B) = q,

where p (= 1 − q) is the chance of a rightward step. Let l be the time of the last visit to 0 prior to the time n, l = max{r : i_{r} = 0}. During the time-interval (l, n], the path lies entirely in either the positive integers or the negative integers. If the former, it is required to follow the route prescribed by the event B ∩ {S_{n} = i}, and if the latter by the event B ∩ {S_{n} = −i}. The absolute probabilities of these two routes are

π_{1} = p^{\frac{1}{2} (n−l+i)}q^{\frac{1}{2} (n−l−i)}, π_{2} = p^{\frac{1}{2} (n−l−i)}q^{\frac{1}{2} (n−l+i)},

whence

ℙ(S_{n} = i | X_{n} = i, B) = \frac{π_{1}}{π_{1} + π_{2}} = \frac{p^{i}}{p^{i} + q^{i}} = 1 − ℙ(S_{n} = −i | X_{n} = i, B).

Substitute into (∗) to obtain

ℙ(X_{n+1} = i + 1 | X_{n} = i, B) = \frac{p^{i+1} + q^{i+1}}{p^{i} + q^{i}} = 1 − ℙ(X_{n+1} = i − 1 | X_{n} = i, B).

Finally ℙ(X_{n+1} = 1 | X_{n} = 0, B) = 1. Assuming X is a Markov chain, its transition probabilities may be calculated more simply by conditioning on S_{n}. (ii) Note that Y_{n} ≥ 0. If Y_{n} > 0, then Y_{n} − Y_{n+1} equals the (n + 1)th step, a random variable which is independent of the past history of the process. If Y_{n} = 0 then S_{n} = M_{n}, so that Y_{n+1} takes the values 0 and 1 with respective probabilities p and q, independently of the past history. [Appealing to an appropriate equation:] We deduce that Y is a Markov chain with transition probabilities

for i > 0, p_{ij} = \{ \begin{matrix}p & if j = i − 1 \\ q & if j = i + 1, \end{matrix} p_{0j} = \{ \begin{matrix}p & if j = 0 \\ q & if j = 1. \end{matrix}

The sequence Y is a random walk with a retaining barrier at 0.

1.5 For any sequence i_{0}, i_{1}, … of states,

ℙ(Y_{k+1} = i_{k+1} | Y_{r} = i_{r} for 0 ≤ r ≤ k) = \frac{ℙ(X_{n_{s}} = i_{s} for 0 ≤ s ≤ k + 1)}{ℙ(X_{n_{s}} = i_{s} for 0 ≤ s ≤ k)}

= \frac{∏_{s=0}^{k} p_{i_{s},i_{s+1}}(n_{s+1} − n_{s})}{∏_{s=0}^{k−1} p_{i_{s},i_{s+1}}(n_{s+1} − n_{s})}

= p_{i_{k},i_{k+1}}(n_{k+1} − n_{k}) = ℙ(Y_{k+1} = i_{k+1} | Y_{k} = i_{k}),

where p_{ij}(n) denotes the appropriate n-step transition probability of X.

With the usual notation, the transition matrix of Y is

π_{ij} = \{ \begin{matrix}p^{2} & if j = i + 2 \\ 2pq & if j = i \\ q^{2} & if j = i − 2. \end{matrix}

1.6 Not necessarily ! Take as example the chains S and Y of Exercise 1.4. The sum is S_{n} +Y_{n} = M_{n}, which is not a Markov chain.

1.7 A simple way to deal with the first flea is to reduce to a two-state chain on {initial vertex,

another\} with transition matrix ( 0 1_{\frac{1}{2} \frac{1}{2}} ) so that

p_{11}(n) = \frac{1}{3} + \frac{2}{3}(−\frac{1}{2})^{n}.

The second flea has transition matrix

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

The eigenvalues of P are 1, −\frac{1}{\sqrt{3}}e^{±iπ/6} so P is diagonalizable and

p_{11}(n) = α + (−\frac{1}{\sqrt{3}})^{n} (β cos \frac{nπ}{6} + γ sin \frac{nπ}{6} )

for some constants α, β, γ. Then α = \frac{1}{3}, β = \frac{2}{3}, γ = 0 by working out p_{11}(n) for n = 0, 1, 2. This method is discussed in the lectures. A very desirable alternative to using p_{11}(2) is to spot that p_{11}(n) → \frac{1}{3} as n → ∞ by convergence to equilibrium (not yet proved in lectures), which identifies α. An alternative method altogether is to exploit symmetry to write

\begin{matrix}p_{11}(n + 1) = \frac{2}{3}p_{12}(n) + \frac{1}{3}(1 − p_{11}(n) − p_{12}(n)) \\ p_{12}(n + 1) = \frac{1}{3}p_{11}(n) + \frac{2}{3}(1 − p_{11}(n) − p_{12}(n)) \end{matrix}

and then solve for p_{11}(n). (Take the first equation. Substituting for p_{12}(n) using the second equation and then for p_{12}(n − 1) using the first, you obtain 3p_{11}(n + 1) + 3p_{11}(n) + p_{11}(n − 1) = \frac{7}{3} and so obtain the constant α = \frac{1}{3} without using initial conditions or convergence to equilibrium.)

1.8 In the first case the die is like the first flea of the last question, and p = \frac{1}{6} + \frac{5}{6}(−\frac{1}{5})^{n−1}. By symmetry, the other probabilities are \frac{1}{5}(1 − p). The second die may be simulated by throwing the first die but taking the nth score to be i_{n} + n − 1 mod 6, where i_{n} is the nth score on the first die. Hence

p = \{ \begin{matrix}\frac{1}{6} + \frac{5}{6}(−\frac{1}{5})^{n−1} & if n = 1 (mod 6) \\ \frac{1}{6} − \frac{1}{6}(−\frac{1}{5})^{n−1} & otherwise. \end{matrix}

1.9 The characteristic polynomial of P is \frac{1}{3}(x − 1)(3x^{2} + x + p). The roots of 3x^{2} + x + p = 0 are −\frac{1}{4}, −\frac{1}{12} in case (a), −\frac{1}{6} ± \frac{1}{6}i in case (b), and −\frac{1}{6} (twice) in case (c). In fact if p = \frac{1}{12}, P is not diagonalizable and the usual trick fails; instead P is similar to

( \begin{matrix}−\frac{1}{6} & 1 & 0 \\ 0 & −\frac{1}{6} & 0 \\ 0 & 0 & 1 \end{matrix} )

so p_{11}(n) = α + (−\frac{1}{6})^{n}(β + γn) for some constants α, β, γ which can be identified as usual. Another approach is to solve the system of recurrences

p_{11}(n + 1) = p. p_{13}(n)
p_{12}(n + 1) = p_{11}(n) + \frac{2}{3}p_{12}(n) + (1 − p)p_{13}(n)
p_{13}(n + 1) = \frac{1}{3}p_{12}(n)

coming from the Chapman–Kolmogorov equations. Using p_{11}(n) + p_{12}(n) + p_{13}(n) = 1 and proceeding as in Exercise 1.7 you obtain 3p_{11}(n + 1) + p_{11}(n) + p.p_{11}(n − 1) = p which can be solved in the usual way. Using this method you obtain the constant term p/(p + 4) in the general case without using initial conditions.

1.10 Classes {1, 5} and {3} are closed.

1.11 If the communicating class of i is not closed, there exists j with i → j, j ↛ i. Suppose there is no closed class. Then we get a sequence i_{1}, i_{2}, … of states with i_{n} → i_{n+1}, i_{n} ↛ i_{n+1}. There can be no repeats, so the state-space is infinite.

1.12 Set h_{i} = ℙ_{i}(hit 10) then

h_{2} = \frac{1}{2}h_{4}, h_{4} = \frac{1}{2}h_{8}, h_{8} = \frac{1}{2}h_{6} + \frac{1}{2}, h_{6} = \frac{1}{2}h_{2} + \frac{1}{2}.

Hence h_{2} = \frac{1}{5}. Set k_{i} = 𝔼_{i}(time to hit 0 or 10), then k_{2} = k_{8} and k_{4} = k_{6}, by symmetry. Also k_{2} = 1 + \frac{1}{2}k_{4} etc, so k_{2} = 2. Students should be encouraged to spot and use the symmetry in this question.

1.13 The calculation of hitting probabilities for a general birth and death chain will be discussed in lectures. Set h_{i} = ℙ_{i}(hit 0), then h_{0} = 1 and

h_{i} = p_{i,i+1}h_{i+1} + p_{i,i−1}h_{i−1}

so u_{i} = h_{i−1} − h_{i} satisfies u_{i} ≥ 0,

u_{i+1} = \frac{p_{i,i−1}}{p_{i,i+1}} u_{i} = (\frac{i}{i + 1})^{2} u_{i} = ⋯ = (\frac{1}{i + 1})^{2} u_{1},

and

h_{i} = h_{0} − (h_{0} − h_{i}) = 1 − u_{1} ∑_{j=1}^{i} \frac{1}{j^{2}} .

Since (h_{i} : i ≥ 0) is the minimal non-negative solution, we have that

u_{1} = (∑_{j=1}^{∞} \frac{1}{j^{2}} )^{−1} = \frac{6}{π^{2}}

and

ℙ_{0}(X_{n} ≥ 1 for all n ≥ 1) = 1 − h_{1} = \frac{6}{π^{2}} .

1.14 By conditioning on X_{1} and using shift invariance and the strong Markov property, we obtain that

ϕ = \frac{1}{2}𝔼(s^{H_{0}} | X_{1} = 2) + \frac{1}{2}𝔼(s^{H_{0}} | X_{1} = 0) = \frac{1}{2}sϕ^{2} + \frac{1}{2}s.

whence ϕ(s) = \{1 ± \sqrt{1 − s^{2}}\}/s. Now ϕ(0) = 0, and ϕ(s) is continuous on [0, 1); hence ϕ(s) = \{1 − \sqrt{1 − s^{2}}\}/s. For the second part,

ϕ = \frac{1}{2}𝔼(s^{H_{0}} | X_{1} = 3) + \frac{1}{2}𝔼(s^{H_{0}} | X_{1} = 0) = \frac{1}{2}sϕ^{3} + \frac{1}{2}s.