next up previous
Next: Computing the Optimal Policy Up: Calculating the Return Value Previous: Example:

   
Properties of the transition matrix:

We show that the matrix $(I-\lambda P_d)^{-1}$ is order conserving.

Lemma 5.3   The following holds for a probability matrix P and $0 \leq\lambda<1$:
1.
If $\Vert\vec{u}\Vert \ \geq \ 0$ then $\Vert(I-\lambda
P)^{-1}\vec{u}\Vert \ \geq \ \Vert\vec{u}\Vert \ \geq \ 0$
2.
If $\Vert\vec{u}\Vert \ \geq \ \Vert\vec{v}\Vert$ then $\Vert(I-\lambda
P)^{-1}\vec{u}\Vert \ \geq \ \Vert(I-\lambda P)^{-1}\vec{v}\Vert$
3.
If $\Vert\vec{u}\Vert \ \geq \ 0$ then $\Vert\vec{u}^{T}(I-\lambda P)^{-1}\Vert\
\geq\ \Vert\vec{u}^{T}\Vert \geq 0$

Proof:Since $\Vert P\Vert= 1$ then $\Vert\lambda P\Vert\leq 1$. By theorem [*]

\begin{eqnarray*}(I - \lambda P_{d})^{-1}\vec{u} = \vec{u} + \underbrace{(\lambd...
... + \ldots}_{(sum\ of\ positive\
vectors )} \geq \vec{u} \geq 0
\end{eqnarray*}


$\Box$



Yishay Mansour
1999-11-24