[測度論] DCT 應用 (2) - Simple Fubini-Tonollei Theorem

Theorem:
假設 $\{f_n\}\subset L^1$ 使得 $\sum_{n=1}^\infty\int |f_n| <\infty$。則
(a) $\sum_{n=1}^\infty f_n$ almost everywhere 收斂 。
(b) $\int \sum_{n=1}^\infty f_n = \sum_{n=1}^\infty \int f_n$。

Proof:(a) 令$\{f_n\}\subset L^1$ 使得 $\sum_{n=1}^\infty\int |f_n| <\infty$，則我們有
\[
\int \sum_{n=1}^\infty |f_n| = \sum_{n=1}^\infty\int |f_n|   <\infty
\]故我們知道 $ \sum_{n=1}^\infty |f_n| \in L^1$ 且 $\sum_{n=1}^\infty |f_n|<\infty$ almost everywhere。此表明對 almost every $x$， $\sum_{n=1}^\infty f_n(x) $ (絕對)收斂。令極限
$$ f(x):=\lim_{N\to \infty} \sum_{n=1}^N f_n(x) $$ 故我們僅需證明此 $f \in L^1$。注意到 對任意 $N$， $\lim_N \sum_{n=1}^N f_n \leq \lim_N \sum_{n=1}^\infty |f_n|$ a.e. 故 $f \leq \lim_N \sum_{n=1}^N |f_n|$ a.e. 由於 $\lim_N \sum_{n=1}^N |f_n| \in L^1$ 故 $f \in L^1$。

Proof (b)
要證明 $\int \sum_{n=1}^\infty f_n = \sum_{n=1}^\infty \int f_n$。首先觀察
\[
 \int \sum_{n=1}^N f_n = \sum_{n=1}^N \int  f_n \;\;\;\; (*)
\]由於 $\sum_{n=1}^N f_n \leq \sum_{n=1}^\infty |f_n| \in L^1$ 且 $\sum_{n=1}^N f_n \to f$ a.e. in $L^1$ ，由 Dominated Convergence Theorem 我們有\[
\lim_{N\to \infty} \int \sum_{n=1}^N f_n =  \int \lim_{N\to \infty}\sum_{n=1}^N f_n = \int \sum_{n=1}^\infty f_n\;\;\;\; (**)
\]故對 $(*)$兩邊同取極限並利用上述結果 $(**)$ 可得
\[
\int \sum_{n=1}^\infty f_n = \sum_{n=1}^\infty \int f_n
\]至此證明完畢。$\square$

[測度論] indicator function 為可測函數的充分必要條件

令 $(X,\mathcal{M})$ 與 $(\mathbb{R},\mathcal{L})$ 為可測空間。

Fact: 令 $1_E: (X,\mathcal{M}) \to (\mathbb{R},\mathcal{L})$ 滿足
\[ 1_E(x):=\begin{cases}
      1 & x \in E\\
      0 & x \notin E
   \end{cases}
\]則 $1_E$ 為可測函數 若且唯若 $E \in \mathcal{M}$。

Proof:

$(\Leftarrow)$ 假設 $E \in \mathcal{M}$。我們要證明 $1_E$ 為可測函數。為此，令 $I:=(-\infty, \alpha]$ 為任意區間，我們僅需證明 $1_E^{-1}(I) \in \mathcal{M}$。若 $\alpha \leq 0$，則
$$
1_E^{-1}(I) =\{x:1_E(x) < \alpha\}=\varnothing \in \mathcal{M}
$$ 若 $\alpha >1$ 則
$$
1_E^{-1}(I) =\{x:1_E(x)<\alpha\}=X \in \mathcal{M}
$$最後，若 $0<\alpha \leq 1$ 則
$$
1_E^{-1}(I) =\{x:1_E(x)<\alpha\}=E^c
$$ 由於 $E\in \mathcal{M}$ 且 $\mathcal{M}$ 為 $\sigma$-algebra，故 $E^c \in \mathcal{M}$。至此我們得證 $1_E$ 為可測函數。

$(\Rightarrow)$ 假設 $1_E$ 為可測函數，我們要證明 $E \in \mathcal{M}$。由於 $1_E$ 為可測函數，對任意區間 $I=(-\infty,\alpha]$ 而言，$1_E^{-1}(I) \in \mathcal{M}$。故取 $\alpha =1/2$ 我們有
$$
1_E^{-1}(I):=\{x:\chi_E(x)<1/2\} = E^c \in \mathcal{M}
$$由於 $\cal M $為 $\sigma$-algebra，故 $E\in \mathcal{M}$。$\square$

[測度論] 有限測度空間中，$f_n\to f$ a.e. $\Rightarrow f_n \to f$ in measure

