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

$\Delta f(x) = \sum_y P_{xy} \Big( f(x) -f(y) \Big) = (I-P)f(x)$

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

$p_{t+1} -p_t = - p_t \Delta$

or equivalently

$\partial_t p_t = - \Delta^* p_t$

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

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

$h_{t+1}(x) - h_t(x) = \Delta h_{t+1}(x).$

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

$p_t(x) = \mathbb{P}_\lambda \big( X_t = x \big)$

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

$h_t(x) = \mathbb{E}\left[ V(X_T) | X_t=x\right]$

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}$ ,

$M^f_t = f(X_t) - f(X_0) - \sum_{\tau =0}^{t-1} \Delta f(X_\tau)$

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

$G_{xy} = \mathbb{E} \left[ \sum_{t=0}^{\infty} \mathbb{I} [ X_t = y ] \Bigg| X_0=x \right]$

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

$R^{\alpha}_{xy} = \mathbb{E} \left[ \sum_{t=0}^{\infty} \alpha^t \mathbb{I} [ X_t = y ] \Bigg| X_0=x \right] = \mathbb{E} \left[ \sum_{t=0}^{{\mathcal G}(\alpha)} \mathbb{I} [ X_t = y ] \Bigg| X_0=x \right]$

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)$

$R(x) = \mathbb{E}_x \left[ \sum_{t=0}^{\infty} \beta^t r(X_t) \right]$

solves the equation

$%\label{MC:Resolve} R(x) = \beta (PR) (x) + r(x), \qquad x\in\mathcal{X}.$

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

$\tilde{R}(x) \geq \beta (P\tilde{R}) (x) + r(x), \qquad x\in\mathcal{X}.$

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

$R(x) = \mathbb{E}_x \left[ \sum_{t<T} r(X_t) + f(X_T) \mathbb{I} \left[ T < \infty \right] \right]$

solves the equation

$\begin{aligned} R(x) = (PR)(x) + r(x), \qquad x \notin\partial\mathcal{X}\\ R(x) = f(x), \qquad x \in \mathcal{X}.\end{aligned}$

Ex 14. [Continued] Argue that

$R_{t}(x) = \mathbb{E}_x \left[ \sum_{\tau=0}^{t - 1} r_\tau(X_\tau) + r_t(X_t) \right], \qquad t\in \mathbb{Z}_+$

solves the equation

$R_{t+1}(x) = (PR_t)(x) + r_t(x)$

(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.

$h_t(x) = \mathbb{E}\left[ V(X_T) | X_{t}=x\right] = \sum_y \mathbb{E} \left[ V(X_t) | X_{t+1} = y \right] P_{xy} = P h_{t+1} (x)$ as required.

Ans 3.

$M^f_t-M^f_{t-1} := f(X_{t}) -f(X_{t-1}) - (P-I)f(X_{t-1}) = f(X_t) -Pf(X_{t-1})$

$X$ is $P$ -Markov iff for all bdd $f$

$\mathbb{E}[f(X_t)|\mathcal{F}_{t-1}]= \mathbb{E}[f(X_{t})|X_{t-1}]=Pf(X_{t-1})$

which holds iff for all bdd $f$

$\mathbb{E}[M^f_t-M^f_{t-1}|\mathcal{F}_{t-1} ]:= 0.$

(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.

$\begin{aligned} G_{xy} = \sum_{t=0}^\infty P^{t} = \sum_{t=0}^{\infty} \mathbb{E} \left[ \mathbb{I} [ X_t = y ] \big| X_0=x \right] = \mathbb{E} \left[ \sum_{t=0}^{\infty} \mathbb{I} [ X_t = y ] \Bigg| X_0=x \right].\end{aligned}$

Ans 7. Obvious from [6].

Ans 8. See that

$P^{\alpha} = \left( \begin{array}{cc} \alpha P & (1-\alpha)\bm{1} \\ 0 & 1 \\ \end{array} \right)$

Applying a similar calculation to [5] gives

$G^{\alpha} = I + \alpha P G = I + \alpha P + \alpha^2 P^2 G = .... = I + P + \alpha^2 P^2 +...$

(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.

$R(x) = r(x) + \mathbb{E}_x \bigg[ \beta \mathbb{E}\bigg[ \sum_{t=1}^\infty \beta^{t-1} r(X_t)\Big| X_1\bigg]\bigg]=r(x) + \mathbb{E}_x\bigg[\beta R(X_1)\bigg] = r(x)+\beta (PR)(x)$

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

$|| \hat{R}-R ||_\infty \leq \beta \sum_y P_{xy} |R(y) - R(y) | \leq \beta || \hat{R} -R||_\infty$

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

$\begin{aligned} \tilde{R}(x) \geq r(x) + \mathbb{E}_x\left[ \beta \tilde{R}(X_1)\right]\geq ... &\geq \mathbb{E}_x \bigg[ \sum_{t=0}^T \beta^t r(X_t) \bigg]+ \beta^{T+1} \mathbb{E}_x \bigg[\tilde{R}(X_{T+1})\bigg]\\ &\geq \mathbb{E}_x \bigg[ \sum_{t=0}^T \beta^t r(X_t)\bigg] \xrightarrow[T\rightarrow\infty]{ }R(x). \end{aligned}$

Forward and Backward Equations

Greens Functions

Potential Theory

Answers

Share this:

Like this:

Leave a Reply Cancel reply