积分

1)Double Series

定义为$\sum_{m,n=1}^\infty a_{mn}$，当两个下标以不同的方式趋于无穷的时候，可能使得结果级数收敛或者收敛到不同的值，甚至发散。当收敛和两个下标趋于无穷的方式无关的时候称为Double Series收敛。
Theorem: 当Double Series都是正数的时候，$\sum_{m,n=1}^\infty a_{mn}$收敛等价于$\sum_{n=1}^\infty \sum_{m=1}^\infty a_{mn}$和$\sum_{m=1}^\infty \sum_{n=1}^\infty a_{mn}$都收敛并且收敛的结果相等。

2)单调函数

单调函数在每点(除了$\pm\infty$)的左右极限都存在并且有限。不连续的点最多有可数多个。

3)step function

$\theta: I \rightarrow R$，有限个区间的集合$I_j$，满足$\cup_i I_j \subseteq I$，对应的有限个实数$c_j$，$\theta$定义为 $$\theta=\left\{ \begin{array}{l l} c_j & \quad \text{if $x \in I_j$}\\ 0 & \quad \text{if $x \in I\setminus \cup_i I_j$}\\ \end{array} \right.$$

4)划分

$S=\{I_1, I_2, \cdots, I_n\}$称为$I$的一个部分划分，如果其元素的交集最多为元素的端点，并集包含在$I$中。
$V_S(f,I)=\sum_{j=1}^n | f(b_j)-f(a_j) |$称为$S$对应的$f$的variation，记$V(f,I)=\sup_S V_S(f,I)$称为total variation，显然$0 \leq V(f,I)\leq \infty$。
例子：step function，$V(f,I)=\sum_{r=1}^m k_r$所有jump的和。

例子：函数$f(x)=\sin(1/x),\ x\in (0, 1)$，部分划分 $$S=\left\{ I_j=\left[ \frac{2}{(j+1)\pi}, \frac{2}{j\pi} \right],\ j=1,2,\cdots, n\right\}$$ $S$对应的variation $V_S(f, I)=n$，所以$V(f, I)=\infty$。

5)$V(f, I)$有界的函数

Lemma：如果$f$在$I=(a, b)$上$V(f, I)$有界，定义函数$g(x)=V(f, I_x)$，其中$I_x=(a, x), x\in I$，那么$g(x)$是单调增函数。
证明：$I_x$的部分划分也是$I$的部分划分。

Theorem:如果$f$在$I=(a, b)$上$V(f, I)$有界，当且仅当$f$可以表达成两个有界，单调增函数的差。
证明：$f(x)=[V(f, I_x)] - [V(f, I_x) - f(x)]$

Corollary：如果$f$在$I=(a, b)$上$V(f, I)$有界，$f$在$I$内点的左右极限都存在。
证明：$f$写成单调函数的差，根据单调函数的性质可得。

绝对连续可以用划分定义：对任意的$\epsilon > 0$可以找到$\delta$，使得任意满足总长度小于$\delta$的部分划分$S$其上的$f$的variation $V_S(f,I) < \epsilon$。

Theorem:有限区间上绝对连续可以推出$V(f, I)$有界。

6)黎曼可积

定义$A(g)$为$g$和$x$轴之间的有符号的面积，其中$g$为任意step function。

黎曼可积：对任意$\epsilon > 0$，存在两个step function $g^\epsilon$和$G^\epsilon$满足：
(i)$g^\epsilon\leq f\leq G^\epsilon$
(ii)$A(G^\epsilon)-A(g^\epsilon) \leq \epsilon$


如果$f:[a, b] \rightarrow R$有界，最多可数个不连续的点，那么$f$黎曼可积。

黎曼可积的函数序列可以收敛到一个黎曼不可积的函数。

7)单调增函数诱导的测度

如果$\alpha : R \rightarrow R$是单调增函数，那么定义$x$轴上的$\alpha\text{-measure}$是区间到$R$的映射，$\mu_\alpha(\cdot)$把区间映射到$\alpha$在区间上最右边可能的单边极限减去最左边可能的单边极限，比如 $$\mu_\alpha(\ [a, b)\ )=\alpha(b-)-\alpha(a-)\\ \mu_\alpha(\ (a, b]\ )=\alpha(b+)-\alpha(a+) $$ 这个测度的可以看成函数$\alpha$在区间$I$上的变化，注意$\alpha\text{-measure}$只和端点的$\alpha$函数值以及区间的开闭有关，和内点的函数值无关，只有是单调的就好。

8)$\alpha\text{-summable}$

简单集合(simple set)：$R$的子集，并且可以表达为有限个区间的不交并。性质：简单集合的$\alpha\text{-measure}$可以表达成有限和
$\alpha\text{-finite}$：如果简单集合的$\alpha\text{-measure}$有限，称为$\alpha\text{-finite}$。
step function的support：根据step function的定义，区间上的step function $\theta:I \rightarrow R$的support是简单集合。
$\alpha\text{-summable}$：如果区间上的step function $\theta:I \rightarrow R$的support是$\alpha\text{-finite}$。

对每个$\alpha\text{-summable}$的step function $\theta:I \rightarrow R$定义一个和$\alpha\text{-measure}$相关的实数 $$A_\alpha(\theta)=\sum_{j=1}^nc_j\mu_\alpha(I_j)$$ 其中$\mu_\alpha$是$\alpha\text{-measure}$，$c_j$是step function在不同区间上的取值。如果把measure理解为长度，$c_j$理解为高度，那么这个式子就是面积。
注意上面的和式，比较复杂的情况是$I_j$的端点开$(a, b)$闭$(a, b]$会的到不同的$\alpha\text{-measure}$，而区间的开闭取决于step function $\theta:I \rightarrow R$在端点$b$是左连续还是右连续，甚至左右都不连续。(计算的顺序是先得step function $\theta$的取值区间划分，这时候区间上的$\theta$函数值以及区间的开闭已定，算区间的$\alpha\text{-measure}$，然后算和式。 )

特殊情况，如果$\alpha\text{-measure}$函数在$c$是一个jump，那么$[c, c]$的$\alpha\text{-measure}:\ \alpha(c+)-\alpha(c-)$不是0，如果求sum的step function $\theta$在$c$点也不连续，也就是$c$也是$\theta$的jump，那么在单点区间上的"$\alpha\text{-sum}$"就不是0。

9)Lebesgue-Stieltjes积分

一个一般的区间上的非负函数$f:I\rightarrow R$，对$f$ admissible的step function序列$\{\theta_j\}$就是满足下面条件的序列：
(i)$\alpha\text{-summable}$
(ii)非负
(iii)$f(x) \leq \sum_{j=1}^\infty \theta_j(x)$

对上面的$f$定义一个实数： $$L_\alpha(f)=\inf\left\{\sum_{j=1}^\infty A_\alpha(\theta_j)\right\},\quad \{\theta_j\} \text{ is $f$ admissible}$$ 例子：定义$f: [0, 1]\rightarrow R$： $$f(x)=\left\{ \begin{array}{l l} 1 & \quad \text{if $x$ is rational}\\ 0 & \quad \text{if $x$ is irrational or $x=0$ or $x=1$ }\\ \end{array} \right.$$ 令$r_j$是$[0,1]$里的第$j$个有理数： $$\theta_j(x)=\left\{ \begin{array}{l l} 1 & \quad \text{if $x = r_j$}\\ 0 & \quad \text{if $x \neq r_j$}\\ \end{array} \right.$$ $\theta_j$是$f$ admissible的step function序列，如果定义测度函数为$\alpha^*(x)=x$那么 $$A_{\alpha^*}(\theta_j)=1\cdot \alpha^*(\ [r_j,r_j]\ )=1\cdot 0=0$$ 由此可知： $$L_{\alpha^*}(f)=0$$ Theorem：如果$\{f_j\}$为区间上的函数序列，并且其和$\sum_j f_j$在区间上逐点收敛，$L_\alpha$对结果和函数$\sum_j |f_j|$的求值小于对单个函数求值$L_\alpha(|f_j|)$然后求和。有限的情况： $$L_\alpha(|f_1|+|f_2|) \leq L_\alpha(|f_1|) + L_\alpha(|f_2|)$$

Theorem：$L_\alpha(|f-f_n|)\rightarrow 0 \Rightarrow L_\alpha(|f_n|) \rightarrow L_\alpha(|f|)$

Lebesgue-Stieltjes积分的定义：对一个区间上的函数$f$，如果存在一个序列的$\alpha\text{-summable}$ step function $\{\theta_j\}$满足 $$L_\alpha(|f-\theta_n|) \rightarrow 0$$ 定义积分 $$\int_I fd\alpha = L_\alpha(f^+)-L_\alpha(-f^-)$$ 如果取测度$\alpha(x)=x$那么积分称为Lebesgue积分。(注意这里没要求$\{\theta_j\}$是$f$ admissible的)

描述简单但是很难证明的事实：上面的积分运用到$\alpha\text{-summable}$ step function上就是实数$A_\alpha(\theta)$。

10)$L_\alpha$的性质

首先$L_\alpha$是对非负函数定义的，对任意一个函数$f$
(i)$L_\alpha(f^+) \leq L_\alpha(|f|)$并且$-L_\alpha(f^-) \leq L_\alpha(|f|)$
(ii)$L_\alpha(|af|) = |a|L_\alpha(|f|)$。(a=0的时候要求式子有意义)

11)Lebesgue积分

类似黎曼积分可以定义$f$下面的step function，定义一个实数 $$l_x(f)=sup\sum_{j=1}^\infty A(\phi_j)$$ 可以证明，当$L_x(f)$有限并且$f$可测的时候这两个实数相等。

有可能在一个区间上黎曼奇异积分存在，但Lebesgue积分不存在，因为Lebesgue可积蕴含Lebesgue绝对可积，有些函数黎曼奇异可积但是不黎曼绝对可积。

12)Lebesgue-Stieltjes积分的基本性质

Lemma：$f$ Lebesgue-Stieltjes可积的必要条件，存在一个step function序列$\{\theta_j\}$满足$L_\alpha(|f - \theta_n|) < \frac{1}{n}$。
Theorem(不是收敛定理)：Lebesgue-Stieltjes可积函数序列$\{f_n\}$满足$L_\alpha(|f-f_n|)\rightarrow 0$，那么$f$ Lebesgue-Stieltjes可积，并且$f$的积分等于$\{f_n\}$的积分的极限。
Theorem：$f$ Lebesgue-Stieltjes可积，那么 $$\left| \int_I f d\alpha \right| \leq \int_I |f|d\alpha$$ Theorem：Lebesgue-Stieltjes可积函数的线性组合可积。

13) Null Functions and Null Sets

Null Function：如果$L_\alpha(|f|) = 0$，$f$称为Null Function，可以证明$f$和$|f|$的积分为0。
Null Set：$R$上characteristic function为Null Function的set。
任何集合$A$的characteristic function记为$\chi_A: A\rightarrow 1$。

$f=0 \text{ a.e.}$ 的意思是$\chi_{\{ x\ |\ f(x)\neq 0 \}}$是null。

