STAT433/833 Assignment 0

1    |    Warm-Up

Solve the following exercises from [Dur99]:

a)  [1.8]

b)  [1.10] (use a computer)

c)  [1.56]

c)  [1.58]

e)  [1.65]

f)  [1.72]

g)  [1.73]

2    |    Some properties of periodic Markov chains

Suppose P is the transition matrix of an irreducible Markov chain on a state space X with period d.

a)  Show that there is a partition of X into X0 , X1 , ...Xd−1  disjoint and non-empty so that for each j it holds

that x ∈ Xj  and px,y  > 0 implies y ∈ Xj+1   mod  d .

b)  Show that for each j it holds that j  = [Pd ]Xj ,Xj   is the transition matrix for an irreducible Markov chain

on Xj .

c)  Let  π(ˆ)0   be  a  stationary  distribution  of 0 .   Show that  π(ˆ)j   =  π(ˆ)0 [Pj ]X0 ,Xj    is  stationary  for  j   for  each

1 ≤ j ≤ d − 1.

d)  Show that if X is finite then each dth root of unity is an eigenvalue of P.  (Hint: construct the corresponding (right-)eigenvectors.

e)  Show  that  if X  is  finite  and  if Q  is  an  irreducible transition  matrix  on  X  with  a  (possibly  complex) eigenvalue ω that satisfies  |ω|  = 1 and ω  1, then Q must be periodic.   (Hint:  if it was  aperiodic, seek a contradiction).

3    |    Random Walk on a Group

A group is a set 武 together with an operation ◦ : 武 × 武 → 武 such that

•  for x,y, z ∈ 武 it holds that (x ◦ y) ◦ z = x ◦ (y ◦ z),

•  there exists e ∈ 武 such that for all x ∈ 武 it holds that x ◦ e = e ◦ x = x,

•  for each x ∈ 武 there exists an x−1  ∈ 武 such that x ◦ x−1  = x−1  ◦ x = e

For a distribution µ on countable group 武 the random walk on 武 with steps according to µ is the Markov chain with transition matrix given by px,y = µy◦x−1 .

a)  Show that a random walk on a group is always doubly stochastic.

b)  Show that if µ is symmetric (for all x it holds that µx = µx−1) then a random walk on a group 武 with steps according to µ is reversible.

c)  Are random walks on groups always reversible?  Prove or provide a counterexample.

4    |    Random Walk on a Graph

An (undirected) graph is a set 武 , called vertices, together with a set of pairs of vertices 念 ⊆ {{i, j} : i, j ∈ 武 , i  j}, called edges.

The degree of a vertex x ∈ 武 is deg(x) = |e ∈ 念 : x ∈ e| .  A graph is d-regular if every vertex has degree d.

A random walk on a graph (武 , 念) is the Markov chain P with transition matrix px,y = I [g()(x(})念]  .

a)  Show that π ∝ (deg(x))x∈武  is stationary for a random walk on  (武 , 念).

b)  Show that a random walk on a graph satisfies detailed balance.

c)  Show that a random walk on a d-regular graph is doubly stochastic.

d)  Are random walks on grpahs always doubly stochastic?  Prove or provide a counterexample.

5    |    Coupling

Let 发 be countable and P be a Markov transition matrix on 发.  Suppose that 发 is irreducible.  Suppose there is an x⋆ in 发 and an α > 0 so that for all x ∈ 发 it holds that px,x⋆ ≥ α > 0.  The goal of this problem is to show that there is a 0 < ρ < 1, a C > 0 and a distribution π such that for all x ∈ 发

Σ 'py(x) − πy ' < Cρt .                                                                       (1)

y∈发

a)  Show that ETx∗ < ∞.  Conclude that the process is positive recurrent and has a stationary distribution.   b)  Construct a Markov transition matrix, , on 发2  such that if ((Xt, Yt))t≥0  is a Markov chain with that transition kernel then

•  if X t and Yt are not both at x⋆ then X and Y each transition independently according to P , and

