40. Blackwell's Sufficient Conditions for a Contraction
40. Blackwell 压缩映射的充分条件
在讨论 Blackwell 充分条件之前，先引入一些术语。
40.1 完备度量空间
定义 40.1（度量空间） 度量空间是有序对 \((M,d)\)，\(M\) 是集合，\(d\) 是 \(M\) 上的度量，即函数 \(d:M\times M\to\mathbb{R}\) 使对任意 \(x,y,z\in M\)： 1. 非负性 \(d(x,y)\ge0\)； 2. 不可分辨者同一性 \(d(x,y)=0\Leftrightarrow x=y\)； 3. 对称性 \(d(x,y)=d(y,x)\)； 4. 三角不等式 \(d(x,z)\le d(x,y)+d(y,z)\)。
定义 40.2（柯西序列） 度量空间 \((M,d)\) 中，\(M\) 内序列 \(\{x_n\}_{n=1}^{\infty}\) 称柯西序列，若 \(\forall\varepsilon>0\) \(\exists N\in\mathbb{N}\) 使 \(m,n\ge N\Rightarrow d(x_m,x_n)<\varepsilon\)。
定义 40.3（完备度量空间） 设 \((M,d)\) 为度量空间。\((M,d)\) 称完备，若 \(M\) 中每个柯西序列都在 \(M\) 中收敛；称 \(S\subseteq M\) 完备，若 \(S\) 中每个柯西序列都在 \(S\) 中收敛。
定理 40.1 设 \((M,d)\) 度量空间、\(S\subseteq M\)。若 \(S\) 紧则 \(S\) 完备。
注记 40.1 完备度量空间的直观是：空间 \(M\) 中任意两点之间没有缺失的点，这与紧性的定义相吻合。
40.2 Blackwell 压缩映射的充分条件
命题 40.1（Blackwell 充分条件） 设 \(X\subseteq\mathbb{R}^l\)，\(B(X)\) 为有界函数 \(f:X\to\mathbb{R}\) 之空间。\((B(X),d)\) 为度量空间，度量 \(d\) 为上确界范数（sup norm，\(\|f\|_S=\sup\{|f(x)|:x\in S\}\)），即 \(\forall f,g\in B(X)\)，\(d(f,g)=\|f-g\|\)。设算子 \(T:B(X)\to B(X)\) 满足： 1. 单调性：\(f,g\in B(X)\) 且 \(f(x)\le g(x)\) \(\forall x\in X\)，蕴含 \((Tf)(x)\le(Tg)(x)\) \(\forall x\in X\)； 2. 折现性：存在某 \(\beta\in(0,1)\) 使 \([T(f+a)](x)\le(Tf)(x)+\beta a\)，对 \(\forall f\in B(X)\)、\(a\ge0\)、\(x\in X\)，其中 \((f+a)(x)\) 是由 \((f+a)(x)=f(x)+a\) 定义的函数。
则 \(T\) 是模 \(\beta\) 的压缩映射。
证明 对任意 \(f,g\in B(X)\)，\(f(x)\le g(x)+\|f-g\|\) (40.1)。则由单调性 \((Tf)(x)\le(T(g+\|f-g\|))(x)\)，由折现性 \(\le(Tg)(x)+\beta\|f-g\|\)，即 $$ > (Tf)(x)-(Tg)(x)\le\beta\|f-g\| \tag{40.2} > $$ 在 (40.1) 中互换 \(f\) 与 \(g\) 的角色：\(g(x)\le f(x)+\|f-g\|\)，同理得 $$ > (Tg)(x)-(Tf)(x)\le\beta\|f-g\| \tag{40.3} > $$ 合并 (40.2)、(40.3)：\(|(Tf)(x)-(Tg)(x)|\le\beta\|f-g\|\)。因对任意 \(x\in X\) 成立，故度量空间 \((B(X),d)\) 中的压缩条件 \(\|Tf-Tg\|\le\beta\|f-g\|\) 成立，即 \(d(Tf,Tg)\le\beta d(f,g)\)。\(\blacksquare\)
40. Blackwell's sufficient conditions for a contraction
Before talking about Blackwell's sufficient conditions, let's first introduce some terminologies.
40.1 Complete metric space
Definition 40.1 (Metric space) A metric space is an ordered pair \((M,d)\) where \(M\) is a set and \(d\) is a metric on \(M\), i.e. a function \(d:M\times M\to\mathbb{R}\) such that for any \(x,y,z\in M\), the following holds: 1. non-negativity: \(d(x,y)\ge0\); 2. identity of indiscernibles: \(d(x,y)=0\Leftrightarrow x=y\); 3. symmetry: \(d(x,y)=d(y,x)\); 4. triangle inequality: \(d(x,z)\le d(x,y)+d(y,z)\).
Definition 40.2 (Cauchy sequence) In a metric space \((M,d)\), a sequence \(\{x_n\}_{n=1}^{\infty}\) in \(M\) is called a Cauchy sequence if for \(\forall\varepsilon>0\), there exists an \(N\in\mathbb{N}\) such that if \(m,n\ge N\) then \(d(x_m,x_n)<\varepsilon\).
Definition 40.3 (Complete metric space) Let \((M,d)\) be a metric space. Then \((M,d)\) is said to be complete if every Cauchy sequence converges in \(M\). And we said that \(S\subseteq M\) is complete if every Cauchy sequence in \(S\) converges in \(S\).
Theorem 40.1 Let \((M,d)\) be a metric space and \(S\subseteq M\). If \(S\) is compact then \(S\) is complete.
Remark 40.1 The intuition for complete metric space is that there is no missing point between any two points in space \(M\), which coincides with the definition of compactness.
40.2 Blackwell's sufficient conditions for a contraction
Proposition 40.1 (Blackwell's sufficient conditions) Let \(X\subseteq\mathbb{R}^l\) and let \(B(X)\) be a space of bounded functions \(f:X\to\mathbb{R}\). And \((B(X),d)\) is a metric space where metric \(d\) is the sup norm (i.e. \(\|f\|_S=\sup\{|f(x)|:x\in S\}\)), i.e. \(\forall f,g\in B(X)\), \(d(f,g)=\|f-g\|\). Let \(T:B(X)\to B(X)\) be an operator satisfying: 1. monotonicity: \(f,g\in B(X)\) and \(f(x)\le g(x)\) for all \(x\in X\), implies \((Tf)(x)\le(Tg)(x)\) for all \(x\in X\); 2. discounting: there exists some \(\beta\in(0,1)\) such that \([T(f+a)](x)\le(Tf)(x)+\beta a\), for all \(f\in B(X)\), \(a\ge0\), \(x\in X\) where \((f+a)(x)\) is the function defined by \((f+a)(x)=f(x)+a\).
Then \(T\) is a contraction with modulus \(\beta\).
Proof For any \(f,g\in B(X)\), \(f(x)\le g(x)+\|f-g\|\) (40.1). Then, by monotonicity \((Tf)(x)\le(T(g+\|f-g\|))(x)\), and by discounting \(\le(Tg)(x)+\beta\|f-g\|\), i.e. $$ > (Tf)(x)-(Tg)(x)\le\beta\|f-g\| \tag{40.2} > $$ Then reverse the role of \(f\) and \(g\) in (40.1): \(g(x)\le f(x)+\|f-g\|\), which similarly implies $$ > (Tg)(x)-(Tf)(x)\le\beta\|f-g\| \tag{40.3} > $$ Combining equation (40.2) and (40.3), we have that \(|(Tf)(x)-(Tg)(x)|\le\beta\|f-g\|\). Since this holds for any \(x\in X\), we have the contraction condition in the metric space \((B(X),d)\): \(\|Tf-Tg\|\le\beta\|f-g\|\), or \(d(Tf,Tg)\le\beta d(f,g)\). \(\blacksquare\)