Theorem：$f$是null$\Longrightarrow f=0\text{ a.e.}$。
证明：对任意的常数$c > 0$，集合$A=\{ x\ |\ |f(x)| \geq c \}$是null，因为$\displaystyle \frac{|f(x)|}{c}\geq 1 \geq \chi_A(x)$运用$L_\alpha$得 $\displaystyle 0 = L_\alpha( \frac{|f(x)|}{c} ) \geq L_\alpha( \chi_A(x))$，所以$A$是null，也就是$\chi_A$是null。

可以把$|f|$的值域分成可数个区间$[1, \infty),\ [1/2, 1),\ [1/3, 1/2),\ \cdots$记为$\{I_j\}$，而集合$\{ x\ |\ |f(x)| \neq 0 \}$的characteristic function是可数个集合$\{x\ |\ f(x) \in I_j\}$的characteristic function $\chi_{\{x\ |\ f(x) \in I_j\}}$的和，因为他们都满足$f\neq 0$，也就是出现在$\{ x\ |\ |f(x)| \neq 0 \}$中，而且可以证明，$\{ x\ |\ |f(x)| \neq 0 \}$中的任何一个元素只出现在唯一的一个$\{x\ |\ f(x) \in I_j\}$中。

运用$L_\alpha$对正函数的可数次可加性可得 $$L_\alpha\left( \chi_{\{ x\ |\ |f(x)| \neq 0 \}} \right)\leq \sum_{n=1}^\infty L_\alpha\left(\chi_{\{x\ |\ f(x) \in I_j\}}\right) =\sum 0 = 0$$ 即$\chi_{\{ x\ |\ |f(x)| \neq 0 \}}$是null。注意characteristic function都是非负的，所以上面省略了null条件里的绝对值。

Theorem：$f$是null$\Longleftarrow f=0\text{ a.e.}$。
证明：上面是构造null set序列(利用了他们的characteristic function)，这里直接构造null function序列，还是划分$|f|$的值域$(n-1, n]$。

14) 收敛定理

Monotone Convergence Theorem：$\{f_n\}$是单调($f_{n-1} \leq f_n$)可积函数序列，并且$\lim_{n\to\infty}(\int_If_nd\alpha)$有限，如果$f_n\to f\text{ a.e.}$，那么$f$可积并且$\int_If_nd\alpha \to \int_If d\alpha$。

Fatou's Lemma：$\{f_n\}$是非负函数序列，$f_n\to f\text{ a.e.}$，那么$f$可积$\Longleftrightarrow \lim_{n\to\infty}(\inf_{m\geq n}\int_I f_m(x)d\alpha)$有限。

Dominated Convergence Theorem：$\{f_n\}$是单调($f_{n-1} \leq f_n$)可积函数序列，并且$f_n(x)\leq \lambda(x)$，$\lambda(x)$可积，如果$f_n\to f\text{ a.e.}$，那么$f$可积。

15) 积分理论的扩展

(i)扩展底部集合

前面定义的积分的值是两个$L_\alpha$的差，而$L_\alpha$是由定义在简单集合(区间的并)上的step function定义的。第一种扩张积分概念的办法是把简单集合换成更一般的集合，也就是$\alpha\text{-measurable}$集合，这个集合的定义需要$\alpha\text{-measurable}$函数。
$\alpha\text{-measurable}$函数：可以被一个$\alpha\text{-summable}$的step function序列$\text{ a.e.}$逼近的函数，也就是，存在$\{\theta_j\}$满足： $$\lim_{n\to\infty}\theta_n=f\text{ a.e.}$$ $\alpha\text{-measurable}$集合：$R$的子集，并且characteristic function是$\alpha\text{-measurable}$函数。

上面的要求主要是为了定义新集合类的$\alpha\text{-measure}$，前面已经定义了简单集合的$\alpha\text{-measure}$，现在希望定义$\alpha\text{-measurable}$集合$X$的$\alpha\text{-measure}$为： $$\mu_\alpha(X)=\int_R \chi_X d\alpha$$ 这个定义要求characteristic function $\chi_X$在$R$上可积，实际上有这样的定理：

Theorem：$f$对$\alpha$可积$\Longleftrightarrow f$ 是$\alpha\text{-measurable}$并且$L_\alpha(|f|)$有限。

对于$L_\alpha(|f|)$无限的情况，我们记$X$的$\alpha\text{-measure}$为$\infty$。

现在希望定义任何一个可积函数$f$在一个$\alpha\text{-measurable}$集合$X$上的积分为： $$\int_X f d\alpha=\int_R f\chi_X d\alpha$$ 要这个定义有意义就要求函数$f\chi_X$在$R$上是可积的，首先$|f\chi_X|\leq|f|$所以$L_\alpha(|f\chi_X|)$有限，而$f\chi_X$又是两个$\alpha\text{-measurable}$函数的乘积($f$可积蕴含$f\ \alpha\text{-measurable}$)，所以也是$\alpha\text{-measurable}$的；这两个条件可以推出$f\chi_X$在$R$上是可积的。

(ii)扩展测度函数

前面定义的测度函数$\alpha$是单调增函数，通过使用大的函数类$V(f, I)$有界的函数，可以扩展积分的概念，任何区间上的类$V(f, I)$有界函数可以扩展到$R$上而不改变$V(f, I)$。根据$V(f, I)$有界函数的性质，这样的$\alpha$可以表达成单调函数的差： $$\alpha=\alpha_1-\alpha_2$$ 在区间$J$上如果函数$f$对$\alpha_1$和$\alpha_2$都可积，那么定义其对$\alpha$的积分为： $$\int_Jfd\alpha=\int_Jfd\alpha_1-\int_Jfd\alpha_2$$ 同样可以定义区间$J$的$\alpha$测度： $$\mu_\alpha(J)=\mu_{\alpha_1}(J)-\mu_{\alpha_2}(J)$$

16) 积分计算方法

Theorem：如果积分区间可以分解成有限个区间的不交并，那么原积分等于在这些区间上积分的和。

Theorem：如果测度函数$\alpha=\sum_{j=1}^mc_j\alpha_j$，其中$c_j$非负有限，$f$对每个$\alpha_j$可积，那么 $$\int_I f d\alpha=\sum_{j=1}^m c_j\int_I f d\alpha_j$$

Theorem：如果测度函数$\alpha$在积分区间的端点连续，那么积分区间在这个端点是开还是闭不影响积分的结果。

Theorem：对任意的区间$I$有$$\int_I 1 d\alpha=\mu_\alpha(I)$$

Theorem：如果测度$\alpha$在开区间$I$上是常数，那么任何函数在这个区间上的积分为0。

Theorem：如果$f(a)$有定义，那么$$\int_{[a,a]}f d\alpha=f(a)[\alpha(a^+)-\alpha(a^-)]$$

Theorem：如果测度$\alpha$在开区间$I$上可微，那么$$\int_I fd\alpha=\int_If\alpha'dx$$

Note：有几个定理是要在开区间上才成立，原因是测度$\alpha$可能在区间的端点不连续，需要特殊处理，计算中可以把闭区间分成端点和开区间的并，然后分别运用定理。

Note：对所有测度$\alpha$不连续的点都要单独处理，区间要从这点分割开。

17) 积分计算的定理

连续严格增函数把区间映射到区间，根据这个有变量替换定理：

Theorem：$u:R\to R$是连续严格增函数，则 $$\int_I(f\circ u)du=\int_{u(I)}fdx$$ 进一步的如果$u$在区间上可微，那么 $$\int_I(f\circ u)du=\int_I(f\circ u)u'dx=\int_{u(I)}fdx$$ 最后如果$\alpha$是一个单调增函数那么 $$\int_I(f\circ u)d(\alpha\circ u)=\int_{u(I)}fd\alpha$$ Integration by Parts

在黎曼积分理论里分部积分是根据公式 $$\int_a^bfg'dx+\int_a^bf'gdx=[fg]_a^b$$ 在Lebesgue-Stieltjes积分理论里公式变为 $$\int_Ifdg+\int_Igdf=\mu_{fg}(I)+\sum_{a\in S}A(a)$$ 这里要求$f,g$是$V(f, I)$有界的，$S$为$f,g$都不连续的点的集合，$A=[f(a)-\frac{1}{2}(f(a^+)+f(a^-))]\mu_g([a,a])+[g(a)-\frac{1}{2}(g(a^+)+g(a^-))]\mu_f([a,a])$

18) 和微分的联系

Fundamental Theorem of Calculus：$f$在$I=[a, b]$上可积，$I_t=[a, t], J_t=[t, b]$，令 $$F(t)=\int_{I_t} fdx,\quad G(t)=\int_{J_t}fdx$$ 那么$F(t), G(t)$绝对连续，并且 $$F'(t)=f(t),\quad G'(t)=-f(t)\ a.e.$$ 反过来，如果$F:I\to R$绝对连续，那么它$a.e.$可微，并且$F'$可积，$F(t)=\int_{I_t}F'dx+C$

交换积分和微分的顺序

Differentiation Under the Integral：

19) 多元积分

首先定义矩形$I_1\times I_2\subseteq R^2$上的乘积测度$\alpha_1\times\alpha_2\text{-measure}$为： $$\mu_{\alpha_1\times\alpha_2}(I_1\times I_2)=\mu_{\alpha_1}(I_1)\times\mu_{\alpha_2}(I_2)$$ 然后定义二维简单集合，简单集合是不相交的矩形的和： $$S=\cup_{j=1}^m(I_{1j}\times I_{2j})$$ 其$\alpha_1\times\alpha_2\text{-measure}$为： $$\mu_{\alpha_1\times\alpha_2}(S)=\sum_{j=1}^m\mu_{\alpha_1\times\alpha_2}(I_{1j}\times I_{2j})$$ 定义simple function为在这$m$个矩形上取常数，其他时候取$0$的函数： $$\theta(x, y)=\left\{ \begin{array}{l l} c_j & \quad \text{if $x \in I_{1j}\times I_{2j}$}\\ 0 & \quad \text{if $x \in R^2\setminus S$}\\ \end{array} \right.$$ 这个函数图象下面的体积可以类似一维时候的定义，记为$A_{\alpha_1\times\alpha_2}(\theta)$

对一个定义在$R^2$上的任意函数可以定义二维积分 $$\iint_{R^2}f d(\alpha_1\times\alpha_2)$$ 一般是把二维积分(double integral)转化为repeated integral。同样的函数的二维积分有两种方式的repeated integral对应，他们并不总相等，例如 $$\int_0^1\int_0^1\frac{x-y}{(x+y)^3}dxdy\neq\int_0^1\int_0^1\frac{x-y}{(x+y)^3}dydx$$ 他们相等的条件是函数在积分区域上绝对可积，也就是：

Fubini's Theorem：如果$f:R^2\to R$是$\alpha_1\times\alpha_2\text{-measurable}$函数，那么下面3个式子 $$\iint_{R^2}|f|d(\alpha_1\times\alpha_2),\quad \int_R\int_R|f|d\alpha_1 d\alpha_2,\quad \int_R\int_R|f|d\alpha_2 d\alpha_1$$ 任何一个存在蕴含下面3个式子相等 $$\iint_{R^2}f d(\alpha_1\times\alpha_2),\quad \int_R\int_R f d\alpha_1 d\alpha_2,\quad \int_R\int_R f d\alpha_2 d\alpha_1$$

随机变量的收敛

1)$\{X_n\}$收敛到$X$ a.e.：概率空间$\Omega$去掉一个null set后，其中任何一点$\omega$有，$X(\omega)$有限，并且： $$\lim_{n\rightarrow \infty}X_n(\omega)=X(\omega)$$ 2)almost uniform convergence：任给一个正数$\epsilon$，记$A_m(\epsilon)=\cap_{n=m}^\infty\{ |X_n-X| \leq \epsilon \}$，这个集合的意思是，集合里的任何一个元素$\omega$，$m$往后所有$X_n(\omega)$和$X(\omega)$的差小于$\epsilon$，(也就是解不等式得到的$\Omega$上的集合然后取交集)。
上面的正数$\epsilon$和$\omega$的选取无关，所以这个收敛是uniform的，这种收敛称为almost uniform convergence。在有限测度空间上，这种收敛和a.e.收敛是等价的。