•  if X t and Yt are both at x⋆ then they “couple”, meaning that they remain equal ever after, and transition

(with perfect dependence with each other) according to P.

It is sufficient to describe p(ˆ)(x1 ,y1 ) ,(x2 ,y2 )  for all x1 , x2 , y1 , y2  ∈ 发 .

c)  Which states are transient for  and which are recurrent?

d)  Find a ρ ∈ (0, 1) and a C\  > 0 such that has P(x,y)(T(x*,x*)  > t) ≤ C\ρt for all x, y ∈ 发 . e)  Bound P(x,y)(Xt  Yt).

f)  Show that for any random elements A and B on a countable set 政 ,

Σ |P(A = a) − P(B = a)| ≤ 2P(A  B).      (2)

ae政

g)  Show that there is a 0 < ρ < 1, a C > 0 and a distribution π such that for all x ∈ 发

Σ 'py(x) − πy ' < Cρt .      (3)

ye发

6    |    Discrete Phase-Type Distributions

Let 发 = 社 ∪或 with |社 | ∈ N∪{0}.  Let P be a transition matrix on 发 so that all states in 社 are transient.  Let (Xt)teNn术0贵  be a Markov chain with transition matrix P and initial distribution α .  This question concerns properties of the distribution T或  = min {n ≥ 0 : Xt ∈ 或}.

Let Q = P社 ,社 , q = P社 ,或✶或 .  Let d = |社 | .

a)  Show that q = (I − Q)✶q .

b)  Show that for all i ∈ 社 it holds that Σj qj < 1

c)  Show  that spec(I − Qd)  ⊂ {z ∈ ❈ : |z − 1| < 1}.  What does this tell us about spec(Q) and Σt≥0 Qt? (Hint: you can use the Gershgorin circle theorem)

d)  Express P(T或  = k) in terms of α社  and Q.  Your result should not depend on α或 , P社 ,或, or P或 ,或 .

e)  Compute and simplify P(T或  ≤ k).

f)  Compute and simplify E[T或].

g)  Compute and simplify the moment generating function of T或.  Express its domain in terms of spec(Q).

Since the distribution of T或  doesnt depend on the 或 part of the chain, only on the 社-part (per part d)), we denote it it as T或  ∼ DPHd(α社 , Q).

h)  Show that if Ti ∼ DPHd i (αi, Qi) for i ∈ {1, 2} and T1  ⊥ T2  then T3  = T1 + T2  ∼ DPHd3 (α3 , Q3 ) for some values of (d3 , α3 , Q3 ).  (Hint: d3  = d1 + d2 ).

i)  Show that if Ti ∼ DPHd i (αi, Qi) for i ∈ {1, 2}, and I ∼ Ber(b) and ⊥ (T1, T2 , I) then T3  = IT1+(1−I)T2  ∼ DPHd3 (α3 , Q3 ) for some values of (d3 , α3 , Q3 ).  (Hint: d3  = d1 + d2 ).

7    |    Grad Reading List

Required of graduate students only!!!

Pick one (1) of the following papers to read and then write a short (≈ 1 page) summary of, focusing on how it applies Markov chain methods.

1.  L. Page et al.  The pagerank citation ranking:  Bring order to the web.  Tech. rep. Technical report, stanford University, 1998 http://www.eecs.harvard.edu/~michaelm/CS222/pagerank.pdf

2.  D. Aldous and P. Diaconis.  “Shuffling cards and stopping times” .   The  American Mathematical Monthly 93.5 (1986), pp. 333–348 https://statweb.stanford.edu/~cgates/PERSI/papers/aldous86.pdf

3.  L.  R. Rabiner.   “A tutorial on hidden markov models and selected applications in speech recognition” . Proceedings of the IEEE 77.2 (1989), pp. 257–286 https://ieeexplore.ieee.org/abstract/document/18626 4.  C. E. Shannon.  “A mathematical theory of communication”.  The Bell system technical journal 27.3 (1948), pp. 379–423 https://people.math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf

References