考慮測度空間 $(X,\mathcal{M},\mu)$
Theorem: 令 $\mu(X) <\infty$ 且 $f_n \to f$ a.e. 則 $f_n \to f$ in measure。
Proof:
不失一般性的情況下，假設 $f_n \to f$ everywhere。令 $\alpha > 0$ 我們要證明
\[
\lim_{n}\mu(x: |f_n(x) - f(x)| \geq \alpha ) = 0
\]因為 $f_n \to f$ everywhere (i.e., $f_n \to f$ pointwise) 由極限定義，我們知道給定任意 $\varepsilon >0$ 存在 $N:=N(x)>0$ 使得當 $n\geq N$，
\[
|f_n(x) - f(x)| \leq \varepsilon
\]這表明
\[
x \in \bigcup_N \bigcap_{n \geq N(x)} \{|f_n(x) - f(x)|\leq \varepsilon\}
\]且
\[
X:= \bigcup_N \bigcap_{n \geq N(x)} \{|f_n(x) - f(x)|\leq \varepsilon\}
\]故
\[
X^c = \emptyset  = \bigcap_N \bigcup_{n\geq N(x)} \{|f_n(x) - f(x)|> \varepsilon\}
\]令 $E_N:= \bigcup_{n\geq N(x)} \{|f_n(x) - f(x)|> \varepsilon\} $ 且注意到 $E_N$ 對 $N$ 遞減，且 $\mu(X) <\infty$ 由 測度的 下連續性，我們有
\[
\underbrace{\mu(\cap_N E_N)}_{=\mu(\emptyset)=0} = \lim_N \mu(E_N)
\]故我們得到
\[
\mu(E_N) = \mu(\bigcup_{n \geq N(x)} \{|f_n(x) - f(x)|> \varepsilon\}) \to \mu(\emptyset) = 0
\]將其換成較小的集合上述結果仍然成立，亦即
\[
\mu( \{|f_n(x) - f(x)|> \varepsilon\}) \to  0
\]此表明 $f_n \to f$ in meausre。至此證明完畢。

[線性代數] 若 $A$ 有線性獨立的 columns 則 $A^TA$ 為 symmetric 且 positive definite

Definitions:
1. 我們說一個矩陣 $A$ 為 symmetric 若 $A^T=A$
2. 我們說一個矩陣 $A \in \mathbb{R}^{n \times n}$ 為 正定 (positive definite) 若 對任意 ${\bf x} \in \mathbb{R}^n, \; {\bf x} \neq 0$ 而言，
\[
{\bf x}^T A {\bf x} >0
\]
Comments:
上述positive definite 建構的 ${\bf x}^T A {\bf x} $ 稱作 矩陣的二次式。
判斷矩陣正定的方式有許多，上述只是其中一種，另外還有許多等價定義。下列敘述等價
1. 矩陣 $A$ 為 positive definite
2. 對任意 ${\bf x} \in \mathbb{R}^n, \; {\bf x} \neq 0$ 而言，${\bf x}^T A {\bf x} >0$
3. 矩陣 $A$ 有 正的 特徵值(eigenvalues)
4. 矩陣 $A$ 有 正的 leading principal minors
5. 矩陣 $A$ 有 正 的 pivots

接著我們給出當 $A$ 非方陣的時候，如何找出其對應的 正定矩陣。



==========
Theorem:
$A \in \mathbb{R}^{m\times n}$ 有線性獨立的 columns 則 $A^TA$ 為 symmetric 且 positive definite
==========
Proof:
首先證明 $A^TA$ 為 symmetric。觀察 $(A^TA)^T = A^TA$故得證。

接著證明 $A^TA$ 為 positive definite。令 ${\bf x} \in \mathbb{R}^n, \; {\bf x} \neq 0$ ，觀察
\[
x^TA^TAx = (Ax)^T(Ax) = \|Ax\|^2
\]我們要證明 $\|Ax\|^2>0$，利用反證法：假設若不然，亦即 $\|Ax\|^2 =0$ ，由於因為 $A$ 有線性獨立(linear independent)的 column，記作 ${\bf a}_1,{\bf a}_2,...,{\bf a}_n$ 故由線性獨立的定義，
\[
A{\bf x} = x_1 {\bf a}_1 + x_2 {\bf a}_2 + \cdots x_n {\bf a}_n = {\bf 0}
\]若且唯若 $x_1= x_2 = ... x_n = 0$ 此與原本假設 ${\bf x} \neq 0$ 矛盾，故 $\|Ax\|^2>0$。$\square$


Theorem 2:
任意 positive definite matrix 為 invertible

Proof: 令 $A$ 為 positive definite matrix。利用反證法，假設 $A$ 的反矩陣不存在，此表示存在 ${\bf x} \neq {\bf 0}$ 使得 $A{\bf x} = {\bf 0}$。現在觀察
\[
{\bf x}^T A{\bf x} = \underbrace{{\bf x}^T {\bf 0}}_{={\bf 0}} \;\;\;\;\;(**)
\]但是由於 $A$為 positive definite，我們知道對任意非零向量 ${\bf x}$，${\bf x}^TA{\bf x} > 0$此與 式 $(**)$ 矛盾。故 $A$ 反矩陣存在，換言之$A$ 為 invertible。$\square$



Theorem 3:
若 $A^TA$ 為 invertible，則 $A$ 具有 線性獨立 columns。

Proof:
令 $A:=[{\bf a}_1 \;\; \cdots \;\; {\bf a}_n]$ 其中 ${\bf a}_i$ 為 $A$ 的 columns。我們要證明
$$
\sum_{i=1}^n x_i {\bf a}_i ={\bf 0} \Rightarrow x_i = 0,\;\; \forall i
$$ 注意到對任意 $x_i$，$\sum_{i=1}^n x_i {\bf a}_i ={\bf 0}$ 表示
\[
A{\bf x} = {\bf 0}
\]其中 ${\bf x}:=[x_1\;\;x_2\;\;\cdots x_n]^T$。故
\[
A^T A{\bf x} = A^T {\bf 0} = {\bf 0}
\]由於 $A^TA$ 為 invertible，故 ${\bf x}={\bf 0}$，亦即 $x_i = 0, \;\; \forall i$ 。至此證明完畢。$\square$



Comments:
相關文章參閱：[線性系統] 矩陣的二次式 與 正定矩陣

[泛函分析] 幾何平均與算術平均不等式的一類推廣

回憶中學時期學過的 幾何平均與算術平均關係：令 $a,b \in \mathbb{R}$則 幾何平均 有 算術平均作為上界
\[
\sqrt{ab} \leq \frac{a+b}{2}
\]現在我們將上述結果做一類推廣