收敛a.e.等价于对所有的$\epsilon > 0$有$\lim_{m\rightarrow \infty}P(A_m(\epsilon))=1$。

3)收敛in probability：对任意的正数$\epsilon$有 $$\lim_{n\rightarrow \infty}P\{|X_n-X| > \epsilon\} = 0$$ 看成解不等式的$\Omega$上的集合，然后求概率，注意解不等式得到的集合不一定是单调的，最极端的情况，每个$n$得到的满足不等式的集合都不同，他们的并集的概率测度不为0，所以收敛a.e.是更强的条件，收敛a.e.的时候那个坏的0测度集是固定的。

4)柯西条件：
$\{X_n\}$收敛到$X$ a.e，$\lim_{m\rightarrow \infty}P\{|X_n-X_{n'}| > \epsilon \text{ for some }n' > n \geq m\} = 0$
收敛in probability，$\lim_{n, n'\rightarrow \infty }P\{|X_n-X_{n'}| > \epsilon\} = 0$

5)：集合的极限
极限的一个看法是去掉序列的前面有限个元素不影响收敛的情况和结果，例如对于集合的序列$E_j$，定义 $$F_m=\cup_{n=m}^\infty E_n$$ $F_m$的含义是序列去掉前面$m-1$个剩下集合的并，所以如果有一个元素$\omega$出现在无穷多个集合里那么它永远不会被扔掉，所以$\omega$在所有的$F_m$中。也就是在 $$\cap_{m=1}^\infty F_m$$ 里，称为infinitely often。

$F_m$是下降序列，所以根据概率的连续性，其概率的极限等于极限集合(i.o.)的概率。

如果$\sum_{n=1}^\infty P(E_n)$有限，根据无穷级数的性质这个无穷和的余项趋于0，也就是 $$\sum_{n=m}^\infty P(E_n)\to 0$$ 根据概率的次可加性，这个$F_m$的概率比这个余项要小，所以也趋于0，也就是说

Theorem：如果$\sum_{n=1}^\infty P(E_n)$有限，那么$E_n$里i.o.的元素集合的概率测度为0。

一个收敛到0的随机变量序列$X_n$和一个正数$\epsilon$定义了集合序列$E_n=\{|X_n| > \epsilon\}$。almost uniform convergence里面的$A_m^c(\epsilon)$看成$F_m$。

6)：收敛in pr蕴含存在子序列收敛a.e.
证明：不是一般性，设收敛到0，收敛in pr那么对任意$\frac{1}{2^k}$可以找到，一个$X_{n_k}$使得集合$E_k=\{X_{n_k} > \frac{1}{2^k}\}$的概率测度小于$\frac{1}{2^k}$，有$\sum_{k=1}^\infty P(E_k)$有限。

独立

0) 考虑离散的特殊r.v. $X, Y$

$P(X=a_i)=p_i,\quad P(Y=b_j)=q_j$满足$a_ib_j$各不相等，他们的乘积r.v.是 $$P(XY=a_ib_j)=P[(X=a_i)\cap (Y=b_j)]$$ $Cov$是乘积的期望和期望的乘积都是$a_ib_j$的线性组合，不过系数一个是 $$P[(X=a_i)\cap (Y=b_j)]$$ 另一个是$$P(X=a_i)P(Y=b_j)$$ 很明显如果两个随机变量独立，两个线性组合是相等的。可以看出，对于两个r.v.独立，他们具体取什么值不重要，重要的是他们诱导的在底部概率空间上的划分。

$Cov$把两个r.v.映射到一个实数，一个性质是可以穿过$\sum$。

0.5) 独立和乘积的关系

如果用乘积测度的角度看独立，$P(A), P(B)$是低一维的测度，$P(A\cap B)$是高一维的测度，其实$P(x\in A)=P(x\times y \in A\times \Omega_2)$

联合分布其实就是给出了$X,Y$诱导的底部概率空间的两个划分之间的所有可能的交集的概率测度。

0.6) r.v.的和的分布，$X,Y$各给出了底部概率空间的两个划分 集合$\{P=s\} = \{P(X+Y)=s\}$是满足的$X,Y$取值的配置的交集的概率测度的和。

如果两个r.v.独立，那么表达可以进一步简化，就是交集的概率等于概率的乘积。

1) $n$个r.v. $\{X_j\ |\ 1\leq j\leq n\}$独立的意思是对任意$\{B_j\in\mathcal{B}^1\ | \ 1\leq j\leq n\}$有： $$P\left\{ \cap_{j=1}^n (X_j\in B_j)\right\}=\prod_{j=1}^n P(X_j\in B_j)$$

2) 根据b.f. $\mathcal{B}^1$可以由区间$(-\infty, x]$生成，所以下面也是独立的条件 $$P\left\{ \cap_{j=1}^n (X_j\leq x_j)\right\}=\prod_{j=1}^n P(X_j\leq x_j)$$

3) 如果用这些r.v.在$(\mathcal{R}^1, \mathcal{B}^1)$诱导的测度$\mu_j$，以及在$(\mathcal{R}^n, \mathcal{B}^n)$诱导的乘积测度$\mu^n$，那么独立的条件可以表达成： $$\mu^n\left(\times_{j=1}^n B_j\right)=\prod_{j=1}^n \mu_j(B_j)$$

4) 两个独立随机变量$X_1, X_2$诱导的测度满足：$\mu^2(dx, dy)=\mu_1(dx)\mu_2(dx)$，所以 $$ \begin{align} E(XY) &= \int_{\Omega}X(\omega)Y(\omega)P(d(\omega))=\iint_{\mathcal{R}^2} xy\ \mu^2(dx, dy)\\ &= \int_{\mathcal{R}^1}x\ \mu_1(dx) \int_{\mathcal{R}^1}y\ \mu_2(dx)\\ &= E(X)E(Y) \end{align} $$

5) 如果$\{f_j\ |\ 1\leq j\leq n\}$是可测函数，那么$\{ f_j(X_j) \}$是独立的。

6) $\mu^n$对应的n-dimensional distribution function： $$F(x_1, \cdots, x_n)=P\left\{X_j\leq x_j, 1\leq j\leq n\right\}=\mu^n\left(\times_{j=1}^n(-\infty, x_j]\right)$$ 独立的条件可以写成： $$F(x_1, \cdots, x_n)=\prod_{j=1}^nF_j(x_j)$$ 7) 离散概率空间$\{\Omega_j\}$，他们的乘积空间为$\Omega^n=\Omega_1\times\cdots\times\Omega_n$，如果$X_i, X_j$分别为$\Omega_i, \Omega_j$上的随机变量，那么定义$\Omega^n$上的随机变量$\widetilde{X}_i, \widetilde{X}_j$，$\Omega^n$的点记为$\omega=(\omega_1, \cdots, \omega_n)$ $$ \widetilde{X}_i(\omega)= X_i(\omega_i)\\ \widetilde{X}_j(\omega)= X_j(\omega_j) $$ 是独立的。
注意： $$ \begin{align} \{\omega\ |\ \widetilde{X}_j(\omega)\in B_j\}=\Omega_1\times\cdots\times\Omega_{j-1}\times\{\omega_j\ |\ X_j(\omega_j)\in B_j\}\times\Omega_{j+1}\times\cdots\times\Omega_{n} \end{align} $$

8) $n$维立方体$\mathcal{U}^n=\{(x_1, \cdots, x_n)\ |\ 0\leq x_j\leq 1\}$，测度空间$(\mathcal{R}^n, \mathcal{B}^n, m^n)$，那么b.f. $\mathcal{B}^n$在$\mathcal{U}^n$上的trace是一个概率空间。$\{f_j\ |\ 1\leq j\leq n\}$为$n$个单变量可测函数，定义 $$X_j(x)=f_j(x_j)$$ 为$\mathcal{U}^n$上的$n$个独立的r.v.。

9) 也可以用$(\mathcal{R}^1, \mathcal{B}^1)$上的$n$个概率测度$\mu_j$也可以构造$(\mathcal{R}^n, \mathcal{B}^n)$上的独立随机变量：

10) 上面几个例子都是乘积空间上构造的，也可以在一个抽象的概率空间$(\mathcal{U}, \mathcal{B}, m)$构造，方法是嵌入一个乘积结构。考虑区间$(0,1]$里的数的二进制表达$x=.\epsilon_1\epsilon_2\cdots\epsilon_n\cdots$。那么$\epsilon_j(x)=\epsilon_j$可以看成一个r.v.，取值为0或者1，而且$P(\epsilon_1=0)=P(\epsilon_1=1)=P(\epsilon_2=1)=P(\epsilon_2=1)=1/2$，而且 $$P(\epsilon_1=1\cap\epsilon_2=0)=1/2^2=P(\epsilon_1=1)P(\epsilon_2=0)$$ $\epsilon_1=1\cap\epsilon_2=0$是长度为$1/4$的区间，所以这两个r.v.独立。

11) $\mathcal{B}^2$中不能直接表达为$\mathcal{B}^1$乘积的元素：

$A\cup B$可以表达成乘积的和，$C$需要无穷多个乘积的和表达。

期望

0) 求计数问题的期望的时候(比如求n次试验里出现的某种结果个数的期望)，如果可以把问题转化成r.v.的和$\sum_i X_i$，那么结果等于是所求的期望是单个$X_i$的期望的和。

1) 期望是概率空间上对概率测度的积分

