Introduction to Probability · Problem 11.20

Random Walks — Grinstead & Snell

Mathematics — Probability · markov-chains-payoff

Problem

Consider a game played as follows: You are given a regular Markov chain with transition matrix

\mathbf{P}

, fixed probability vector

\mathbf{w}

, and a payoff function

\mathbf{f}

which assigns to each state

s_i

an amount

f_i

which may be positive or negative. Assume that

\mathbf{w}\mathbf{f} = 0

. You watch this Markov chain as it evolves, and every time you are in state

s_i

you receive an amount

f_i

. Show that your expected winning after

n

steps can be represented by a column vector

\mathbf{g}^{(n)}

, with

\mathbf{g}^{(n)} = (\mathbf{I} + \mathbf{P} + \mathbf{P}^2 + \cdots + \mathbf{P}^n)\mathbf{f}.

Show that as

n \to \infty

\mathbf{g}^{(n)} \to \mathbf{g}

with

\mathbf{g} = \mathbf{Z}\mathbf{f}