Claim: 令 $\theta \in (0,1)$ 且 $a, b \geq 0$則
\[
a^{1-\theta}b^{\theta} \leq (1-\theta)a + \theta b
\]
在給出證明之前我們先做出一些說明

Remarks:
1. 上述 claim 不等式左方：$a^{1-\theta}b^{\theta}$ 一般稱作廣義幾何平均 (Generalized Geometric Mean)。
2. 上述 claim 不等式右方：$(1-\theta)a + \theta b$ 有些學者將其稱作廣義算術平均 (Generalized Arthmic Mean)。但若有涉獵凸分析或者凸最優問題的讀者大概不難看出 此式具備 convex combinaiton 的形式。事實上此不等式在 與凸分析中的 log-convexity 有相關，讀者可自行查閱相關文獻。
3. 上述 Claim 一般又稱作 Auxiliary  Holder inequality.

以下我們給出 Claim 的證明。

Proof of the Claim: 首先做以下觀察：若 $a,b = 0$ 或任一為 $0$ 則不等式自動成立。故在不失一般性的情況下 我們設 $a \geq b >0$ 並且注意到 $a^{1-\theta} = a a^{-\theta}$ 故我們可改寫要證明的不等式如下
\begin{align*}
\left(\frac{b}{a}\right)^\theta \leq (1-\theta) + \theta \frac{b}{a}
\end{align*}
令 $x:=b/a$ 則 $x \in (0,1)$ 且我們僅需證明
\[
x^\theta \leq (1-\theta) +\theta x
\]令 $g(x):=  1-\theta +\theta x - x^\theta $，注意到 $g(1) = 0$ 且 $g(0) = 1-\theta>0$
\[
g'(x) = \theta -\theta x^{\theta-1} < \theta -\theta = 0
\]亦即 $g'(x) <0$ 表示 $g$ 為在 $x \in (0,1)$ 處為遞減函數。故由 $g$ 的連續性，對 $x \in [0,1]$ 我們有
\[
g(x) \geq 0
\]此等價為
\[
1-\theta +\theta x - x^\theta \geq 0
\]同理
\[
x^\theta \leq (1-\theta) +\theta x
\]上述即為我們待證的不等式，至此證明完畢。$\square$

[測度論] Dominated Convergence Theorem

Theorem: Dominated Convergence Theorem DCT  (real-valued functions)
令 sequence $\{f_n\} \subset L^1$ 滿足
(a) $f_n \to f$ almost everywhere
(b) 存在非負函數 $g \in L^1$ 使得 $|f_n| \leq g$ almost everywhere for all $n$
則\[
f \in L^1
\]且
\[
\lim_n \int f_n =\int f
\]
Proof:  先證 $f \in L^1$：由於 $f_n \to f$ almost everywhere  且 $f_n \in L^1$，可知 $f $ measurable (see Proposition 2.11/2.12 )。由於 $|f_n| \leq g$ almost everywhere 故 $|f| \leq g$ almost everywhere，故 $f \in L^1$。