2) 对离散的r.v.，设对应的weighted partition是$\{\Lambda_j; b_j\}$，那么期望可以写成 $$E(X)=\sum_j b_j P(\Lambda_j)$$ 3) 对连续的正的r.v.，先定义一个weighted partition和一个离散的r.v.，对$m, n \geq 0$，定义集合 $$\Lambda_{mn}=\left\{ \omega | \frac{n}{2^m} \leq X(\omega) < \frac{n+1}{2^m} \right\}$$ 这是partition，weight定义为$n/2^m$也就是$\Lambda_{mn}$上$X$取的最小值，得到weighted partition $\{\Lambda_{mn}; n/2^m\}$。
这个weighted partition对应的离散r.v.为$X_m(\omega)=\frac{n}{2^m},\ \omega\in \Lambda_{mn}$。它的期望为 $$E(X_m)=\sum_{n=0}^{\infty}\frac{n}{2^m}P(\Lambda_{mn})$$ 定义$X$的期望为 $$E(X)=\lim_{m\rightarrow \infty}E(X_m)$$ 4)概率空间上的抽象积分和$(\mathcal{R}^1, \mathcal{B}^1)$上的Lebesgue–Stieltjes积分： $$\int_\Omega f(X(\omega))P(d\omega)=\int_{\mathcal{R}^1}f(x)\mu(dx)$$ 其中$\mu$是$X$在$(\mathcal{R}^1, \mathcal{B}^1)$诱导的概率测度，$f$是$(\mathcal{R}^1, \mathcal{B}^1)$上的可测函数， 如果取$f=1_{B\in \mathcal{B}^1}$，那么$\int_\Omega f(X(\omega))P(d\omega)=\int_\Omega 1_{B}(X(\omega))P(d\omega)$，可以看 $$1_{B}(X(\omega))=\left\{ \begin{array}{l l} 1 & \quad \text{if $\omega \in X^{-1}(B)$}\\ 0 & \quad \text{if $\omega \notin X^{-1}(B)$}\\ \end{array} \right.$$ 所以$\int_\Omega 1_{B}(X(\omega))P(d\omega)=\int_{X^{-1}(B)}P(d\omega)=P(X^{-1}(B))=P(X\in B)$。
另一边，$\int_{\mathcal{R}^1}f(x)\mu(dx)=\int_{\mathcal{R}^1}1_{B}(x)\mu(dx)=\int_{B}\mu(dx)=\mu(B)$。也就是 $$P(X\in B)=\mu(B)$$ 这就是$\mu$的定义，所以等式成立。$f$可以看成$(\mathcal{R}^1, \mathcal{B}^1)$上的r.v.，再根据积分的线性和单调收敛可以证明等式对离散和连续的$f$都成立。

二维的情况 $$\int_{\Omega}f(X(\omega), Y(\omega))P(d\omega)=\iint_{\mathcal{R}^2} f(x, y)\mu^2(dx, dy)$$

5)期望表达为在概率空间上的抽象积分形式： $$E(X)=\int_{\Omega}X(\omega)P(d\omega)$$ 根据4)，这时候$f(x)=x$，积分表达为$(\mathcal{R}^1, \mathcal{B}^1)$上的Lebesgue–Stieltjes积分： $$E(X)=\int_{\Omega}X(\omega)P(d\omega)=\int_{\mathcal{R}^1}x\mu(dx)$$

6)对moment来说$f=(x-a)^r$ $$\int_{\mathcal{R}^1}(x-a)^r\mu(dx)$$

随机变量

1) 逆映射保持补，交，并运算。特别的交集为空的两个集合的逆像交集也是空。

2) 验证一个由概率空间$(\Omega, \mathcal{F}, P)$到$(\mathcal{R}^1, \mathcal{B}^1)$的映射是r.v.只需要验证$X^{-1}(\ (-\infty, x]\ )\in \mathcal{F}$。

3) 所以对任何一个r.v.概率$P( \{X \in B\} )$有定义，其中$B\in \mathcal{B}^1$。

4) r.v.在$(\mathcal{R}^1, \mathcal{B}^1)$上诱导了一个概率测度$\mu=P\circ X^{-1}$称为$X$的"probability distribution measure"或者p.m.。$(\mathcal{R}^1, \mathcal{B}^1)$上的概率测度$\mu$诱导的D.F.称为$X$的D.F.。

5) 不同的r.v.可能诱导同样的$(\mathcal{R}^1, \mathcal{B}^1)$上的测度，比如取概率空间为$(\mathcal{U}, \mathcal{B}, m)$，那么$X(\omega)=\omega$和$Y(\omega)=1-\omega$诱导的测度是一样的。

6) 设$f: (\mathcal{R}^1, \mathcal{B}^1) \rightarrow (\mathcal{R}^1, \mathcal{B}^1)$是一个可测函数，那么$f\circ X$是一个r.v.。
证明：注意到$f$可测也就是$f^{-1}(\mathcal{B}^1) \subset \mathcal{B}^1$，所以 $$(f\circ X)^{-1}(\mathcal{B}^1)=X^{-1}\circ f^{-1}(\mathcal{B}^1) \subset X^{-1}(\mathcal{B}^1) \subset \mathcal{F}$$

7) 二维测度空间$(\mathcal{R}^2, \mathcal{B}^2)$，其中$\mathcal{B}^2$是由下面的集合生成 $$B_1 \times B_2 = \{ (x, y) | x\in B_1, y\in B_2,\ \ B_1, B_2 \in \mathcal{B}\}$$

8) 设$X, Y$是r.v.，随机向量$(X, Y): (\Omega, \mathcal{F}, P) \rightarrow (\mathcal{R}^2, \mathcal{B}^2)$诱导了$(\mathcal{R}^2, \mathcal{B}^2)$上的概率测度$\nu=P\circ (X, Y)^{-1}$，注意求概率的时候是并且的关系，也就是任取$A = B_1\times B_2$($\mathcal{B}^2$由这种形式的集合生成)那么： $$(X, Y)^{-1}(A)=X^{-1}(B_1)\cap Y^{-1}(B_2) \in \mathcal{F}$$

---

9) 离散随机变量：存在可数集$B\subset \mathcal{R}$满足$P(X\in B)=1$。

10) 集合的indicator：比如$\Delta$的indicator定义为 $$1_{\Delta}(\omega)=\left\{ \begin{array}{l l} 1 & \quad \text{if $\omega \in \Delta$}\\ 0 & \quad \text{if $\omega \notin \Delta$}\\ \end{array} \right.$$ 当$\Delta \in \mathcal{B}$的时候$1_{\Delta}$是一个r.v.。

11) 概率空间$\Omega$的可数划分(countable partition)：划分是可数个$\Omega$的子集的集合$\{\Lambda_j\}$，满足$\Lambda_j\in \mathcal{F}$和$\cup_j\Lambda_j=\Omega$。
每个$\Lambda_j$选取一个实数$b_j$，下面的函数是一个离散r.v. $$\phi(\omega)=\sum_j b_j1_{\Lambda_j}(\omega)$$ $\phi$被称为r.v. belonging to the weighted partition $\{\Lambda_j; b_j\}$。 反过来，根据离散r.v.的定义，每个离散r.v.对应一个weighted partition。

---

例子

比如掷骰子, probability space是{1点, 2点, ..., 6点}, $X$是把(1点)映射到数值1, (2点)映射到数值2。$X$也可以看成把(掷色子)这个实验映射到实数的映射，而probability space{1点, 2点, ..., 6点}是刻画所有样本的工具。这里$X$在probability space上诱导的测度正好和它本身的测度重合，如果$Y$这个随机变量把偶数点数映到1，奇数点数映射到2，那$Y$诱导的测度就要粗的多。但有时$Y$可能是唯一能观察到的量。比如下面的例子。

很好的例子: $A$和$B$点有$n$个通信通道连接，每个信道的传输率都是$\rho$，显然有$k$条信道同时通信的时候总传输率是$k\rho$，每个信道失效的概率是$p$。样本空间是所有可能的组合，现在考察measure，假设你只能观察到总传输率，你measure一次只能得到值$k\rho$，从而知道有几个信道work，具体哪几个不知道。如果全部信息都知道的话，可能的情况应该有$2^n$种可能，但是我们测一次只知道这个样本落在集合
$$A_k=\{\omega=(\epsilon_1, \epsilon_2, \cdots, \epsilon_n) \in \Omega: \sum_n \epsilon_i=k\}$$
里，这样得到$n$个集合$\{A_i\}$。
如果一个人不知道具体的实验设置，他只能统计$k\rho$，这就是他能得到背后的probability space的测度。

概率测度和D.F.的关系

1) $\mathcal{B}^1$上的$p.m. \mu$决定一个D.F. $$F(x) = \mu(\ (-\infty, x]\ )$$ 2) D.F.到p.m.要用到测度的存在性，以及某种意义上的唯一性，还有测度的扩张。

一些概率空间的定义

1) $(\mathcal{U}, \mathcal{B}=\sigma(\mathcal{L}), m)$
区间$\mathcal{U}=(0, 1]$，其中$\mathcal{L} = \{(a, b]\ |\ 0 < a < b \leq 1\}$，$m$是lebesgue测度。

可数可加<=>有限可加+连续性

1) 如果$E_n \downarrow$，则 $$E_n=\cup_{k=n}^\infty (E_k\setminus E_{k+1})\cup \cap_{k=1}^\infty E_k$$ 设$x\in E_n$并且$x\notin \cup_{k=n}^\infty (E_k\setminus E_{k+1})$
$x\in E_n, x\notin E_n\setminus E_{n+1} \Rightarrow x\in E_{n+1}$由归纳法知$x\in E_i, i > n+1 \Rightarrow x \in \cap_{k=1}^\infty E_k$

2) 如果$E_n \downarrow \Phi$，则$\cap_{k=1}^\infty E_k = \Phi$ $$E_n=\cup_{k=n}^\infty (E_k\setminus E_{k+1})$$
3)如果可数可加成立 $$P(E_n) = P( \cup_{k=n}^\infty (E_k\setminus E_{k+1}) )=\sum_{k=n}^\infty P((E_k\setminus E_{k+1}))$$
取$n=1$ $$P(E_1) = P(E_1\setminus E_2) + P(E_2 \setminus E_3) + \cdots + P(E_{n-1} \setminus E_n) + \sum_{k=n}^\infty P((E_k\setminus E_{k+1}))$$ 上面的无穷级数收敛的事实说明，$\lim_{n\rightarrow \infty}P(E_n) = 0$

4)反过来，如果连续性和有限可加成立，设$B_k$两两不相交那么 $$\cup_{k=n+1}^\infty B_k \downarrow \Phi$$ 因为如果上面的极限不是$\Phi$那么必存在元素在无穷多个$B_k$中，这个两两不相交矛盾。由连续性 $$\lim_{n\rightarrow \infty}P(\cup_{k=n+1}^\infty B_k) = 0$$ 由有限可加性 $$ \begin{align} P(\cup_{k=1}^\infty B_k) &=& P(\cup_{k=1}^{n} B_k) + P(\cup_{k=n+1}^{\infty} B_k) \\ &=& \sum_{k=1}^n P(B_k) + P(\cup_{k=n+1}^{\infty} B_k) \end{align} $$ 上面的式子说明和式$\sum_{k=1}^n P(B_k)$有界，它又是递增的，所以这个和式的极限存在。让$n$趋于无穷，可得可数可加的等式。

一些扩展

5) 4的证明里，在一个field上也可以证明，只要$\cup_{k=1}^\infty B_k$在field里，并且连续性满足。

A Course in Probability Theory - chap 2

2.1

