Markov Chains: a functional view

  • Laplacian; Adjoints; Harmonic fn; Green’s fn; Forward Eqn; Backward Eqn.
  • Markov Chains and Martingales; Green’s Functions and occupancy; Potential functions; time-reversal and adjoints.


The following results will help us develop a more function analytic view of Markov chains which will be useful when we extend Markov chains to continuous time and space. Further the potential theory view is useful when considering optimal control and applications such as electrical networks.

Unless stated otherwise, in this section, X=(X_t: t\in \mathbb{Z}_+ is a discrete time Markov chain on \mathcal{X} is transition matrix P and initial distribution \lambda.

Def. [Laplacian] The Laplacian of a Markov chain is

Def. [Adjoint] The adjoint of \Delta is \Delta^* : = \Delta^{\top}.

Def. [Harmonic] The function h is harmonic if \Delta h(x) = 0 \forall x \in \mathcal{X}

Def. [Green’s function] G = \Delta^{-1} is the Green’s function of \Delta.

(If the inverse \Delta^{-1} exists)

Def. [Resolvent] R_{\alpha}=(I-\alpha P)^{-1}, \alpha \in (0,1), is the resolvent of P.

Forward and Backward Equations

Def. [Forward Equation] The Forward Equation is defined to be

or equivalently

where \partial_t p_t: = p_{t+1} - p_t.

Def. [Backward Equation] The Backward Equation is defined to be

Ex 1. Show that if p solves the forward equation with p_0 = \lambda for some initial distribution \lambda, then

where {X} is a Markov chain with initial distribution \lambda and transition matrix {P}.

Ex 2.  Suppose at (fixed) time T you get a reward V(X_T) show that

solves the backward equation, with condition h_T(x)=V(x).

Ex 3. [Markov Chains and Martingales] Show that a random variables (X_t)_{t\geq 0} are a Markov chain if and only if, for all bounded functions f:\mathcal{X} \rightarrow \mathbb{R},

is a Martingale with respect the filtration of X.

Ex 4. [Harmonic Fns are Martingales] Show that if a function h(x) is harmonic then h(X_t) is a Martingale.

Greens Functions

Ex 5. Show that G= I + P + P^2 +...

Ex 6. Show that the Green’s function is given by

Ex 7. Argue that the Green’s function G_{xy} is not defined for recurrent states y (for which x communicates with y).

Ex 8. [Resolvent is a Green’s fn] Let P^{\alpha} be the Markov chain that either with probability \alpha evolves according to P and with probability 1-\alpha goes to an exist state \emptyset where it remains for all time.

(So the resolvant is the Greens function of a absorbed Markov chain.)

Ex 9. Show that the resolvent is given by

where {\mathcal G}(\alpha) is a Geometric RV with parameter \alpha.

Potential Theory

This is really just more resolvants.

Ex 10. [Markov Chains and Potential Functions] Let r:\mathcal{X}\rightarrow \mathbb{R}_+ be a bounded function. Argue that for \beta \in (0,1)

solves the equation

Ex 11. [Continued] Show that R is the unique bounded solution this equation.

Ex 12. [Continued] Show that if the bounded function \tilde{R}:\mathcal{X} \rightarrow \mathbb{R}_+ satisfies

then \tilde{R}(x) \geq R(x), x\in\mathcal{X}.

Ex 13. Let \partial \mathcal{X} be a subset of \mathcal{X} and let T be the hitting time on \partial\mathcal{X} i.e. T=\inf\{ t : X_t \in \partial \mathcal{X}\} and take f: \partial X \rightarrow \mathbb{R}_+ argue that

solves the equation

Ex 14. [Continued] Argue that

solves the equation

(Compare the above with Bellman’s equation.)


Answers

Ans 1. The calculation agrees with the definition of a Markov chain through Matrix multiplication.

Ans 2. 

as required.

Ans 3. 

X is P-Markov iff for all bdd f

which holds iff for all bdd f

(i.e. iff M^f is .) (Notice the same result holds for indicator functions, i.e. take f(x)=\mathbb{I}[x=x_t].)

Ans 4. Directly follows from [3] and the definition of a Harmonic function above.

Ans 5. G= ( I - P)^{-1}, so (I-P) G = I. Therefore G = I + P G. Iterating gives

(where we, rather sketchily, assume convergence to zero of P^n G.)

Ans 6.

Ans 7. Obvious from [6].

Ans 8. See that

Applying a similar calculation to [5] gives

(Note now \alpha^n P^n converges). So G^{\alpha}= (I-\alpha P) = R_{\alpha}.

Ans 9. This is really just the same as [6].

Ans 10.

Ans 11. Take any \hat{R} then \hat{R}-R=\beta P(\hat{R}-R). So

which, since \beta <1, only holds if \hat{R} = R .

Ans 12. Suppose that \tilde{R} is a positive fn such that \tilde{R}(x) \geq r(x) +\beta P\tilde{R} (x) . Repeated substitution gives

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s