- 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, is a discrete time Markov chain on is transition matrix and initial distribution .

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

**Def.** [Adjoint] The adjoint of is .

**Def. **[Harmonic] The function is harmonic if

**Def. **[Green’s function] is the Green’s function of .

(If the inverse exists)

**Def. **[Resolvent] , , is the resolvent of .

### Forward and Backward Equations

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

or equivalently

where .

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

**Ex 1.** Show that if solves the forward equation with for some initial distribution , then

where is a Markov chain with initial distribution and transition matrix .

**Ex 2. ** Suppose at (fixed) time you get a reward show that

solves the backward equation, with condition .

**Ex 3. **[Markov Chains and Martingales] Show that a random variables are a Markov chain if and only if, for all bounded functions ,

is a Martingale with respect the filtration of .

**Ex 4. **[Harmonic Fns are Martingales] Show that if a function is harmonic then is a Martingale.

### Greens Functions

**Ex 5.** Show that

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

**Ex 7.** Argue that the Green’s function is not defined for recurrent states (for which communicates with ).

**Ex 8. **[Resolvent is a Green’s fn] Let be the Markov chain that either with probability evolves according to and with probability goes to an exist state 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 is a Geometric RV with parameter .

### Potential Theory

This is really just more resolvants.

**Ex 10. **[Markov Chains and Potential Functions] Let be a bounded function. Argue that for

solves the equation

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

**Ex 12. **[Continued] Show that if the bounded function satisfies

then , .

**Ex 13. **Let be a subset of and let be the hitting time on i.e. and take 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. **

is -Markov iff for all bdd

which holds iff for all bdd

(i.e. iff is .) (Notice the same result holds for indicator functions, i.e. take .)

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

**Ans 5. **, so . Therefore G = I + P G. Iterating gives

(where we, rather sketchily, assume convergence to zero of .)

**Ans 6.**

**Ans 7.** Obvious from [6].

**Ans 8.** See that

Applying a similar calculation to [5] gives

(Note now converges). So .

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

**Ans 10.**

**Ans 11.** Take any then . So

which, since , only holds if .

**Ans 12.** Suppose that is a positive fn such that . Repeated substitution gives