1)
$(\cup_j A_j)\setminus(\cup_j B_j)=(\cup_j A_j)\setminus(\cup_i B_i)=(\cup_j A_j)\cap(\cup_i B_i)^c=(\cup_j A_j)\cap(\cap_i B_i^c)\\ =\cup_j [A_j \cap (\cap_i B_i^c) ]=\cup_j [ \cap_i(A_j\cap B_i^c) ]=\cup_j [ \cap_i(A_j\setminus B_i) ]$
对固定的$j$有$\cap_i(A_j\setminus B_i) \subset A_j\setminus B_j$，所以$\cup_j [ \cap_i(A_j\setminus B_i) ] \subset \cup_j (A_j\setminus B_j)$，相等的条件是$\cap_i(A_j\setminus B_i) = A_j\setminus B_j$也就是$i\neq j$的时候$A_j\setminus B_i = A_j$即$A_j\cap B_i = \Phi$
2)
对称差的计算方法$1_{A\Delta B} = 1_A + 1_B \mod 2$，例如$1_{(A\Delta B)\Delta (B \Delta C)} \mod 2 =\\ 1_{A\Delta B} + 1_{B \Delta C} \mod 2=\\ 1_A + 1_B + 1_B + 1_C \mod 2 = 1_A + 2_B + 1_C \mod 2 = 1_A+1_C=1_{A\Delta B}$
3)
原始集合加上他们的补集一共是$2n$个，这些集合的可数并有$2^{2n}$个。
4)
6)
到3为止的正整数构成的B.F.：$\mathcal{F}_3=\left\{ \Phi, N, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2 ,3\} \right\} \\ \cup \left\{ \{1\}^c, \{2\}^c, \{3\}^c, \{1, 2\}^c, \{1, 3\}^c, \{2, 3\}^c, \{1, 2 ,3\}^c \right\}$
考虑所有奇数构成的集合，这个集合是单点集合可数并，但是不属于任何$\mathcal{F}_n$，所以不在B.F.的可数并里。

2.2

1) 可数个单点集并起来的一个无限的。
2)当n取不同的值趋向于极限的时候,$E\cap F$取不同的极限.
3)
4) $P(\Omega)=\infty$
5) 记所有形式$F\cap \Delta$的集合构成的集合为$\mathcal{F}_{\Delta}$, 其中最大的是$\Omega \cap \Delta$.
6) $\forall F\in \mathcal{F}, P(F\setminus \Delta) = 0$, 也就是$E=F\cap \Delta$是$F$去掉一个0测集.
7) 闭区间的可数并可得开区间; 单点集或者有限集的可数并得不到区间.

A Course in Probability Theory - chap 1

1.1

1)
当$x=-\infty$的时候对任意的$i$有$x < i$，所以$\delta_i(x)=0$，所以和式为0。
当$x=+\infty$的时候对任意的$i$有$x > i$，所以$\delta_i(x)=1$，所以和式为$\sum_n b_n$。
2) $$f=\sum_{n=1}^\infty [\delta_n(x)-\delta_n(-x)] -\frac{1}{2}\delta_0(x) + \frac{1}{2}\delta_0(-x)$$ 设$x > 0, m=[x]$，那么
当$-x < 0 < n$：$\delta_n(-x) = 0, n=1,2,...$
当$n > m$：$\delta_n(x) = 0$ 所以$\sum_{n=1}^\infty \delta_n(x)=\sum_{n=1}^m \delta_n(x)=\sum_{n=1}^m 1=m$
$f(x)=m-\frac{1}{2}\delta_0(x) + \frac{1}{2}\delta_0(-x)=m-\frac{1}{2}$
3)
任给$\epsilon$，大于$\epsilon$的jump的数量小于$(B-A)/\epsilon$，否则因为函数是增函数，这些jump是不相交的区间，函数的取值范围大于$[A, B]$。
现在取$\epsilon = \frac{1}{n}$，用$J_n$记大于$\epsilon$的jump的数量，是个有限的整数，函数总的jump的数量小于$\sum_{n=1}^\infty J_n$，所以是可数个。
Froda's theorem
第一类型的不连续包括removable discontinuity，a jump discontinuity。removable discontinuity是左右极限相等，但是函数的取值不是这个极限。
Let f be a monotone function defined on an interval I. Then the set of discontinuities of the first kind is at most countable.
4)
5)
例如$f=\frac{1}{\pi - x}$在有理数集上是连续的，但诱导的$\tilde{f}$不连续。如果$f$一致连续，$\tilde{f}$在$x_0$点不连续，左右极限不相同，找$D$中的两个序列，分别从两端趋向于$x_0$，根据一致连续性$f(b_n)-f(a_n)\rightarrow 0$，这和$\tilde{f}$在$x_0$不连续矛盾。
一致连续的反面是：存在$C$，使得不论$\delta$多小，并不是所有满足$|x_1-x_2| < \delta$的两点都满足$|\tilde{f}(x_1)-\tilde{f}(x_2)| < C$。
$C$有时候可以任意的大，比如$f(x)=\frac{1}{x}$，有时候$C$不能任意大，比如$f(x)=sin(\frac{1}{x})$，只要存在就好，只要不是无穷小的量就好。
现在假设$\tilde{f}$不一致连续，那么它满足上面的性质，考虑$(x_1 + 1/n, x_2 - 1/n)$，根据$\tilde{f}$的连续性，总可以使$|\tilde{f}(x_1) - \tilde{f}(x_1 + 1/n)| < C/3$，根据$D$的稠密性，总可以找到$a_1 \in D$并且$a_1\in [x_1, x_1 + 1/n]$，另一边找到$a_2$，根据单调性有$|f(a_1) - f(a_2)| > C/3 $，也就是$f$不一致连续。

1.2

1)
$=F(x+)-F(x-)$
2)
考虑以$x$为右端点的开区间，当区间长度趋于0的时候，因为d.f.是右连续，区间里不会包含任何jump，而区间$(x-\epsilon, x]$，当$x$是jump的时候收敛到jump。
证明Theorem 1.2.1
$[F_d(x)-F_d(x-)]=\lim_{\epsilon\rightarrow 0}[F_d(x)-F_d(x-\epsilon)]=\lim_{\epsilon\rightarrow 0}[\sum_jb_j\delta_{a_j}(x)-\sum_jb_j\delta_{a_j}(x-\epsilon)]$
上面最后一个式子的意思是$(x-\epsilon, x]$之间的jump的和，或者写成$\sum_{x-\epsilon < a_j \leq x}[F(a_j)-F(a_j-)]$。
$F_c(x)-F_c(x-)=F(x)-F(x-)-[F_d(x)-F_d(x-)]$
$=F(x)-F(x-)-\lim \sum_{x-\epsilon < a_j \leq x}[F(a_j)-F(a_j-)]$
分别考虑$x$是jump和不是jump的情况，可以证明定理。
3)
如果jump的点是稠密的，那么"jump之间"就没有定义，如果在欧氏距离下离散，就排除了稠密的情况。
4)
d.f.的$F_d$的定义有意义的原因是和式是有限的，因为d.f.有界而且是增函数，jump只有可数个。
$$\begin{align} &F_d(a) & = & F(a)\\ &F_d(a-x) & = & F(a) - \sum_{jump \in (a-x, a)} b_i \end{align}$$ 注意到不同的$a$会定义不同的$F_d$，对于d.f.选的是$a=-\infty$。
5)
6)
根据jump的定义，因为是下确界和上确界的差，总能找到$F(x+\delta) - F(x-\delta) \geq b_i$，所以如果存在$\epsilon$使得$F(x+\epsilon) - F(x-\epsilon)=0$(小于0是不可能的，因为$F$是增函数)，令$\delta < \epsilon$，两式相减 $$F(x+\delta) - F(x+\epsilon) + ( F(x-\epsilon) - F(x-\delta) ) \geq b_i > 0$$ 这和$F$是增函数矛盾。
如果$y$不是support里的点，那么可以找到$y$的一开区间，d.f.在区间的两端取的值相等，再根据d.f.是单调函数，知道d.f.在这个区间上取常数值。如果$x$是support的孤立点，并且$x$不是jump，因为是孤立点，可以知道d.f.在两个区间$(x-\delta, x)$和$(x, x+\delta)$分别取常数值，在根据jump的定义知道df在第一个区间的取值的上确界，等于在第二个区间取值的下确界，所以两个常数相等，这和$x$属于support矛盾。
如果一个d.f.在一个稠密可数集合上都是非零jump，其他时候取常数，其support是整个line，因为任何开区间都包含jump，取常数值的开区间是不存在的，而非support点要求有个包含它的取常值的开区间。
7)
由上面知道任何非support点都有一个包含它的d.f.取常值的开区间，这个开区间里的点显然都不是support里的点，所以support的补集是开集，support是闭集。

跨语言的变量共享

在build系统或者大量使用不同脚本的任何系统里，不同脚本直接的变量传递以及集中管理常量是很头疼的一件事件，考虑了一下解决的方法。Template based code generation好像可以解决这种问题

1. 常量
用一种meta格式描述常量，或者就选一种语言，IDL什么的，用code generation生成各种赋值脚本(ant, perl, python, sh, java, c++)，然后被其他脚本包含。

常量的来源有时候是环境变量，所以template system初始化的时候先初始化自己的环境变量，然后通过环境变量生成IDL，和静态的IDL放一起。接着在进行IDL到各语言的转换，这样的好处是容易调试和记录。运行过后环境变量会消失，但生成的IDL还在。

2. 如果是中间生成的变量，但是需要传递怎么办？
要集中管理，template system提供API，可在run time被调用，所有的变量传递必须经过，如果需要可以定向，比如perl到ant，都当参数传给template system。一样先生成IDL，最好IDL里有些tag来记录调用者和时间。

3. 静态的文件里需要动态的内容，比如一些配置xml必须运行时改变，所以template system要提供文件里变量的替换功能的API，这时候可能不需要再用IDL中转，但是最好有log。

4. 如果有一群类似的文件，要用模板，但是模板会造成code下载下来不能直接用ide编译，这是个问题，也许可以用缺省的文件代替，真正build的时候把缺省文件用通过模板生成的文件代替。
模板里的数据可以和一个hash对应，可以用命名空间隔开名字相同位置不同的文件，比如feature.xml。


会有什么问题？要求使用者遵循什么规则？如何测试？如何维护？维护者遵循什么规则？

Dynkin定理证明($\pi-\lambda$ Theorem)

$\pi$-system是对有限交封闭；$\lambda$-system是对补和不交并封闭，并且包含全空间$\Omega$。如果一个system既是$\lambda$又是$\pi$，那么它是个$\sigma$-field(包含空集，对补集和可数并封闭)。

定理：设$\mathcal{L}$是一个$\lambda$-system，$\mathcal{C}$是一个$\pi$-system，且$\mathcal{C}\subseteq \mathcal{L}$，那么$\sigma(\mathcal{C}) \subseteq \mathcal{L}$。（也就是$\pi$-system生成的$\sigma$-field比包含它的任何一个$\lambda$-system小）。

路线：构造一个新的$\lambda$-system，证明它是$\pi$-system，并且这个system包含$\sigma(\mathcal{C})$且被$\mathcal{L}$包含。

新的$\lambda$-system定义为所有包含$\mathcal{C}$的$\lambda$-system的交集，记为$\mathcal{L}(\mathcal{C})$。

根据$\mathcal{L}(\mathcal{C})$的定义两个显然的包含关系
-- $\mathcal{L}(\mathcal{C})$必然被$\mathcal{L}$包含，因为$\mathcal{L}$是其中一个$\lambda$-system。
-- $\mathcal{L}(\mathcal{C})$包含$\mathcal{C}$，因为$\mathcal{L}(\mathcal{C})$是包含$\mathcal{C}$的system的交集。

---

1) $\mathcal{L}(\mathcal{C})$是$\lambda$-system。

