Markov chain contraction mapping

Let $P$ be an $n \times n$ transition matrix with all positive entries. Let $d$ be the smallest entry of $P$ .

Let $\vec{y}$ be a column vector with $M_{0}$ being the largest entry of $\vec{y}$ and $m_{0}$ being the smallest entry of $\vec{y}$ .

Let $M_{1}$ be the largest entry of $P \vec{y}$ and let $m_{1}$ be the smallest entry of $P \vec{y}$ .

Then $M_{1} - m_{1} \leq (1 - 2 d) (M_{0} - m_{0})$ .

Since $0 \leq (1 - 2 d) < 1$ , the difference between the largest and smallest entries of $\vec{y}$ gets smaller after applying $P$ . This is called contraction mapping.

Proof

By construction, $d > 0$ .
If $n \geq 2$ , then $d \leq \frac{1}{2}$ .
So $0 \leq 1 - 2 d < 1$ .

Construct a "worst-case scenario" for both $M_{1}$ and $m_{1}$ :

Let $\vec{ρ}$ be the $i^{t h}$ row of $P$ , with $\vec{ρ} = (\begin{matrix} * & * & \dots & * & d_{i} \end{matrix})$ where $d_{i}$ the smallest element of $\vec{ρ}$ .

b-i)
To maximize $M_{1}$ ,

Let $\vec{y} = (\begin{matrix} M_{0} \\ M_{0} \\ ⋮ \\ M_{0} \\ m_{0} \end{matrix})$ . Minimize $m_{0}$ .
Then

P \vec{y} = (\begin{matrix} * & * & \dots & d_{1} \\ * & * & \dots & d_{2} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ * & * & \dots & d_{n} \end{matrix}) (\begin{matrix} M_{0} \\ M_{0} \\ ⋮ \\ M_{0} \\ m_{0} \end{matrix}) = (\begin{matrix} (1 - d_{1}) M_{0} + d_{1} m_{0} \\ (1 - d_{2}) M_{0} + d_{2} m_{0} \\ ⋮ \\ (1 - d_{n}) M_{0} + d_{n} m_{0} \end{matrix}) $ $ S o e a c h e l e m e n t o f $ P \vec{y} $ l o o k s l i k e $ (1 - d_{i}) M_{0} + d_{i} m_{0} $ . I f $ d $ t h e m i n i m a l $ d_{i} $, $ M_{1} \leq (1 - d) M_{0} + d m_{0} $ . b - i i) T o m i n i m i z e $ m_{1} $, L e t $ \vec{y} = (\begin{matrix} m_{0} \\ m_{0} \\ ⋮ \\ m_{0} \\ M_{0} \end{matrix}) $ . M a x i m i z e $ M_{0} $ . T h e n $ $ P \vec{y} = (\begin{matrix} * & * & \dots & d_{1} \\ * & * & \dots & d_{2} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ * & * & \dots & d_{n} \end{matrix}) (\begin{matrix} m_{0} \\ m_{0} \\ ⋮ \\ m_{0} \\ M_{0} \end{matrix}) = (\begin{matrix} (1 - d_{1}) m_{0} + d_{1} M_{0} \\ (1 - d_{2}) m_{0} + d_{2} M_{0} \\ ⋮ \\ (1 - d_{n}) m_{0} + d_{n} M_{0} \end{matrix}) $ $ S o e a c h e l e m e n t o f $ P \vec{y} $ l o o k s l i k e $ (1 - d_{i}) m_{0} + d_{i} M_{0} $ . I f $ d $ t h e m i n i m a l $ d_{i} $, $ m_{1} \geq (1 - d) m_{0} + d M_{0} $ . b - i i i) T h e r e f o r e, $ M_{1} - m_{1} \leq (1 - d) M_{0} + d m_{0} - ((1 - d) m_{0} + d M_{0}) = (1 - 2 d) (M_{0} - m_{0}) $ . T h u s, $ M_{1} - m_{1} \leq (1 - 2 d) (M_{0} - m_{0}) $ . Q E D