接著我們證 $\lim_n \int f_n =\int f$：注意到 $|f_n| \leq g$ almost everywhere，故我們有
\[
-g \leq f_n \leq g \text{ almost everywhere}
\]換言之，我們有
\[
f_n + g \geq 0\text{ almost everywhere}
\]與
\[
g-f_n \geq 0 \text{almost everywhere}
\]也就是說 $\{f_n + g\}, \{g-f_n\} \in L^+$。由 Fatou Lemma 我們有
\[
\begin{gathered}
  \int {\mathop {\lim \inf }\limits_n } ({f_n} + g) \leqslant \lim \inf \int {({f_n} + g)} ; \hfill \\
  \int {\mathop {\lim \inf }\limits_n } (g - {f_n}) \leqslant \lim \inf \int {(g - {f_n})}  \hfill \\
\end{gathered} \;\;\; (*)
\]注意到上述積分不等式左方，積分項有以下結果 (利用 limsup or liminf 的性質)，我們有 $\mathop {\lim \inf }\limits_n \left( {{f_n} + g} \right) = g + \mathop {\lim \inf }\limits_n {f_n}$ 以及 $$\mathop {\lim \inf }\limits_n \left( {g - {f_n}} \right) = g + \mathop {\lim \inf }\limits_n \left( { - {f_n}} \right) = g - \mathop {\lim \sup }\limits_n {f_n}
$$同理，對於積分不等式右方，我們有
\[\lim \inf \int {({f_n} + g)}  = \lim \inf \left( {\int {{f_n} + \int g } } \right) = \lim \inf \int {{f_n} + \int g } \]與
\[\lim \inf \int {(g - {f_n})  = \int {g + \lim \inf \left( { - \int {{f_n}} } \right)}  = \int {g - \lim \sup \int {{f_n}} } } \]
將此結果帶入 $(*)$ 我們有
\begin{align*}
  &\left\{ \begin{gathered}
  \int {\mathop {\lim \inf }\limits_n } ({f_n} + g) \leqslant \lim \inf \int {({f_n} + g)} ; \hfill \\
  \int {\mathop {\lim \inf }\limits_n } (g - {f_n}) \leqslant \lim \inf \int {(g - {f_n})}  \hfill \\
\end{gathered}  \right. \hfill \\
   &\Rightarrow \left\{ \begin{gathered}
  \int g  + \int {\mathop {\lim \inf }\limits_n } {f_n} \leqslant \lim \inf \int {{f_n} + \int g } ; \hfill \\
  \int g  - \int {\mathop {\lim \sup }\limits_n {f_n}}  \leqslant \int {g - \lim \sup \int {{f_n}} }  \hfill \\
\end{gathered}  \right. \hfill \\
   &\Rightarrow \left\{ \begin{gathered}
  \int {\mathop {\lim \inf }\limits_n } {f_n} \leqslant \lim \inf \int {{f_n}} ; \hfill \\
   - \int {\mathop {\lim \sup }\limits_n {f_n}}  \leqslant  - \lim \sup \int {{f_n}}  \hfill \\
\end{gathered}  \right. \hfill \\
\end{align*} 注意到 $f = \lim_n f_n = \liminf_n f_n = \limsup_n f_n$ ，而且 $\{x: \lim_n f_n \neq f(x)\}$ 的測度為 $0$，故 $\int f = \int \liminf f_n  = \int \limsup f_n$。 現在我們進一步改寫上式
\[\begin{gathered}
  \left\{ \begin{gathered}
  \int f  \leqslant \lim \inf \int {{f_n}} ; \hfill \\
  \int f  \geqslant \lim \sup \int {{f_n}}  \hfill \\
\end{gathered}  \right. \hfill \\
   \Rightarrow \lim \sup \int {{f_n} \leqslant \int {f \leqslant \lim \inf \int {{f_n}} } }  \hfill \\
\end{gathered} \]亦即 $\int f_n \to \int f$。至此得證。$\square$



Remarks:
$\liminf (a_k + b+k) = \liminf a_k + \liminf b_k$ 不全為然。Counter example?

上述等式成立僅僅 $\lim a_k = a$ 則 $\liminf_k (a_k + b_k) = a+\liminf b_k$。

[最佳化] 對原最佳化問題的解是否能"回收"使用到新最佳化問題

令 $J: \mathbb{R}^n \to \mathbb{R}$ ，考慮以下最佳化問題
\[
\min_{x_1,x_2,...x_n} J(x_1,x_2,...x_n)  := J(x_1^*,x_2^*,...,x_n^*)
\]上述 $x_i^*$ 表示最佳解。現在考慮新的目標函數 $G: \mathbb{R}^n \to \mathbb{R}$ 為 上述的 $J:\mathbb{R}^n \to \mathbb{R}$ 額外加上新的函數 $F: \mathbb{R}^n \to \mathbb{R}$，亦即
\[
 G(x_1,x_2,...,x_n) :=J(x_1,x_2,...,x_n) + F(x_1,x_2,...,x_n)
\]我們想問前述獲得的最佳解 $x_1^*,x_2^*,.., x_n^*$ 是否仍然對新的目標函數成立？換句話說，是否能夠 "回收" 之前已經算好的最佳解  $ x_i^*$ 用在新的目標函數 $G$ 上呢。答案是否定的。考慮以下一個簡單的反例

Example:
對 $i=1,2,$，令 $x_i \in [-1,1]$並且將所有符合此條件的 $x_i$ 所成之集合記作 $\mathcal{X}$。現在考慮目標函數 $J(x_1,x_2) := x_1^2+x_2^2$ 並且 我們要求
$$
\min_{x_1,x_2 \in \mathcal{X}} J(x_1,x_2) =  \min_{x_1,x_2 \in \mathcal{X}}x_1^2+x_2^2
$$則最佳解不難發現為 $x_1^*=x_2^*=0$。現在我們考慮新的目標函數，將其記作
$$
G(x_1,x_2) :=J(x_1,x_2) + x_2
$$亦即 $G$ 為舊的目標函數 $J$ 額外加上 線性函數 $x_2 $。我們要求
$$
\min_{x_1,x_2 \in \mathcal{X}} G(x_1,x_2) = \min_{x_1,x_2 \in \mathcal{X}} x_1^2+x_2^2 + x_2
$$其最佳解變成 $x_1^* = 0$ 但 $x_2^* = -1/2 \;\;\; ( \neq 0)$。亦即舊的最佳解不能被"回收"使用。

Comments:
1. 上述謬誤偶爾能在文獻中發現。讀者應小心並盡量避免犯此錯誤。
2. 上述例子中若要使原最佳解可以被回收使用到新最佳解有很多方法，比如限制 可行集 $\mathcal{X}$ 將其改為 $0 \leq x_i \leq 1$ 便是一種。但是否符合需求又是另外一層考量。
3. 上述例子中若把 $\mathcal{X} := \mathbb{R}^2$，則有拘束最佳化問題變成無拘束最佳化問題，但反例仍然成立。

[測度論] 何時 兩可測函數相乘之積分 會與 個別先做積分後再相乘 相等？

Theorem: 
令 $(X,\mathcal{M,\mu})$ 與 $(Y, \mathcal{N},\nu)$ 為任意測度空間。
(a) 若 $f: X \to \mathbb{R}$ 為 $\mathcal{M}$-measurable 且 $g: Y \to \mathbb{R}$ 為  $\mathcal{N}$-measurable 且我們定喔 $h(x,y):=f(x)g(y)$ 則 $h$ 為 $\mathcal{M} \otimes \mathcal{N}$-measurable。
(b) 若 $f \in L^1(\mu)$ 且 $g \in L^1(\nu)$，則 $h \in L^1(\mu \times \nu)$ 且
\[
\int h \; d(\mu \times \nu) = \left( \int f d\mu \right) \left( \int g d \nu \right)
\]

Proof (a):
令 $a \in \mathbb{R}$，考慮 $A:=[a,\infty) \in \mathcal{B}_{\mathbb{R}}$我們要證明
\[
h^{-1}(A) \in \mathcal{M} \otimes \mathcal{N}
\]注意到因為 $f: X \to \mathbb{R}$ 為 $\mathcal{M}$-measurable 且 $g: Y \to \mathbb{R}$ 為  $\mathcal{N}$-measurable ，我們有 $f^{-1}([a,\infty)) \in \mathcal{M}$ 與 $g^{-1}([a,\infty)) \in \mathcal{N}$ 。

現在定義兩個新函數 $F,G: X\times Y \to \mathbb{R}$ 分別滿足 $F(x,y) := f(x), \forall y \in Y$ ，$G(x,y):=g(y), \forall x \in X$，則我們可知 $h $ 為 $F$ 與 $G$ 相乘，亦即 $h=FG$。現在觀察
\begin{align*}
 {F^{ - 1}}(A) &= \left\{ {(x,y) \in X \times Y:F(x,y) \in [a,\infty )} \right\}  \\
  &  = \left\{ {(x,y) \in X \times Y:f\left( x \right) \in [a,\infty ),\forall y \in Y} \right\}  \\
  &  = \left\{ {x \in X:f\left( x \right) \in [a,\infty )} \right\} \times Y  \\
  &  = \underbrace {{f^{ - 1}}\left( {[a,\infty )} \right)}_{\in \mathcal M} \times \underbrace Y_{ \in {\mathcal N}} \in {\mathcal M} \otimes {\mathcal N}
\end{align*}
同理
\begin{align*}
 {G^{ - 1}}(A) &= \left\{ {(x,y) \in X \times Y: G(x,y) \in [a,\infty )} \right\}  \\
  &  = \left\{ {(x,y) \in X \times Y:g\left( x \right) \in [a,\infty ),\forall x \in X} \right\}  \\
  &  =  X \times  \left\{ {y \in Y : g\left( x \right) \in [a,\infty )} \right\} \\
  &  = \underbrace X_{ \in {\mathcal M}} \times \underbrace {{g^{ - 1}}\left( {[a,\infty )} \right)}_{ \in {\mathcal N}} \in {\mathcal M} \otimes {\mathcal N}
\end{align*}亦即，$F,G \in \mathcal{M} \otimes \mathcal{N}$，故由 相乘保證 measurability 性質可知 $FG  \in \mathcal{M} \otimes \mathcal{N}$，亦即 $h  \in \mathcal{M} \otimes \mathcal{N}$。

Proof (b): 首先證明 $h \in L^1(\mu \times \nu)$，亦即要證
\[
\int |h| d(\mu \times \nu) < \infty
\]由於 $|h| \in L^+(X \times Y)$，故由 Tonelli Theorem 可知
\[
\int |h| d(\mu \times \nu) = \int \int |f(x)| |g(y)| d \mu(x) d\nu(y)  <\infty
\]上述不等式成立因為 $f \in L^1(\mu)$ 與 $g \in L^1(\nu)$。故 $h \in L^1(\mu \times \nu)$。

接著由於 $h \in L^1$ ，利用 Fubini theorem 我們可寫
\[
\int h d(\mu \times \nu) = \int \int FG d\mu d\nu = \int f(x) d\mu(x) \int g(x) d\nu(y)
\]即為所求。$\square$

[集合論] $\{x: 2^n < |f(x)| < 2^{n+1}\}$ 為 disjoint

Claim: 令 $f \in L^1$ 且 考慮集合
\[
A_n:=\{x: 2^n < |f(x)| < 2^{n+1}\}
\]其中 $n \in \mathbb{Z}$則對任意 $n \neq m$， $A_n \cap A_m = \emptyset$

Proof: 用反證法，令 $n \neq m$ (假設 $n > m$)，$ A_n \cap A_m \neq \emptyset$。亦即存在 $x_0 \in A_n \cap A_m \neq \emptyset$。此表明 $x_0 \in A_n$ 且 $x_0 \in A_m$。則由 $x_0 \in A_n  $ 我們有 \[
2^n < |f(x_0)| <2^{n+1}
\]同樣地，由 $x_0 \in A_m$ 可推得 \[
2^m < |f(x_0)| < 2^{m+1}
\]換言之，我們有 $|f(x_0)| \in (2^n, 2^{n+1})$ 且 $|f(x_0)| \in (2^{m}, 2^{m+1})$ 得到矛盾，因為 $(2^n, 2^{n+1}) \cap (2^m, 2^{m+1}) = \emptyset $。故 $A_n$ 為 disjoint $\square$

[訊號與系統] LTI系統輸入輸出關係由 Convolution 決定 - 從離散時間觀點

以下我們討論 為何 線性非時變 (Linear Time-Invariant, LTI) 系統 輸入與輸出關係 由 所謂的 convolution 表示。為了避免過多繁雜的數學，以下僅討論離散時間的情況。首先我們需要一些定義的幫助：

========================
Definition: Unit Impulse Function in Discrete-Time (Kronecker Delta)
我們說函數 $\delta: \mathbb{N} \to \{0,1\}$ 為 unit impulse function in discrete-time time 若 $\delta$ 滿足
\[\delta \left[ n \right] = \left\{ \begin{gathered}
  1,\;\;\;\;n = 0 \hfill \\
  0,\;\;\;\; o.w. \hfill \\
\end{gathered}  \right.
\]========================

========================
Definition: Impulse Response
給定任意系統配備輸入 $x[n]$ 與輸出 $y[n]$ 關係為 $y[n] = T\{x[n]\}$其中 $T$ 視為 operator (定義在某函數空間)，若輸入為 $x[n]=\delta[n]$ 則 輸出
\[
h[n] := y[n] = T\{\delta[n]\}
\]稱為系統 $T$ 的 脈衝響應 (impulse response)
========================


========================
FACT: 任意離散訊號 $x[n]$ 可由 $\delta$ 做組合疊加，亦即
\[
x[n] = \sum_{k=-\infty}^{\infty}x[i] \delta[n-k]
\]========================
Proof: 證明顯然，在此不做贅述。$\square$



========================
Definition: Linear System
給定系統 $T$ 滿足以下輸入與輸出關係： $y_1[n]=T\{x_1[n]\}$ 且 $y_2[n] = T\{x_2[n]\}$。現在定義 $x[n] =ax_1[n] + bx_2[n]$ 其中 $a,b \in \mathbb{R}$則我們說系統 $T$ 為 linear 若下列條件成立
\[
y[n] = T\{x[n]\}
\]且 $y[n] = a y_1[n] + b y_2[n]$
========================

Remarks:
上述 系統 $T$  其實可看按作 泛函分析中的 operator。故線性系統 就是 泛函分析中的 線性算子 (linear operator)。



========================
Definition: Time-Invariant System
給定系統 $T$ 滿足以下輸入與輸出關係： $y[n]=T\{x[n]\}$。現在定義 $x[n] :=x[n-d]$  其中 $d \in \mathbb{N}$ 則我們說 $T$ 為 time-invariant 若下列條件成立
\[
y[n-d] = T\{x[n-d]\}
\]========================


有了以上定義的幫助，我們現在有辦法給出以下為何 LTI 系統的輸入輸出關係確實為 convolution。


========================
Theorem: LTI input-output Relationship is Governed by Convolution
給定 線性非時變 (LTI)系統 $L$ 滿足
\[
y[n] = L\{x[n]\}
\]其中 $L$ 為 linear operator，則
\[
y[n] = \sum_k h[k] x[n-k]
\]========================
Proof:
由於 任意 輸入 $x[n]$ 皆可被表為 脈衝函數的 組合：
\[
x[n] = \sum_{k = -\infty}^\infty x[k] \delta[n-k]
\]現在將此訊號作為LTI系統 $L$ 的輸入，則由於 $L$ 為 linear operator 我們有
\begin{align*}
  y[n] &= L\left\{ {x\left[ n \right]} \right\} \\
&= L\left\{ {\sum\limits_{k =  - \infty }^\infty  x [k]\delta [n - k]} \right\} \hfill \\
   &= \sum\limits_{k =  - \infty }^\infty  x[k] L\left\{ \delta [n - k] \right\}  \;\;\;\; (*)
\end{align*} 接著因為 $L$ 為 time-invariant 我們可進一步改寫
\[L\left\{ {\delta [n - k]} \right\} = h\left[ {n - k} \right] \;\;\;\; (**)
\]故由 $(*)$ 與 $(**)$ 可得
\[y[n] = \sum\limits_{k =  - \infty }^\infty  {x[k]h\left[ {n - k} \right]} \]即為所求。$\square$

Comments:
上述 \[
y[n] = \sum\limits_{k =  - \infty }^\infty  {x[k]h\left[ {n - k} \right]}
\]一般又稱作 $x[n]$ 與 $h[n]$ convolution sum。記作
\[
y[n] = x[n] * h[n]
\]

[測度論] DCT 應用：積分例子(1)

試證下列積分
\[
\lim_{n \to \infty} \int_0^\infty (1+(x/n))^{-n} \sin(x/n)dx = 0
\] Proof: 對任意 $x \in [0,\infty)$而言，令 $f_n(x):=(1+(x/n))^{-n} \sin(x/n)$，則 $f_n \to 0$。另外我們注意到 因為 $\sin(x/n) \leq 1 $ 以及利用 附註的 Claim 可知 $(1+x/n)^{-n} \leq e^{-x}$ 故
\[
f_n(x) = (1+(x/n))^{-n} \sin(x/n) \leq e^{-x}
\]現在我們令 $g(x):=e^{-x} \in L^1([0,\infty),m)$。為此我們觀察
\[
\int_0^\infty e^{-x} dx = 1 < \infty
\]故 $g \in L^1([0,\infty),m)$ 且 $|f_n(x)| \leq g(x)$，故由 Dominanted Convergence Theorem 可知
\begin{align*}
\lim_{n \to \infty} \int_0^\infty (1+(x/n))^{-n} \sin(x/n)dx &=  \int_0^\infty \lim_{n \to \infty}(1+(x/n))^{-n} \sin(x/n)dx\\
&=\int_0^\infty  0 dx = 0
\end{align*}
至此證明完畢。$\square$



Claim: 對任意 $x\in(0,\infty)$ 與 $n \in \mathbb{N}$，我們有 \[
(1+x/n)^{-n} \leq e^{-x}
\] Proof:
注意到 $\log (1+x/n)^{-n} = -n \log(1+x/n) \leq -n \frac{x}{n}=-x$。現在對兩邊同取 $exp()$ 可得
\[
(1+x/n)^{-n} \leq e^{-x}
\]至此得證。$\square$

[測度論] 從 測度論 觀點看 Chebyshev Inequality

Chebyshev inequality 是 機率論 中一個非常好用的不等式，此不等式可以從 更廣義的 測度論觀點來證明，且不僅僅局限於使用機率測度。
令 $L^1(\mu)$ 為所有可測函數 $g$ 滿足 $\int |g| d\mu <\infty$ 所成之集合， $\mu$ 為測度。

Claim: Chebyshev Inequality in Measure-Theoretic Setting
令 $g \in  L^1$ 且 $\alpha >0$ 則
\[
\mu (\{x:|g(x)| \geq \alpha\}) \leq \frac{1}{\alpha}\int |g| d\mu
\]
Proof: 令 $\alpha >0$ 觀察
\begin{align*}
  \mu (\{ x:|g(x)| \geqslant \alpha \})  &= \int {{1_{\{ |g(x)| \geqslant \alpha \} }}} d\mu  \hfill \\
   &= \int {{1_{\left\{ {\frac{{|g(x)|}}{\alpha } \geqslant 1} \right\}}}} d\mu  \;\;\;\; (*)
\end{align*} 其中 $1_A(x)$ 為 indicator function 滿足 $x\in A$ 則 $1_A(x) =1$ 反之則 $1_A(x) = 0$。注意到 \[\frac{{|g(x)|}}{\alpha } \geqslant 1 \Rightarrow \frac{{|g(x)|}}{\alpha } \geqslant {1_{\left\{ {\frac{{|g(x)|}}{\alpha } \geqslant 1} \right\}}}\]故 $(*)$ 改寫
\[\int {{1_{\left\{ {\frac{{|g(x)|}}{\alpha } \geqslant 1} \right\}}}} d\mu  \leqslant \int {\frac{{|g(x)|}}{\alpha }} d\mu  = \frac{1}{\alpha }\int {|g(x)|} d\mu \]即為所求。$\square$


Comments:
1. 上述證明儘管相當容易但對於 測度，積分 以及 indicator function 之間的操作頗具巧思值得多加注意。(關於 indicator 相關討論可參閱 [機率論] 指示函數 ( Indicator function) )。

2. 測度論觀點之下的 Chebyshev inequality 證明比 (初等)機率論 或者 數理統計 中的證明來的簡潔許多 (參閱 [機率論]   Chebyshev's Inequality 的推廣型)，讀者不需煩惱積分範圍，是否要分段積分或者考慮是否有無機率密度函數。這現象在較高等的數學中非常常見 (e.g., 泛函分析中將 函數所成的空間 利用線性代數的觀念 將其視為 無窮維向量空間，則不論多複雜的函數都變成該空間上的一"點")，也就是 抽象化之後 可以在某種程度上避免許多複雜的操作，但代價就是抽象化後的觀念需要時間沈澱。

3.  上述 Chebyshev inequality 陳述在 $L^p$ 空間也對。
Claim:
若 $g \in L^p$  其中 $p \in (0,\infty)$ 且 $\alpha >0$ 則
\[
\mu (\{x:|g(x)|^p \geq \alpha^p \}) \leq \frac{1}{\alpha^p}\int |g|^p d\mu
\] 證明雷同，在此不贅述。

[測度論] $\mathbb{R}$ 上的外測度

令 $A \subset \mathbb{R}^*$ ，定義 outer measure $m^*: \mathcal{P}(\mathbb{R}) \to [0,\infty]$ 滿足
\[{m^*}(A): = \mathop {\inf }\limits_{A \subset \bigcup\limits_j^{} {\left[ {{a_j},{b_j}} \right]} } \sum\limits_j^{} {\left( {{b_j} - a_j^{}} \right)} \]

以下我們檢驗幾個性質

Property of Outer Measure on R:
1. $m^*(\emptyset) = 0$
2. Monotonicity: 若 $A \subset B$ 則 $m^*(A) \subset m^*(B)$
3. Subadditivity: $m^*(\cup_j^\infty A_j) \leq \sum_j^\infty m^*(A_j)$

Proof:
1. 取 $A:= \emptyset$ 則任意區間必定涵蓋 $\emptyset$，故 $m^*(\emptyset) = 0$。

2. 若 $A \subset B$ 則存在一組區間 $I_{j} := [a_{j}, b_{j}]$, $j=1,2...$  使得 $A \subset B \subset \cup_{j=1}^\infty [a_{j}, b_{j}]$，故由定義可知 $m^*(A) \subset m^*(B)$。

3. 首先觀察 $m^*(A_j)$ 定義中有 infimum，故給定 $\varepsilon>0$ 可知必定存在一組區間 $I_{j,k} := [a_{j,k}, b_{j,k}]$, $k=1,2...$  使得 $A_j \subset \cup_{k=1}^\infty [a_{j,k}, b_{j,k}]$
\[
\sum\limits_k^{} {\left( {{b_{j,k}} - a_{j,k}^{}} \right)}  < {m^*}(A_j) + \frac{\varepsilon}{10^j} \]由此可知
\[
\sum\limits_{j,k}^{} {\left( {{b_{j,k}} - a_{j,k}^{}} \right)}  < \sum\limits_j^{} {\left( {{m^*}(A_j) + \varepsilon } \right)}  = \sum_j^\infty {m^*}(A_j) + \varepsilon \sum\limits_j^{} {\left( {\frac{1}{{{{10}^j}}}} \right)}
\]注意到區間 $I_{j,k}$, $j,k=1,2,...$ 涵蓋 $\cup_j A_j$，亦即
\[ \cup _j^\infty {A_j} \subset \bigcup\limits_{j,k}^{} {\left[ {{a_{j,k}},{b_{j,k}}} \right]}
\]故由前述的性質2 (Monotonicity)，
\[{m^*}( \cup _j^\infty {A_j}) \leqslant \sum\limits_{j,k}^{} {\left( {{b_{j,k}} - a_{j,k}^{}} \right)}  < \sum_j^\infty {m^*}(A_j) + \varepsilon \sum\limits_j^{} {\left( {\frac{1}{{{{10}^j}}}} \right)} \]由於 $\varepsilon$ 為任取，讓 $\varepsilon \to 0$ 我們有
$$m^*(\cup_j^\infty A_j) \leq \sum_j^\infty m^*(A_j)$$即為所求。$\square$


Remarks:
上述的性質可以用來定義外測度對任意空間可以給出更為一般的(公理化)定義如下：

Definition: Abstract Outer Measure
我們說 $\mu^*: \mathcal{P}(X) \to [0,\infty]$ 為 abstract outer measure on $X$若下列條件成立
1. $m^*(\emptyset) = 0$
2. Monotonicity: 若 $A \subset B$ 則 $m^*(A) \subset m^*(B)$
3. Subadditivity: $m^*(\cup_j^\infty A_j) \leq \sum_j^\infty m^*(A_j)$

[數學分析] MVT應用：$\sin(x)$ 上界為 $x$

回憶我們在微積分或者高等微積分中，對於連續且可導函數的一個重要結果：均值定理。

================
均值定理 (Mean Value Theorem, MVT):
若函數 $f$ 在 閉區間 $[a,b]$ 連續  且 在開區間 $(a,b)$ 上可導，則存在 $c \in (a,b)$ 使得
\[
f(b) - f(a) = f'(c)(b-a)
\]================

現在我們來看一個 MVT 很棒的應用，可以幫助我們找到 $\sin(x)$ 除了 $1$ 以外 稍微更細緻的上界 ($ x $ 夠小的時候)。

==========
FACT: 若 $x \in \mathbb{R}$ 且 $x \geq 0$ 則 $\sin(x) \leq x$。
==========

Proof: 以下我們分幾個 case討論：
CASE 1: 首先觀察當 $x = 0$，則 $\sin(0)  = 0 \leq 0$ 自動成立。

CASE 2: 當 $0 < x < 1$ ，令 $f(t) := \sin(t)$ 則對任意 $t \in \mathbb{R}$， $f$ 為 連續且可導，故 $f$ 在 $(0,x)$ 區間亦為可導。由 MCT 可知 存在 $c \in (0,x)$ 我們有
\[
f(x) - f(0) = f'(c) (b-a) \Rightarrow \sin(x) - 0 =  \cos(c) x
\]換言之，我們有
\[
\cos(c) x = \sin(x)
\]由於 $|\cos(.)| \leq 1$ 故 $\sin(x) \leq x$。

CASE 3: 最後我們考慮 $x \geq 1$ 情況，由於 $|\sin(x)| \leq 1$ 故 當 $x\geq 1$ 時，
\[
\sin(x) \leq x
\]自動成立。至此得證。$\square$


Remarks:
上述結果可以進一步推廣，亦即我們不需要假設 $x$ 為非負：對任意 $x \in \mathbb{R}$，
\[
|\sin(x)| \leq |x|
\]證明雷同在此不做贅述。讀者可以試著證明看看。

[測度論] 非遞減函數必定可測

Claim: 令 $f: \mathbb{R} \to \mathbb{R}$ 為 非遞減(nondecreasing)函數，則 $f$ 為 $(\mathcal{B}_{\mathbb{R}},\mathcal{B}_{\mathbb{R}})$-measurable 其中 $ \mathcal{B}_{\mathbb{R}}$ 為 Borel $\sigma$-algebra

Proof:
令 $a\in \mathbb{R}$，並取開集 $E:= (a, \infty) \in \mathcal{B}_{\mathbb{R}}$ 。我們要證明 $f$ 可測，亦即要證明
\[
f^{-1}(E) = f^{-1}(a, \infty) = \{x \in \mathbb{R} : f(x) > a\} \in \mathcal{B}_{\mathbb{R}}
\]此等價證明 $f^{-1}(E)$ 為 $\mathbb{R}$ 上 interval 即可(因為所有 interval on $\mathbb{R}$ generates $\mathcal{B}_{\mathbb{R}}$)。故取 $c:= \inf f^{-1}(E)$ ，則我們僅需證明
\[
f^{-1}(E) = (c, \infty)
\]  以下我們分兩種情況討論：
Case 1: 若 $c \in f^{-1}(E)$ ：首先證明 $\subset :$ 取 $x \in f^{-1}(E)$，則 $f(x) > a$，則此 $x \geq c$ by infimum 性質。接著我們證明 $\supset$: 取 $x \in (c, \infty)$，則對任意 $x \geq c$ 而言 ，由於 $f$ 為非遞減，我們知道
\[
f(x) \geq f(c) > a
\]此表明 $x \in f^{-1}(E)$，故至此我們證得 \[
f^{-1}(E) = (c, \infty)
\]

Case 2: 若 $c \notin f^{-1}(E)$：首先證明 $\subset :$ 取 $x \in f^{-1}(E)$，則 $f(x) > a$，則此 $x \geq c$ by infimum 性質。接著我們證明 $\supset$: 取 $x \in (c, \infty)$，則對任意 $x \geq c$ 而言 ，必定存在 $y \in f^{-1}(E)$ 使得 $x > y \geq c $。由於 $f$ 為非遞減，我們知道
\[
f(x) \geq f(y)  > a
\]此表明 $x \in f^{-1}(E)$，故至此我們證得 \[
f^{-1}(E) = (c, \infty)
\]
由上述兩類情況總結可知 $f^{-1}(a,\infty) = (c, \infty) $ interval，故其必定為 Borel measurable 且 $f$ is Borel measurable。$\square$

[測度論] 連續函數必定可測

令 $X,Y$ 為 metric space，定義 $\mathcal{B}_X$ 與 $\mathcal{B}_Y$ 為其上的 Borel $\sigma$-algebra (generated by some open sets)。

Claim: $f:X \to Y$ 為連續函數 on $X$，則 $f$ 為 $(\mathcal{B}_X, \mathcal{B}_Y)$-measurable。

Proof: 令 $E \in \mathcal{B}_Y$，我們要證明 $f^{-1}(E) \in \mathcal{B}_X $。注意到若 $E$ 為 任意 set generates $\mathcal{B}_Y$; e.g., $E$ be open set，則由連續函數性質可知 $f^{-1}(E)$ 亦為 open ，故 $f^{-1}(E) \in \mathcal{B}_X$。$\square$