$\mathcal{L}(\mathcal{C})$是$\lambda$-system的交集，而每个$\lambda$-system都包含全空间$\Omega$，所以$\mathcal{L}(\mathcal{C})$也包含$\Omega$。同样的道理任何一个$\mathcal{L}(\mathcal{C})$中的元素$A$必包含在所有的$\lambda$-system中，所以补集$A^c$也包含在所有的$\lambda$-system中。

不交并的运算同样发生在所有的$\lambda$-system中，所以也包含在$\mathcal{L}(\mathcal{C})$。

---

2) $\mathcal{L}(\mathcal{C})$是$\pi$-system。证明复杂一点。

对$\mathcal{L}(\mathcal{C})$中的一个元素$X$定义一个system $\mathcal{L}_X=\{Y|X\cap Y \in \mathcal{L}(\mathcal{C})\}$。$\mathcal{L}_X$是一个$\lambda$-system，证明见最后。

$\mathcal{L}_X$的含义是所有和$X$相交在$\mathcal{L}(\mathcal{C})$中的元素，当$X$变化的时候它有这样的性质：

• $X\in \mathcal{C}$，那么$\mathcal{L}_X$包含$\mathcal{C}$，因为任取$A\in \mathcal{C}$，根据目前的条件$A, X$都在$\mathcal{C}$里，而$\mathcal{C}$是$\pi$-system，对有限交封闭，因此$A\cap X\in\mathcal{C} \subseteq\mathcal{L}(\mathcal{C})$，所以$A$满足$\mathcal{L}_X$的条件。
  
  $\mathcal{L}_X$包含$\mathcal{C}$的$\lambda$-system，所以是其中一个$\lambda$-system，所以$\mathcal{L}(\mathcal{C})\subseteq\mathcal{L}_X$，或者写成$\mathcal{L}(\mathcal{C})|_{\cap X\in\mathcal{C}} \subseteq \mathcal{L}(\mathcal{C})$。
  
  也就是说，如果把和$\mathcal{C}$里面的元素相交看成一种运算的话，$\mathcal{L}(\mathcal{C})$对这个运算封闭。(这里很有意思，本来$\lambda$-sysem的定义是补和并的运算封闭，这里得到了一种交集运算封闭)。
  
  
• $X\in\mathcal{L}(\mathcal{C})$，根据上面的结论，这时候$X$和$\mathcal{C}$的元素相交还在$\mathcal{L}(\mathcal{C})$中，所以$\mathcal{C}\subseteq \mathcal{L}_X$
  
  也可以得出$\mathcal{L}(\mathcal{C})\subseteq\mathcal{L}_X$，或者写成$\mathcal{L}(\mathcal{C})|_{\cap X\in\mathcal{L}(\mathcal{C})} \subseteq \mathcal{L}(\mathcal{C})$
  
  

最后那个式子就是对有限交封闭，虽然不太正规。 由以上，$\mathcal{L}(\mathcal{C})$是$\sigma$-field，而且包含$\mathcal{C}$，而$\sigma(\mathcal{C})$的定义为包含$\mathcal{C}$的最小的$\sigma$-field，所以$\mathcal{L}(\mathcal{C})$包含$\sigma(\mathcal{C})$。

大小关系

$\pi$-system $\mathcal{C}$ --> $\sigma$-field $\sigma(\mathcal{C})$ --> $\sigma$-field $\mathcal{L}(\mathcal{C})$ --> $\lambda$-system $\mathcal{L}$

---

证明$\mathcal{L}_X$是一个$\lambda$-system。

---

在概率里的应用
推论：如果两个概率测度在一个$\pi$-system $\mathcal{C}$上相等，那么他们在$\sigma(\mathcal{C})$上相等。

证明：注意到根据概率测度的性质，满足概率测度相等的所有集合（包含$\mathcal{C}$）是一个$\lambda$-system。

可测函数

---

要求$f$值域里的区间的逆像可测，实际上是对连续函数要求的一种放松，连续函数要求开集的逆像还是开集。

单调函数都是可测的，区间的逆像还是区间。

注意求区间的逆像其实就是解不等式。

可测函数对加法$f+g$和乘法$fg$封闭，如果$f=c$是常函数，显然可以推出对数量乘积封闭。

---

Lebesgue integral：假设函数$f$值域里的区间$J_n$的逆像是可测集，和式
$$\sum_{n=1}^N c_n m(f^{-1}(j_n))$$
有定义，其中$c_n \in J_n, m(\cdot)$是测度，和式的极限是Lebesgue integral。

Lemma：如果$F:R\times R \rightarrow R$是连续函数，$f, g$是可测函数，那么$h(x)=F(f(x), g(x))$可测。

wiki:The (pointwise) supremum, infimum, limit superior, and limit inferior of a sequence (viz., countably many) of real-valued measurable functions are all measurable as well.

limit superior $\lim\sup_{n\rightarrow \infty}f_n$可以这样看，对定义域的每一点$x_0, \{f_n(x_0)\}$是一个实数序列，limit superior在这点的取值是这个实数序列的limsup。对实数序列，limsup用语言描述是$n$后面的无穷多个元素的上界$p_n$，当$n$趋于无穷的时候得到的$p_n$的极限。

$p_n \geq p_{n+1}$，因为$p_{n} = max\{a_n, p_{n+1}\}$，所以$p_n=\sup_{m\geq n} a_m$是个递减的序列。递减序列如果有极限的话，极限也是下确界，所以limit superior也可以写成$n$个上界的下界。
$$\limsup_{n\rightarrow \infty}f_n=\inf_{n\geq 1}\{p_n=\sup_{m\geq n}f_m\}$$

---

对随机变量来说，一般他们的取值都是很好的集合，如果假设都是Borel sets。所以定义
$$X^{-1}(\mathcal{B})=\{S \subset \mathcal{F}: S=X^{-1}(B)\text{ for some }B\in \mathcal{B} \}$$
是一个$\sigma$-field，称为$X$生成的$\sigma$-field，记为$\mathcal{F}_X$，注意$X$的逆像是可以是空，而且不同集合的逆像可能是相同的，逆像不同个数可能很有限，所以如果$X$的取值是实数，我们可以检查实轴上的Borel set在$X$的逆像。

如果$X$只取值$a$，那么$\mathcal{F}_X=\{\Phi, \Omega\}$。
如果$X$只取两个值$a, b$，那么$\mathcal{F}_X=\{\Phi, \Omega, X^{-1}(a), X^{-1}(b) \}$。
如果$X$只取有限个值，那么$\mathcal{F}_X$有限。
如果$X$只取有可数个值，那么$\mathcal{F}_X$不可数，因为可数集合的全部子集的个数是不可数的，这些子集都可以得逆像。

注：Borel sets：the smallest $\sigma$-field containing all open sets (in $R^1$ or $R^n$).

---

通过$P_X(B)=P(X^{-1}(B)), B\in \mathcal{B}$可以在$X$的值域$(R, \mathcal{B})$的空间里定义了一个测度，称为$X$的分布。也就是说$(R, \mathcal{B}, P_X)$是一个概率空间。

例子：
1. Dirac measure, $X\equiv a$，诱导的$(R, \mathcal{B})$测度为
$$\delta_a(B)=\left\{
\begin{array}{l l}
1 & \quad \text{if $a \in B$}\\
0 & \quad \text{if $a \notin B$}\\
\end{array} \right.$$
也就是如果集合包含$a$那么测度为1，否则为0。

2. 如果$X$是离散随机变量，且$P(a_i)=p_i$，那么诱导的测度为
$$P_X(B)=\sum_{i=1}^\infty p_i\delta_{a_i}(B)$$

3. 如果底空间$\Omega$是离散的，那么其上的所有实值函数都是可测的，都是随机变量。

4. 不同函数值的函数逆像必然不相交，更进一步，不相交的集合的逆像是不相交的。

5. 从分布$F$构造随机变量的办法，假设$F$满足分布函数的性质。
--首先注意到$0 \leq F \leq 1$，取$\Omega = (0, 1)$为构造的随机变量的概率空间，对任何$\omega \in \Omega$，定义$X(\omega)=\sup\{y|F(y)<\omega\}$

---

随机变量$X, Y$独立的意思是$\mathcal{F}_X, \mathcal{F}_Y$独立，也就是对任意Borel集合$B, C\subset R$有：
$$P(X^{-1}(B)\cap Y^{-1}(C))=P(X^{-1}(B))P(Y^{-1}(C))$$

概率：测度

集合

定义：

• Field：对补和并封闭。
• Monotone Class(M.C.)：对可数单调上升集合序列的并封闭，对单调下降集合序列的交封闭。注意M.C.不要求是Field。
• Borel Field(B.F.)：对补集和可数并封闭。

定理：对有限并封闭+可数个上升集合序列的并封闭$\Rightarrow$对可数并封闭，因为，根据集合的运算规则： $$\cup_{i=1}^\infty E_n = \cup_{n=1}^\infty ( \cup_{i=1}^n E_i )$$ 而$(\cup_{i=1}^n E_i),\ \ n = 1, 2, 3, \cdots$是上升的集合序列。
关系：

• B.F.要求最严，显然B.F.是M.C.。
• 已知是Field，那么“是B.F.”和“是M.C.”等价(根据上面的定理)。
• 包含一个Field的M.C.也是Field。
• 包含一个Field的最小M.C.和最小B.F.是一致的。

单调上升下降集合的序列的好处是性质好，容易使用，然后利用上面的关系，可得更大范围的运算的性质。

---

1) Null set：$A \subseteq R$，任给一个正数$\epsilon$，存在一个区间的序列$\{I_i\}$，$A$可以被这些区间覆盖，并且这些区间的长度的和小于$\epsilon$，$\sum_i l(I_i) < \epsilon$。 可数个null set，$\{A_i\}$的并还是null set。(对任意$\epsilon$，用几何级数$\epsilon/2^i$作为第$i$个null set的覆盖的长度上界，所有这些覆盖的并的长度小于$\epsilon$) 可数集合都是和数个单点集合的并，所以是null set。 2) Cantor set：递归定义$C_0=[0, 1], C_n=(C_{n-1}/3)\cup (2/3 + C_{n-1}/3))$

0到1之间的实数用3进制表达，如果其中不包含1，那么这个数在Cantor set里

先考虑第一分割，新产生的端点为$1/3=0.1, 2/3=0.12222...$，去掉的点都是第一个小数位是1的数。

Outer measure的定义是所有覆盖的长度的下确界，确界的意思是对任意的正数$\epsilon, m ^*(A)+\epsilon$不是下界，也就是可以找到一个覆盖其长度落在$(m ^*(A), m ^*(A)+\epsilon)$里。

区间的Outer measure等于自己的长度，也就是说区间长度是所有覆盖的长度的下确界。

$m^*(I)\leq l(I)$：区间是自己的覆盖，所以其长度大于所有覆盖的下确界。

下面只要证明$m^*(I) < l(I)$不成立就可以了，也就是对任意的正数$\epsilon $可以找到在$(m^* (I), m^* (I) + \epsilon)$的一个覆盖，而且这个覆盖的长度大于$l(I)$。覆盖很容易找，因为Outer measure是下确界，计算长度的时候要用Heine-Borel theorem，先把覆盖变成开覆盖，但是长度又变化很小，然后找出有限开覆盖，这个长度可以计算。

