2018年10月12日 星期五

[線性代數] 若 $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$



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


2018年9月8日 星期六

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

回憶中學時期學過的 幾何平均與算術平均關係:令 $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$

2018年7月11日 星期三

[測度論] 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$。



2018年6月27日 星期三

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

令 $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$,則有拘束最佳化問題變成無拘束最佳化問題,但反例仍然成立。


2018年5月9日 星期三

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

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$

2018年5月4日 星期五

[集合論] $\{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$

2018年4月25日 星期三

[訊號與系統] 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]
\]

2018年4月11日 星期三

[測度論] 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$

2018年4月4日 星期三

[測度論] 從 測度論 觀點看 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
\] 證明雷同,在此不贅述。

2018年3月27日 星期二

[測度論] $\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|
\]證明雷同在此不做贅述。讀者可以試著證明看看。

2018年3月6日 星期二

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

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$

2018年1月9日 星期二

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

令 $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$