Chapter 3.8

Discrete-Time Markov Chains

[7/100%]
Show
LaTeX
Problem 3.8.1

Prove that in the definition of a Markov chain it suffices to check the condition only for consecutive time points. Namely, prove that a sufficient condition for the Markov property of a process (Xn,n∈Z+)\left(X_{n}, n \in \mathbb {Z}_+\right) with values in an at most countable set X\mathcal{X} is the equality

P(Xn+1=an+1∣Xn=an,Xn−1=an−1…,X0=a0)=P(Xn+1=an+1∣Xn=an) \mathbb {P}\left(X_{n+1}=a_{n+1} \mid X_{n}=a_{n}, X_{n-1} = a_{n-1} \ldots , X_{0}=a_{0}\right) = \mathbb {P}\left(X_{n+1}=a_{n+1} \mid X_{n}=a_{n}\right)

∀n∈N,  ∀an+1,…,a0∈X\forall n \in \mathbb {N}, \; \forall a_{n+1}, \ldots , a_0 \in \mathcal{X} (the equality must hold whenever the conditioning probabilities are positive).

?
Problem 3.8.2

Let {ξn,n∈N}\left\{ \xi_{n}, n \in \mathbb {N}\right\} be independent identically distributed random variables with values in Z\mathbb {Z}, with probability function p(x):=P(ξi=x)p(x) := \mathbb {P}\left(\xi_i = x\right), positive for all x∈Zx \in \mathbb {Z}. State whether the following random sequences (random processes) are necessarily Markov chains:

?
(a)

ξ=(ξn,  n∈N)\xi =\left(\xi_{n}, \; n \in \mathbb {N}\right);

(b)

S=(Sn=ξ1+…+ξn,  n∈Z+)S = \left(S_{n}=\xi_{1}+\ldots +\xi_{n}, \; n \in \mathbb {Z}_{+}\right), where S0=0S_{0}=0;

(c)

S+=(Sn⋅  1Sn≥0,  n∈Z+)S^{+} = \left(S_{n} \cdot \; \mathbb {1}_{S_{n} \geq 0}, \; n \in \mathbb {Z}_{+}\right);

(d)

T=(Tn=max⁡{S0,…,Sn},  n∈Z+)T = \left(T_{n}=\max \left\{ S_{0}, \ldots , S_{n}\right\} , \; n \in \mathbb {Z}_{+}\right).

If the process is not necessarily a Markov chain, give a counterexample proving this. If it is, state the one-step transition probabilities.

Problem 3.8.3

Let {ξn,n∈Z+}\left\{ \xi_{n}, n \in \mathbb {Z}_{+}\right\} be a Markov chain with phase space S={1,2,3}S= \left\{ 1,2,3\right\}, initial state ξ0=1\xi_{0}=1 a.s. and transition probability matrix

(3/73/71/71/112/118/111/114/116/11) \begin{pmatrix} 3 / 7 & 3 / 7 & 1 / 7 \\ 1 / 11 & 2 / 11 & 8 / 11 \\ 1 / 11 & 4 / 11 & 6 / 11 \end{pmatrix}

Set ηn=  1ξn=1+2  1ξn≠1\eta_{n}= \; \mathbb {1}_{\xi_{n}=1} + 2\; \mathbb {1}_{\xi_{n} \neq 1}. Prove that ηn\eta_{n} is also a Markov chain, and find its transition matrix.

?
Problem 3.8.4

The Markov chain (ξn,n∈Z+)\left(\xi_{n}, n \in \mathbb {Z}_{+}\right) has initial state ξ0=0\xi_{0}=0 and transition probabilities

P(ξn+1=k+1∣ξn=k)=p,P(ξn+1=k∣ξn=k)=1−p, \mathbb {P}\left(\xi _{n+1}=k+1 \mid \xi _{n}=k\right) = p, \quad \mathbb {P}\left(\xi _{n+1}=k \mid \xi _{n} = k\right) = 1 - p,

k,n∈N,  p∈[0,1]k, n \in \mathbb {N}, \; p \in [0,1].

?
(a)

Find the distribution of ξn\xi_{n};

(b)

Prove that the sequence τ0=0,τk=min⁡{n:ξn=k}\tau_{0}= 0, \tau_{k}=\min \left\{ n: \xi_{n}=k\right\} is also a Markov chain and find its transition probabilities.

Problem 3.8.5

The Markov chain ξn\xi_{n} has initial state ξ0=0\xi_{0}=0 and transition probabilities

P(ξn+1=k+1∣ξn=k)=a−k,P(ξn+1=k∣ξn=k)=1−a−k, \mathbb {P}\left(\xi _{n+1}=k+1 \mid \xi _{n}=k\right) =a^{-k}, \quad \mathbb {P}\left(\xi _{n+1}=k \mid \xi _{n}=k\right) = 1-a^{-k},

where k,n∈Z+,  a>1k, n \in \mathbb {Z}_{+}, \; a > 1. Find E[aξn],Var⁡[aξn]\mathbb {E}\left[a^{\xi_{n}}\right], \operatorname {Var}\left[a^{\xi_{n}}\right].

?
Problem 3.8.6
?
(a)

Give an example of a homogeneous discrete-time Markov chain that has several stationary distributions but no limiting one;

(b)

Give an example of a homogeneous discrete-time Markov chain that has no stationary distribution, but does have limits of the transition probabilities as n→∞n \rightarrow \infty;

(c)

Prove that if a homogeneous discrete-time Markov chain has several stationary distributions, then in fact it has infinitely many.

Problem 3.8.7

Let (ξn,n∈Z+)\left(\xi_{n}, n \in \mathbb {Z}_{+}\right) be independent identically distributed random variables with values in {0,1,2,3}\left\{ 0,1,2,3\right\} and the following distribution:

P(ξn=0)=17,P(ξn=1)=27,P(ξn=2)=37,P(ξn=3)=17 \begin{align} \mathbb {P}\left(\xi _{n}=0\right) & = \frac{1}{7}, & \quad \mathbb {P}\left(\xi _{n}=1\right) & = \frac{2}{7}, \\ \mathbb {P}\left(\xi _{n}=2\right) & = \frac{3}{7}, & \quad \mathbb {P}\left(\xi _{n}=3\right) & = \frac{1}{7} \end{align}

Consider the processes

Xn=ξ1+…+ξn  ( mod 4),Yn=ξ1⋅…⋅ξn  ( mod 4), \begin{align} X_{n} & = \xi _{1} + \ldots + \xi _{n} \; (\bmod 4), \\ Y_{n} & = \xi _{1} \cdot \ldots \cdot \xi _{n} \; (\bmod 4), \end{align}

n∈Nn \in \mathbb {N}. Prove that (Xn,  n∈N)\left(X_{n}, \; n \in \mathbb {N}\right) and (Yn,  n∈N)\left(Y_{n}, \; n \in \mathbb {N} \right) are homogeneous Markov chains, and find their limiting distributions.

?