Outer measure is countably subadditive: 也就是并集的outer measure不大于各个集合的outer measure的和。任何单个集合的覆盖，并在一起可以得到并集的一个覆盖。

Outer measure并不是对所有的集合都有可数可加性，即可数个不想交的集合，并集的outer measure等于单个集合outer measure的和。

如果$E$可测，那么对任何集合$A$，有$m^*(A)=m^*(A\cap E) + m^*(A\cap E^c)$，（显然可测的定义对补集运算对称，可测集合的补集一定是可测的）

如果$E$是区间那么$E$可测：对任何的集合$A$，根据Outer measure的定义，要描述$m^*(A)$，需要找一个$A$的覆盖(覆盖的元素是区间)，而$E$和$E^c$也是区间，覆盖和区间的交集还是覆盖，研究这几个覆盖之间的关系可以证明。


$\sigma$-field的定义，以及其上测度的定义($\Omega$为底空间，Field里的元素是底空间子集)
Field $\mathcal{F}$的性质
1) 对补集运算封闭。
2) 对可数并运算封闭。
测度的性质
测度$\mu$定义为Field到正实数的映射，且要求其满足可数可加性。

满足上面公理的三元组记为$(\Omega, \mathcal{F}, \mu)$。

Outer measure约束在$R$上的可测集上满足上面的$\sigma$-field的定义，以及测度的定义，记为$(R, \mathcal{M}, m^*)$

outer measure的目的主要是为了辨别出可测的集合，构造$\sigma$-field，并在其上定义measure，进而得到measure space三元组。

由上面测度满足的公理可以推出，测度有性质
1)Monotonicity
2)Subadditivity
3)Continuity from below
4)Continuity from above
上面这些性质证明的方法是构造合适的不相交的集合，然后利用可数可加性。

具体的分布

二项分布

定义：已知一次实验中成功的先验概率是$p$，做$n$次独立的实验，成功次数是一个Random Variable，这个Random Variable的分布可以通过先验概率和排列组合的方法计算出来。

公式$B(n, p)$:
$$p(i)=P(X=i)={n \choose i}p^i(1-p)^{n-i},\ \ i=0, 1, 2, .... n$$
$E[X]=np, Var(X)=np(1-p)$

Poisson分布

Poisson分布是已知随机变量的期望，和密度函数$P(X=i)=f(i, E(X))$

二项分布和Poisson分布的关系：现在考虑如果$p$很小，也就是事件发生的可能性很小，那么如果实验次数$n$也很小的话，基本不用实验了，发生的可能性很小。但是如果$n$很大，可以认为无穷大，二项分布$n$趋于无穷的时候得到Poisson分布。

既然$n$很大可以认为是无穷大，是个常数的所以Poisson分布的参数里不含$n$，只有期望$\lambda\approx np$($n$很大$p$很小$np$在有意思的范围)。比如一页书里面出现的错字，可以认为每个字都有错的可能，但是概率很小，这样我们就可以用Poisson分布了。
$$p(i)=P\{X=i\}=e^{-\lambda}\frac{\lambda^i}{i!},\ \ i=0, 1, 2, .... \infty$$
$e$的极限形式:
$$e^\lambda=\lim_{n\mapsto \infty}(1+\frac{\lambda}{n})^n$$
计算的时候还会用到$e$的级数形式:
$$e^\lambda=\sum_{j=0}^{\infty} \frac{\lambda^j}{j!}$$
Poisson分布的约束还可以进一步放松, 下面的近似方法称为Poisson Paradigm: 假设有$n$个事件, $p_i$是第$i$个事件发生的概率, 都很小, 而且这些事件不独立的话相关度也要很弱, 那么这些事件发生的发生的次数近似的是一个期望为$\sum_{i=1}^n p_i$的Poisson分布.

---

$$ \begin{align} p(i) &={n \choose i}p^i(1-p)^{n-i}\\ &=\frac{n!}{(n-i)!i!}(\frac{\lambda}{n})^i(1-\frac{\lambda}{n})^{n-i}\\ &=\frac{\lambda^i}{i!}(1-\frac{\lambda}{n})^{n}\left[\frac{n!}{(n-i)!}(\frac{1}{n})^i(1-\frac{\lambda}{n})^{-i}\right]\\ &=\frac{\lambda^i}{i!}(1-\frac{\lambda}{n})^{n}\left[\frac{n(n-1)\cdots(n-i+1)}{n^i}(1-\frac{\lambda}{n})^{-i}\right]\\ &\rightarrow \frac{\lambda^i}{i!}e^{-\lambda} \end{align} $$

---

multinomial分布：实验$n$次，每次实验结果可能有$r$种，第$i$种出现的概率是$p_i$，一个configuration可以由$x_1, x_2, \cdots, x_r$每种结果出现的次数来描述。 $$P(x_1, x_2, \cdots, x_r)=\frac{n!}{\prod_{i=1}^rx_i!}\prod_{i=1}^rp_i^r$$ $k$种$n$个元素的排列。

二项分布：两种物品，n次试验，每次取一个物品。
几何分布：两种物品，k次试验，每次取一个物品，最后一次得想要的。
超几何分布：两种物品，每次试验取n个物品。

概率：概念

集合能看成事件的原因是，考虑这样一个实验，从底空间中任取一个点，这个点在集合$A$里可以看成事件。

独立

事件$A, B$独立的意思是：$P(A\cap B)=P(A)P(B)$。推广到可数个独立事件的集合的意思是：其中任意$k$个事件的交集的概率等于这个$k$个事件概率的乘积。特别要指出的是两两独立推不出集合独立。

例如四个不同的事件$E_i, i=1,2,3,4$发生的概率都是1/4，定义$A_1=E_1\cup E_2$，$A_2=E_1\cup E_3$， $A_3=E_1\cup E_4$，这三个事件两两独立，但是$P(A_1\cap A_2\cap A_3)=P(E_1)=1/4$。

随即变量$X, Y$独立的意思是：他们在取值空间上诱导的$\sigma$-field独立。

$n+m$个相同的实验，$X$为前$n$个中成功的个数，$Y$为后$m$中成功的个数，$X, Y$独立。

随机变量$Y$在概率空间里诱导了一个$\sigma$-field，假设$D$这个$\sigma$-field里的一个可测集，那么$X$把这个可测集$D$映到$X$的所有可以取的值。$X, Y$独立吗？

考虑两个概率空间$\Omega_1, \Omega_2$，其上各定义了一个随机变量$X_1, X_2$，两个概率空间的笛卡尔积$\Omega_1\times \Omega_2$作为一个概率空间，新的概率测度定义为两个空间事件概率的乘积，也就是如果$\omega_1 \in \Omega_1, \omega_2 \in \Omega_2$那么$P((\omega_1, \omega_2))=P(\omega_1)P(\omega_2)$, 这显然是一个概率测度, 再定义$\bar{X_1}((\omega_1, \omega_2))=X_1(\omega_1)$, $\bar{X_2}((\omega_1, \omega_2))=X_2(\omega_2)$,那么$\bar{X_1}, \bar{X_2}$是独立的。

观察上面的两新个随机变量的逆像，如果把$\Omega_1$看成横轴那么$\bar{X_1}$的逆像只是和横轴垂直的条形，在纵轴方向无限延伸，每个逆像都是这样的，给不出任何纵轴的测度信息。

$A\cap B$和$A^c\cap B$两个集合是不相交的，不会同时发生，而且他们的并是$B$，所以$P(B)=P[(A\cap B)\cup (A^c\cap B)]=P(A\cap B) +P(A^c\cap B)$，如果$A, B$独立，那么$P(A\cap B)=P(A)P(B)$，

代数 概念

Ker 和 Im
对任何$m\times n$矩阵$A$，$dim Im(A) + dim Ker(A) = n$。

---

Permutation matrix：$\pi$是$\{1, \cdots n\}$的一个Permutation，Permutation matrix是
$$P=[S_{\pi(1)}, \cdots, S_{\pi(n)}]$$
其中$S_i$是单位矩阵的第$i$行。$P$有性质$P^{-1}=P^{T}$。

---

Fact：$Ax$是$A$列向量的线性组合，也就是$Im(A)$就是$A$的列向量张成的子空间。
Fact：如果$y \in ker(A)\text{ i.e. }Ay=0$，那么$y$和$A$的每个行向量都垂直。

上面两个Fact很直观，也很有用，可以用来证明行rank和列rank相等，设行rank为$k$，$R_1^T, \cdots, R_k^T$为线性无关的行，考虑$A(R_1) \cdots, A(R_k)$，如果它们线性相关，那么$\sum \lambda_i A(R_i)= A(\sum\lambda_iR_i)=0$，这说明$\sum\lambda_iR_i \in ker(A)$，而$ker(A)$里的向量和$A$的每个行向量都垂直，矛盾。$k$个向量$A(R_1) \cdots, A(R_k)$显然都在$Im(A)$中，线性无关说明，$Im(A)$就是$A$的列向量张成的子空间的rank至少是$k$。对$A^T$重复上面的过程，可知两个rank相等。

---

行列式的几何意义是$n$个行（列）向量构成的$n$维平行多面体的$n$维定向体积，显然如果这些向量线性相关，多面体的维度就会小于$n$，$n$维体积就是0。因为某个向量本该戳出去张成多一维的体积，但是它没有，缩到了其他向量张成的子空间里了。

行列式可以看成是行向量的$n$元线性函数，一个行向量被加上另一个行向量的倍数不改变行列式，因为$f(C_1+kC_2,C_2)=f(C_1, C_2) + kf(C_2, C_2)$，根据行列式的体积解读，后面那项为0。几何上看$C_1+kC_2$移动的方向和$C_2$的方向平行，象沿着和底边平行的方向移动三角形的对面的顶点，三角形的面积不变（当然行列式是平行四边形的面积，三角形的二倍就是这个平行四边形）。

Optimal Control：无限维

一阶必要条件，对所有的admissible perturbations $\eta$如果
$$\delta J|_{y^{ *}}(\eta)=0$$

因为变分和极值的定义都取决于摸，上面的条件对所有的摸成立。

习题：functional $J(y)=\int_0^1\phi(y(x))dx$，求一阶变分。
$$\delta J(y)|_\eta=\lim_{\alpha\rightarrow 0}\frac{\int_0^1\phi(y+\alpha\eta)dx-\int_0^1\phi(y)dx}{\alpha}$$
$$=\lim_{\alpha\rightarrow 0}\frac{\int_0^1\phi(y+\alpha\eta)-\phi(y)dx}{\alpha}$$
上下乘以$\eta$:
$$=\lim_{\alpha\rightarrow 0}\int_0^1\frac{(\phi(y+\alpha\eta)-\phi(y))\eta}{\alpha\eta}dx=\int_0^1\phi'(y)\eta dx$$

Fr echet derivative：
$$J(y+\eta) = J(y)+\delta J|_y(\eta) + o(\left\|\eta\right\|)$$
这个derivative是更强的一种变分可微要求，因为perturbations $\eta$可以更任意的趋向0.

微分的含义

一阶可微的定义其实就是对一点存在一个线性函数或泛函(和被微分的对象一样)，这个函数或者泛函可以用于逼近原函数。二阶微分就是存在一个二次型。只是逼近这一点附近的情况，线性函数或泛函输入是自变量的变化，输出是线性变化，这个线性变化加上这点的函数值，得到的和逼近实际的函数值：$f(x_0+h)=f(x_0)+L_{x_0}(h)$，函数的时候
$$L_{x_0}(h)=\nabla f(x_0)\cdot h=(\nabla f(x_0)\cdot \frac{h}{|h|})|h|$$
从第一个等号可以看出梯度决定了一个线性算子，第二个等号的含义是(梯度和自变量$h$变化方向的单位向量的点积=)方向导数，乘以$h$的模长。

泛函的时候：
$$L_{x_0}(h)=\delta J|_{x_0}(h)$$

微分和导数的区别

考虑线性函数$y=kx$在$x_0$点的微分，显然用线性函数逼近线性函数只要它自己就好，不论$x_0$怎么变化得到的线性函数都是他自己，导数就是把这个线性函数看成$x_0$的函数，是不变的，也就是是个常数。

$e^x$的导数还是$e^x$意思是$x_0$的逼近线性函数是$L_{x_0}(h)=e^{x_0}h$.

模

模的要求越严格其定义下的极值越弱，因为在模定义下接近极值点的点越少，比如1-norm要求函数属于$C^1$，一阶可微连续，极值就是检查在这个norm下，靠近极值点(函数$y^*$)的其他点(其他一阶可微连续函数)，因为1-norm的定义要求一阶导数也要很接近才叫接近，所以会排除很多一阶导数变化很大的扰动，也就是这个极值要求要弱一些(很多函数被排除了)。

一个强极值(斩掉的扰动更多)必然是一个弱极值，反过来弱极值的必要条件也是强极值的必要条件。

Euler-Lagrange equation

Basic Calculus of Variations Problem：
求极值:$$J(y):=\int_a^b L(x,y(x),y\ '(x))dx$$
其中$y$满足$y(a)=y_0, y(b)=y_1$.

functional $J$取极值的一阶必要条件是$y$满足Euler-Lagrange equation:
$$L_y=\frac{d}{dx}L_{y\ '}$$

一个包含求$L$在一个区间上的积分的极值问题，转化为$L$的在这个区间上的微分方程，含义是解在每个局部无穷小的区间上都是最优的，没有局部的"shortcut".


定义在有限维空间上的线性函数自然是连续的，也就是线性可以推出连续性，但是在无限维线性空间(比如连续函数的空间)，定义在其上的线性泛函的连续性不能直接从线性得出，但是连续性和下面两条等价：1）在0点连续，2）线性泛函有界，即存在$M>0$使得$|L(x)|\leq M|x|$。

Optimal Control： 有限维

无约束的情况

连续可微函数在某点取局部极（小）值的一阶必要条件是梯度在这点为0：证明方法，梯度的定义可以直接用公式定义，假设在这点梯度不为0，这里要用到一个梯度的性质（需要证明，方向导数是梯度和方向向量的点积）。由这点$x^*$我们总可以找到一个方向导数为负的方向$v$（和梯度向量夹角大于90度）。如果自变量往方向导数为负的方向移动，不管移动多小，中间取值$f(x^*+hv)$不可能都比这点$f(x^*)$大，可以把方向导数写成极限的形式：
$$\lim_{h\rightarrow 0}\frac{f(x^*+hv)-f(x^*)}{h}$$
如果都比这点大，那么方向导数必然收敛到0或者正数，这和我们选的方向导数为负这个事实矛盾，也就是$f(x^*)$不是极小因为不管多小的$x^*$领域内，总有比$f(x^*)$小的点。

几何上看如果一个线性函数不为0，必可以找到一个向量，线性函数把这个向量映到负值，比如$L(v) \neq 0$，令$u=L(v)v$，计算可以知道$L(u)=[L(v)]^2 > 0$所以$L(-u) < 0$, 梯度为0的点叫critical point (or stationary point) 二阶必要条件是Hessian在这点半正定：对于critical point，这点附近的函数可以用Hessian决定的二次形逼近，Hessian反应了这点的曲率情况。

二阶充要条件梯度为0，Hessian正定。上面必要条件的证明都是用反证法，找到存在比这点函数值更小的值，充分性的证明关键是找到那个最小的$\epsilon$球面，这里要用到球面的紧性。每个单位方向找个$\epsilon$，得到一个单位球面上的函数，利用紧性找到最小的$\epsilon$。

几何背景

二维数量场(也就是目标函数是$x,y$的函数)可以看成三维空间的曲面$(x,y,f(x,y))$，这个曲面上某点的法向量在$x,y$平面上的投影就是数量场的梯度。我们知道梯度总垂直于等值面，二维的时候就是等值线。

曲面切空间在$x,y$平面上的投影给出了一个曲面上曲线和$x,y$平面上曲线的对应，也就是切空间和$x,y$平面同构。

二维空间的线性函数$w=ax + by = (a, b)\cdot (x, y)$可以有一个二维向量决定，数量场的梯度向量决定了一个线性函数，这个函数在选定的点可以用于逼近数量场。

但是如果允许曲面在三维空间旋转，那么总可以使得选定点的法向在$x, y$平面的投影为0,，对应数量场这点的梯度为0。所以对曲面来说选定点的对应的数量场梯度其实反映了切平面和$x, y$平面的夹角的关系。

梯度给出了一种计算任意$x,y$平面方向导数的方法，就是用选定方向的单位向量和梯度做点积。而Hessian则是给出了一种计算任意两个方向二阶导数的办法，任给两个方向$L_{uv}=u^T H v$。

任意两个方向二阶导数可以看成是$x,y$平面上的点先往$v$方向，然后往$u$方向移动，用一个线性函数逼近数量场的变换情况，需要两个向量输入得到一个数量的线性函数显然是一个二次型。后一个，往$u$方向移动可以用线性函数逼近$\nabla f(x^*+\delta_1 v) \cdot \delta_2 u = \nabla ( \nabla f(x^*) \cdot \delta_1 v ) \cdot \delta_2 u $

如果把方向导数看成是一种加权平均(单位向量看成归一化)，梯度给出的是n个正交方向(就是坐标方向)的量，单位向量给出n个正交方向的权重，点积是加权平均得到方向导数。

三维空间上的数量场：

任意约束

在证明无约束情况的必要条件的时候，我们假定了自变量总可以往和梯度夹角大于90度的方向移动，但是加上约束以后这种移动就不一定允许了（这里往那个方向移动的含义是移动的轨迹在这点的切向量和这个方向向量重合）。可移动的方向称为feasible direction，现在考虑如果这个点是极小值，那么离开这个点的方向总是函数值不减少的方向，所以所有从这个点出发的feasible direction和梯度的夹角小于等于90度，也就是点积小于等于0。

无约束的时候必要条件为梯度为0，有约束的时候接近这个条件的描述是所有的feasible direction都和极值点的$f$的梯度方向垂直，也就是说梯度约束在feasible direction构成的子空间里（也就是投影）为0. 这时候二阶必要条件约束在feasible direction子空间里还是可以用的。

如果取值区域是凸的，函数也是凸的，那么1）局部极值同时是全局极值，2）一阶必要条件也是充分条件。

等式约束

$$h_1(x)=h_2(x)=\cdots =h_m(x)=0$$

等式约束相当于约束区域是一个低维曲面，看必要条件，点$x^*$是一个极值，任取一条曲面上过$x^*$点的曲线$\gamma(t)$,$t=0$对应$x^*$点，因为曲线在曲面上所以满足曲面方程$h_i(\gamma(t))=0$，对$t$求导
$$\nabla h_i(x^*)\cdot \gamma\ '(0)=0$$
又因为极值的条件可以推出$\gamma(t)$代表的feasible direction和目标函数$f$在这点的梯度是垂直的，由$\gamma(t)$的任意性知道目标函数$f$在$x^*$点的梯度是$\nabla h_i(x^*)$的线性组合。因为$f$在$x^*$点的梯度在有所有feasible direction构成的空间的正交补空间里，而$\nabla h_i(x^*)$是这个空间的一个基。

几何上解释就是如果目标函数$f$在$x^*$点的梯度不和这些曲面垂直，那么存在一条曲线通过$x^*$而且其在$x^*$点的切向量和$f$在$x^*$点的梯度的点积不为0，那么就有一个方向的在曲面上的移动使得目标函数变的更小，像上面的证明一样。

这个条件可以写成向量形式，就是Lagrange multipliers
$$\nabla f(x^*)+\lambda_1 \nabla h_1(x^*) + \cdots + \lambda_m \nabla h_m(x^*) =0$$
梯度是$n$维向量，所以上面的式子是$n$个方程，加上$m$个约束方程，我们得到$n+m$个等式的方程组，而且未知变量的个数正好是$n+m$个，$n$个是极值点的坐标$x^*$，和$m$个$\lambda$。

上面的证明比较几何化，下面的方法比较解析一点，只证明一个约束的情况。设$x^*$是极小值，$d_1, d_2$为任意$R^n$中的单位向量，考虑映射：
$$F:(\alpha_1, \alpha_2) \mapsto (f(x^*+\alpha_1d_1+\alpha_2d_2), h(x^*+\alpha_1d_1+\alpha_2d_2))$$
此映射的性质：1)把$(0,0)$映射到$(f(x^*), 0)$；2)在$(0,0)$点的Jacobian矩阵退化，$(f(x^*), 0)$点往横轴负方向的移动的点的轨迹，这个轨迹代表$h=0$，而且$f$的值减少，这是不可能的，也就是无论$(f(x^*), 0)$多小的领域内总有一点是没有逆像的，所以Jacobian矩阵在这点退化。
$$\left( \begin{array}{lr}
\nabla f(x^*)\cdot d_1 & \nabla f(x^*)\cdot d_2 \\
\nabla h(x^*)\cdot d_1 & \nabla h(x^*)\cdot d_2 \\
\end{array} \right)$$
也就是矩阵行向量一个是另一个的倍数，由$d_1, d_2$的任意性，可以推出$\nabla f(x^*) +\lambda \nabla h(x^*) = 0$.

Augmented Cost：
$$L(x,\lambda):=\sum^{m}_{i=1}\ \lambda_ih_i(x)$$
对这个函数求梯度，可以得到刚才提到的所有的$n+m$个方程，这样就把一个有约束的问题变成了无约束的问题。

算法：深度优先遍历的应用

无向图找桥

在无向图中使用上面的算法还有一个问题，上面把指向父节点的边看成是back edge，而这个back edge和父节点指向子节点的边又不构成无向图的cycle，其实完全是矩阵表示造成的重复计数。

因为不需要考虑forwar/cross edge改用White-Gray-Black染色的算法，touch顺序上只记开始访问时候的时间，这个值称为DFS tree number，从0开始计算。

假设无向图是连通的，任选一个节点就可以遍历整个图。

初始的时候所有节点都是white，遍历的时候从一个假想的-1节点开始，-1节点为gray，节点第一次被touch到的时候变为gray，当一个节点的所有邻居都被touch过后(wgbdfs返回的时候)这个节点变为black。

DFS Tree这样定义，DFS Tree包含所有gray节点指向white的边。



这样程序得到的back edge都有一个无向图的cycle对应。