The Micro-Price by Stoikov 精读

本文是Stoikov的paper：The Micro-Price A High Frequency Estimator of Future Prices的读书笔记。我不打算按照作者讲故事的flow去写，而是用我自己的行文逻辑，我认为前者叫"翻译"，后者才叫"精读"，当然这也意味着欣赏过原文的读者们再来看我的笔记应该会有更多的收获。

General Framework

作者认为，\(t\) 时刻的中间价 \(M_t\) 不是当前资产的一个合理价格，那什么才是合理的价格呢？一个fair price就应当是基于当前订单簿信息，对未来无穷远处价格给出的合理估计，用数学语言来表述就是 \[ \begin{equation} P^{micro}_t=\lim\limits_{\tau\to\infty}\mathbb{E} [ M_\tau | \mathcal{F}_t ] \end{equation} \] 其中 \(\mathcal{F}_t\)是 \(t\) 时刻的 \(\sigma\) 流（也就是 \(t\) 时刻所确定的信息）。

无穷远太远了，不方便我们的数学工具展开，那我们就先把 Eq.(1) 的极限符号去掉，先考虑一个时间足够远的估计： \[ \begin{equation} P_t^i = \mathbb{E} [ M_{\tau_i} | \mathcal{F}_t ], \tau_i > t \end{equation} \] 当我们使用数学工具导出了 \(P_t^i\) 的性质，再取个极限就可以了。

现在我们只需要一个假设，就可以证明 Eq.(2)是一个martingale，这个假设大多数情况是成立的：

Theorem 1. 在well defined的概率空间 \((\Omega,\mathcal{F}, \mathbb{P})\) ，以及 \(\sigma\) 流 \(\forall s < t, \mathcal{F}_s \subset \mathcal{F}_t \subset\mathcal{F}\) 中，如果中间价的变化 \(M_t-M_s\) 与中间价本身 \(M_t\) 相互独立，那么 \(P_t^i\) 是一个martingale under filtration \(\mathcal{F}_t\)。

Proof：根据假设，我们用条件期望的linearity，可以将 Eq.(2) 展开为： \[ \begin{equation} \begin{aligned} P_t^i &= \mathbb{E} [ M_{\tau_i} | \mathcal{F}_t ] \\ &= \mathbb{E} [ M_t | \mathcal{F}_t ] + \sum_{k=1}^{i} \mathbb{E} [ (M_{\tau_{i}}-M_{\tau_{i-1}}) | \mathcal{F}_t ] \end{aligned} \end{equation} \] 其中我们令 \(\tau_0=t\)，记号 \(\{\tau_1 < \tau_2 < ...\}\) 表示中间价产生变化的时间点： \[ \begin{equation} \tau_{i} = \inf\{ u > \tau_{i-1} | M_{u}-M_{u^-} \neq 0\} \end{equation} \] 为什么\(P_t^{i}\)是一个martingale呢，我们考虑时间点 \(s < t\) ，我们有： \[ \begin{equation} \begin{aligned} P_t^i &= \mathbb{E} [ M_t | \mathcal{F}_t ] + \sum_{k=1}^{i} \mathbb{E} [ (M_{\tau_{i}}-M_{\tau_{i-1}}) | \mathcal{F}_t ] \\ &= \mathbb{E} [ M_s+M_t-M_s | \mathcal{F}_t ] + \sum_{k=1}^{i} \mathbb{E} [ (M_{\tau_{i}}-M_{\tau_{i-1}}) | \mathcal{F}_t ]\\ &= \mathbb{E} [ M_s | \mathcal{F}_t ] + \mathbb{E} [ (M_t-M_s) | \mathcal{F}_t ] + \sum_{k=1}^{i} \mathbb{E} [ (M_{\tau_{i}}-M_{\tau_{i-1}}) | \mathcal{F}_t ]\\ \end{aligned} \end{equation} \] 两边对 \(s\) 时刻的已知信息 \(\mathcal F_s\) 取条件期望，并且使用条件期望的iterated conditioning性质，就证明了这个结论： \[ \begin{equation} \begin{aligned} \mathbb{E} [P_t^i | \mathcal{F}_s ] &= \mathbb{E} \bigg[ \mathbb{E} [ M_s | \mathcal{F}_t ] \bigg | \mathcal{F}_s\bigg] + \mathbb{E} \bigg[ \mathbb{E}[(M_t-M_s) | \mathcal{F}_t] \bigg| \mathcal{F_s} \bigg] + \sum_{k=1}^{i} \mathbb{E} \bigg[ \mathbb{E} [ (M_{\tau_{i}}-M_{\tau_{i-1}}) | \mathcal{F}_t ] \bigg| \mathcal{F}_s \bigg]\\ &= \mathbb{E} [ M_s | \mathcal{F}_s ] + \mathbb{E} [ (M_t-M_s) | \mathcal{F}_s ] + \sum_{k=1}^{i} \mathbb{E} [ (M_{\tau_{i}}-M_{\tau_{i-1}}) | \mathcal{F}_s ]\\ &=P_s^i \qquad (Q.E.D) \end{aligned} \end{equation} \]

我们令 \[ \begin{equation} g^k_t = \mathbb{E} [ (M_{\tau_k}-M_{\tau_{k-1}}) | \mathcal{F}_t ] \end{equation} \] 并且我们注意到 \(g^k\) 与 \(g^{k-1}\) 有循环迭代的关系 \[ \begin{equation} \begin{aligned} g^{k+1}_t &= \mathbb{E} [ (M_{\tau_{k+1}}-M_{\tau_{k}}) | \mathcal{F}_t ] \\ &= \mathbb{E}\bigg[ \mathbb{E}[M_{\tau_{k+1}}-M_{\tau_{k}} | \mathcal{F_{\tau_1}}] \bigg| \mathcal{F}_t\bigg] \quad &\text{iterated conditioning} \\ &= \mathbb{E}[g^{k}_{\tau_1} | \mathcal{F}_t] \quad &\text{definition of }g_{\tau_1}^k \end{aligned} \end{equation} \] 因此这个martingale还可以表示成一个更加简洁的形式： \[ \begin{equation} \begin{aligned} P_t^i &= \mathbb{E} [ M_t | \mathcal{F}_t ] + \sum_{k=1}^{i} \mathbb{E} [ (M_{\tau_{i}}-M_{\tau_{i-1}}) | \mathcal{F}_t ] \\ &=M_t + \sum_{k=1}^{i}g^i_t\\ g_t^{1} &= \mathbb{E}[(M_{\tau_1}-M_t) | \mathcal{F}_t]\\ g_t^{i+1} &= \mathbb{E}[g^{i}_{\tau_1} | \mathcal{F}_t] \end{aligned} \end{equation} \] 从 Eq.(9) 我们发现，这个martingale序列的本质就是对中间价 \(M_t\) 进行修正，使得其满足martingale的性质，如果我们把修正的项数取到无穷大，就得到了Micro-Price，当然它也是一个martingale under filtration \(\mathcal F_t\)。

那当我们 \(t\) 时刻掌握的信息与未来的价格变化 \(M_{\tau_{i+1}}-M_{\tau_{i}}\) 是无关的时候是什么样子呢？此时用条件期望表示的修正项全部都是0，也就是The Micro-Price等于mid price。这也解释了为什么中间价不是一个好的微观价格，因为使用中间价并没有用到与未来收益有关的信息，这意味着你将自己的微观结构建模在了一个naive的风险中性概率测度上（50% percent up and down）。而换句话说，当你拥有了一些与未来的回报（也就是价格变化）具有相关性的变量（也就是所谓的高频因子）时，micro-price能够保证，你基于这一组因子所修正出来的价格仍然是一个martingale under the information you considered。

A simple Example

有一个大家都well known的因子叫订单不平衡： \[ \begin{equation} I_t = I(Q^a_t,Q^b_t)=\frac{Q^b_t}{Q^b_t+Q^a_t}\in(0,1) \end{equation} \] 这个因子趋0时，价格往下的压力会变大，反之价格网上压力会变大，也就是说\(\mathbb{E}[M_\infty-M_t|I_t] > 0\)。随后作者用Finite State Markov Model对这个well known alpha下的micro-price做了一个计算，以此为例来教大家怎么用自己的private alpha去构造micro-price。在此之前，我们得回顾一下使用imbalance对中间价进行correction的一种naive的方法，也就是将best bid \(P^b_t\) 和best ask \(P^a_t\) 加权一下，我们管他叫weighted mid price： \[ W_t=I_tP^a_t+(1-I_t)P^b_t = M_t+I_t-\frac{1}{2} \] 这种方法虽然简单，但不是一个很好的correction，因为要让 \(W_t\) 成为一个martingale，我们需要做一个非常不合理的假设：

Theorem 2. 当以下条件满足时，weighted mid price是一个martingale，并且\(P^{micro}_t=W_t\) ：

1. 最优买卖的spread固定为1tick
2. 订单不平衡 \(I_t\) 在[0-1]区间时是布朗运动 (almost surely)
3. \(I_{\tau_1^-}=1\) 时，中间价往上走一个tick，也就是 \(M_{\tau_1}-M_{\tau_1^-}=1\) ，此时\(I_{\tau_1}\)有0.5概率取到 \(\epsilon\in(0,1)\), 0.5概率取到 \(1-\epsilon\)
4. \(I_{\tau_1^-}=0\) 时，中间价往下走一个tick，也就是 \(M_{\tau_1}-M_{\tau_1^-}=-1\) ，此时\(I_{\tau_1}\)有0.5概率取到 \(1-\epsilon\), 0.5概率取到 \(\epsilon\)

Proof：这里直接贴原文的证明过程了，我们将上述假设代入 Eq. (8)，得到一阶修正为 \[ \begin{equation} \begin{aligned} g^1_t = g^1(I_t) &= \mathbb{E}[(M_{\tau_1}-M_t) | I_t]\\ &= \frac{1}{2}\cdot\mathbb{P}[I_{\tau_1}=1|I_t]-\mathbb{P}[I_{\tau_1}=0|I_t] \\ & =I_t-\frac{1}{2} \quad \text{hitting time of Brownian Motion} \end{aligned} \end{equation} \] 二阶修正为 \[ \begin{equation} \begin{aligned} g^2_t = g^2(I_t) &= \mathbb{E}[g^1(I_{\tau_1})|I_t]\\ &=\mathbb{E}[I_t-\frac{1}{2}|I_t]\\ &=\frac{1}{2}\epsilon-\frac{1}{2}(1-\epsilon)-\frac{1}{2} \end{aligned} \end{equation} \] 令 \(\epsilon\to0\)，于是2阶修正为0，高阶修正也为0，此时有 \(P^{micro}_t=W_t\) is a martingale。

从这个假设的阐述就能知道它是基本不可能成为一个martingale，因此weighted mid price是一个bad correction，这个例子彰显了the Micro-price是如何的好。

衍生品的定价理论3：二项式定价模型

在博客的第一部分，我们将资产价格建模为几何布朗运动，根据delta对冲的方法导出其衍生品的Black-Scholes模型，现在我们考虑一个离散的玩具模型（二项式定价模型），通过这个模型，我们将阐述一个比构造delta中性投资组合，使得其收益等价于无风险利率更好的衍生品定价思想。我们将会通过标的物复制衍生品收益的方法来得出衍生品的定价理论，最终我们将得到一个结论，一个衍生品的价格，就是你从头到尾对冲掉所有标的物风险的成本。这个结论足够简洁，并不依赖于标的物资产的SDE是什么样的形式，这种方法叫做风险中性定价原理。

随机最优控制理论3: 连续情况的动态规划——HJB方程

前面的一篇文章讲述了如何在一个时间离散的体系下进行动态规划，现在我们对时间连续的体系构建这一套理论，从离散状态下的Bellman Equation，结合经典力学中的最下作用量原理，我们就能得到连续时间下的动态规划方程——Hamilton-Jacobi-Bellman equation (HJB equation).

经典力学框架的回顾

最小作用量原理

考虑一个经典物理系统，一个运动质点的作用量为拉格朗日量对时间的累积： \[ \begin{equation} S(q)= \int_0^{T}L(q,\dot{q},t)dt \end{equation} \] 其中 \(q=q(t)\) 是广义坐标，\(\dot{q} := dq/dt\) 是广义速度。质点从 \(q(0)\) 到 \(q(T)\) 之间有无数条可能的路径，最小作用量原理告诉我们，满足物理学规律的那条路径，将使得作用量取到最小, 利用变分原理 \(\delta S = 0\) \[ \begin{equation} \begin{aligned} 0 &= \delta S(q,t) \\ \Rightarrow 0 &= \delta\int_0^{T}L(q,\dot{q},t)dt \\ &= \int_0^{T} \left(\frac{\partial L}{\partial q}\delta q + \frac{\partial L}{\partial \dot{q}}\delta\dot{q} \right)dt \\ &= \int_0^{T} \frac{\partial L}{\partial q}\delta q dt + \int_0^{T} \frac{\partial L}{\partial \dot{q}}\delta\dot{q}dt \\ &= \int_0^{T} \frac{\partial L}{\partial q}\delta q dt + \int_0^{T} \frac{\partial L}{\partial \dot{q}}\frac{d \delta q}{dt}dt \\ \end{aligned} \end{equation} \] 将等号右边第二项分部积分： \[ \begin{equation} \begin{aligned} \int_0^{T}\frac{\partial L}{\partial \dot{q}}\frac{d \delta q}{dt}dt = \frac{\partial L}{\partial \dot{q}}\delta q|_{0}^{T} - \int_0^{T}\frac{d}{dt}\frac{\partial L}{\partial \dot{q}}\delta qdt \end{aligned} \end{equation} \] 由于变分取到极值的条件是 \(\delta q(0) = \delta q(T)=0\) ,于是代入得到 \[ \int_0^{T} \left(\frac{\partial L}{\partial q}-\frac{d}{dt}\frac{\partial L}{\partial \dot q}\right)\delta q dt = 0 \] 由于积分是任意的，所以括号里的被积函数必须为0，于是得到欧拉-拉格朗日方程： \[ \frac{\partial L}{\partial q}-\frac{d}{dt}\frac{\partial L}{\partial \dot q} = 0 \] 其中，\(\partial L/\partial q\)称为广义力，\(\partial L/\partial\dot{q}\) 称为广义动量，因此拉格朗日方程这就是牛顿第二定律的高级版本。由拉格朗日方程解出来的 \(q^* = q^*(t)\) 为真实世界的运动轨迹，也就是满足最小作用量的最优路径。

Hamilton-Jacobi方程

我们注意到，最小作用量原理，是一个过程量，也就是说，只要 \([0,T]\) 整个时间区间的过程中，如果有一个最优粒子的运动轨迹 \(q^*(t)\)，使得这个区间内的作用量是最小的，那么\([0,T]\) 区间内的最优轨迹 \(q^*(t)\) 在 \([t1,t2]\in [0,T]\) 应该也是让作用量取到最小，也就是对于时间区间 \([0,t]\) 的作用量 \[ S(q,t) = \int_0^t L(q,\dot{q},\tau)d\tau \] 于是作用量的全微分为： \[ \begin{equation} \begin{aligned} Ldt =dS &= \frac{\partial S}{\partial q}dq+\frac{\partial S}{\partial t}dt \\ &= \frac{\partial S}{\partial q}\dot{q}dt+\frac{\partial S}{\partial t}dt \\ &= \left(\frac{\partial S}{\partial q}\dot{q}+\frac{\partial S}{\partial t}\right)dt \end{aligned} \end{equation} \] 而最小作用量原理下的最优轨迹 \(q^*\) , 满足拉格朗日方程，于是作用量对坐标的偏微分为 \[ \begin{equation} \begin{aligned} \frac{\partial S}{\partial q} &= \frac{\partial }{\partial q}\int_0^t L(q,\dot{q},\tau)d\tau \\ &= \int_0^t \frac{\partial L}{\partial q}d\tau \\ &= \int_0^t \frac{d}{d\tau}\left(\frac{\partial L}{\partial \dot{q}}\right)d\tau \\ &= \frac{\partial L}{\partial \dot{q}}|_{0}^{t} = p(t) \end{aligned} \end{equation} \] 因此 \(p=\partial S/\partial q = \partial L/\partial\dot{q}\)，于是我们得到 \[ p\dot{q}+\frac{\partial S}{\partial t}-L = 0 \] 我们定义哈密顿量 \(H(p,q,t)=p\dot{q}-L\) , 于是得到了哈密顿-雅克比方程 \[ \frac{\partial S(q,t)}{\partial t} + H(p,q,t) = 0 \] - Remark: 哈密顿量还可以通过拉格朗日量，由勒让德变换导出一样的结果，并且后者能导出哈密顿量满足的正则方程，由于正则方程不在我们的讨论范围内，这里就略过了。

注意对区间变化的作用量还可以使用这样的定义： \[ S(q,t) = \int_t^T L(q,\dot{q},\tau)d\tau \] 区别在于对哈密顿量的定义里，差一个正负号。后面在推导HJB方程时，我们会使用后者，这里使用前者是遵循经典力学的惯例。因为经典力学中，我们往往知道的边界条件是时间开始时 \(q(0)\) 和 \(\dot{q}(0)\) , 而在最优控制中，我们往往知道的是在时间结束时 \((t=T)\) 时刻的边界值。

Hamilton-Jacobi-Bellman方程

实际上，把离散时间的动态规划推广到连续层面，已经由最小作用量原理，在力学上做过一遍了，我们只要把它推广到任意的最优控制体系中即可。最小作用量原理，实际上就是一个动态规划问题，我们要找出一个最优的路径 \(q^*\), 使得作用量取最小： \[ \begin{aligned} S(q,t) &= \min_{q}\int_0^TL(q,\dot{q},t)dt \\ s.t. & \quad \dot{q} = \dot{q}(q,\dot{q},t) \end{aligned} \] 在这里，我们对广义速度进行控制，来控制质点的运动轨迹，使得系统的作用量达到最小。而在一个更一般化的情况里： \[ \begin{aligned} \text{作用量} &\to \text{收益(max) or 成本(min)} \\ \text{坐标} &\to \text{状态 }x \\ \text{速度} &\to \text{操作 }\pi \\ \end{aligned} \] 这里以累计收益为例，我们定义 Bellman 函数为在最优控制 \(\pi^*\) 下所获得的最大收益: \[ \begin{equation} \begin{aligned} V(x,t) &= \max_\pi \left\{g(x(T))+ \int_t^T r(x(s), \pi(s))ds \right\} \\ s.t. \quad \dot{x} &= f(x,\pi) \end{aligned} \end{equation} \] 其中第一项是终止收益，也是边界条件 \[ V(X_T,T) = g(x(T)) \] 第二项是时间累计的收益，可以看到回报函数 \(r(x,\pi)\) 就是一个广义的拉格朗日量，Bellman 函数就是广义的作用量，我们定义广义的动量 \[ p=-\frac{\partial V}{\partial x} \] 对 Bellman 函数求全微分得： \[ \begin{equation} \begin{aligned} -rdt = dV &= \frac{\partial V}{\partial t}dt + \frac{\partial V}{\partial x}dx \\ &= \frac{\partial V}{\partial t}dt + \frac{\partial V}{\partial x} \dot{x}dt \\ &= \frac{\partial V}{\partial t}dt - p \dot{x}dt \\ \Rightarrow 0 &= \frac{\partial V}{\partial t} + \max_{\pi}(r-p\dot{x}) \end{aligned} \end{equation} \] 定义广义的哈密顿量: \(H=\max_{\pi}(r-p\dot{x})\) ，于是得到了Hamilton-Jacobi-Bellman (HJB)方程: \[ \begin{equation} \left\{ \begin{aligned} \frac{\partial V}{\partial t} + H(x, p,t) &= 0 \\ V(x,T) &= g(x) \end{aligned} \right. \end{equation} \] 这个推广的最小作用量原理称为Pontryagin Maximum Principle。

进一步地，我们将连续时间的动态规划原理，推广到不确定的体系。在具有随机性的体系里，我们寻求一个最优控制 \(\pi^*\), 使得目标收益的期望值取到最大: \[ \begin{equation} \begin{aligned} V(x,t) &= \max_\pi \mathbb{E}_{t,x} \left[ G(X_t^\pi)+ \int_t^T F(X_s^\pi, \pi_s,s)ds \right] \\ s.t. \quad dX_t^\pi &= \mu(X_t^\pi, \pi_t,t)dt+\sigma(X_t^\pi, \pi_t,t) dW_t \end{aligned} \end{equation} \] 其中 \(X_t\) 为伊藤过程，\(W_t\) 为布朗运动(Weiner过程)。这里就不能直接套用确定性系统里的东西了，只能类比，因为求微分的方式要使用伊藤引理： \[ \begin{equation} \begin{aligned} dV &= \left( \frac{\partial V}{\partial t} + \frac{\partial V}{\partial x}\mu + \frac{1}{2}\frac{\partial^2 V}{\partial x^2}\sigma^2 \right)dt+\frac{\partial V}{\partial x}\sigma dW_t \\ V(x,t) &= \max_{\pi} \mathbb{E}_{x,t} \left[ V(x_{t+dt},t+dt) + F(X_t^\pi, \pi_t, t) dt \right]\\ & \Rightarrow \frac{\partial V}{\partial t} + \max_{\pi} \left\{ \frac{\partial V}{\partial x}\mu + \frac{1}{2}\frac{\partial^2 V}{\partial x^2}\sigma^2 + F(X_t^\pi, \pi_t, t) \right\} = 0 \end{aligned} \end{equation} \] Eq. (18) 第一行是伊藤引理，第二行是无穷小形式的动态规划原理，第三行就是最终得到的HJB方程。伊藤引理中的不确定项在求平均值的时候被消掉了： \[ \mathbb{E}_{x,t}\left\{ dW_t \right\} = 0 \] 但观察HJB方程的形式，我们仍然可以定义哈密顿量 \[ H(x,t) = \max_{\pi} \left\{ \frac{\partial V}{\partial x}\mu + \frac{1}{2}\frac{\partial^2 V}{\partial x^2}\sigma^2 + F(X_t^\pi, \pi_t, t) \right\} \] 得到与Hamilton-Jacobi方程完全一样的形式。

随机最优控制理论2: 不确定的系统

前面的一篇文章讲述了如何在确定性的问题下进行动态规划，现在我们把确定性的弄到不确定的体系里面。首先看一下马尔科夫链。

Markov Chain

定义1. 离散时间的马尔科夫链

设\(\mathcal{X}\)为一可数集，表示所有可能的状态集合，\(\lambda=(\lambda_x:x\in\mathcal{X})\)为一初始概率分布，也就是 \[ \sum_{x\in\mathcal{X}}\lambda_x=1 \] 对于任意两个状态\(x,y\in\mathcal{X}\)，我们定义转移矩阵\(P\), 其中\(P_{xy}\)代表从状态\(x\)转移到状态\(y\)的概率，也就是 \[ \sum_{y\in\mathcal{X}}P_{xy} = 1 \] 一个离散时间的马尔科夫链为一个时间的随机变量\(X=X_t\in\mathcal{X}, t\in \mathbb{Z}^+\), 在\(t=0\)有初始分布: \[ \mathbb{P}(X_0=x_0) = \lambda_{x_0} \] 并且满足 \[ \begin{aligned} \mathbb{P}(X_{t+1}=x_{t+1}|X_t = x_t,...,X_0=x_0) &= \mathbb{P}(X_{t+1}=x_{t+1}|X_t = x_t) \\ &=P_{x_tx_{t+1}} \end{aligned} \] 上面的性质称为马尔可夫性，也就一个马尔科夫链的未来\(X_{t+1}\)在当前\(X_t\)，与过去\((X_{1},...x_{t-1})\)条件独立，换句话说就是未来每个状态的概率分布只由当前\(X_t=x_t\)决定。

根据上面这个性质，我们可以找出一个生成马尔科夫链的方法：

定理1. 设 \(\mathcal{U}=U_t\in[0,1]\) 为均匀分布的随机变量, \(X_0\in\mathcal{X}\)为一个随机变量。通过函数 \(f:\mathcal{X}\times \mathcal{U}\rightarrow \mathcal{X}\) 递推生成的随机变量\(X_t\) \[ X_{t+1}=f(X_t,U_t) \] 是一个马尔科夫链.

Markov Decision Process

现在我们来把动态规划问题带进马尔科夫链中。如果一个动态规划问题中，其状态的演化是一个马尔科夫链，那么我们就称之为Markov Decision Process (MDP).

定义2. Markov Decision Process

考虑一个离散的时间过程 \(t=0,1,...T\) ，有可数的状态集合 \(x\in\mathcal{X}\) ，操作集合 \(a\in\mathcal{A}\) 以及在给定状态 \(x\) 后采取操作 \(a\) 的回报 \(r(x,a)\). 如果从动态规划函数 \(f\) 是随机的，并且满足马尔可夫性： \[ X_{t+1}=f(X_t,a_t;U_t)\equiv f(X_t,a_t) \] 我们称这个过程为Markov Decision Process。其中 \(U_t \in [0,1]\) 是一个均匀分布的随机过程。

与确定性的系统类似，我们的动态规划目标仍然是找到一个策略 \(\pi\), 使得效用函数\(R(x_0,\pi)\) 达到最大。但由于 \(f\) 的随机性，我们在定义效用函数的时候，就只能取其期望值： \[ \begin{equation} V(X_0)=\left\{ \begin{aligned} \text{maximize }& R(X_0,\Pi) = \mathbb{E}\left[ r(X_T) + \sum_{i=0}^{T-1}r(X_i,\pi_i) \right]\\ \text{over }& \Pi \in \mathcal{P} \end{aligned} \right. \end{equation} \] 接下来我们来看其对应的Bellman Equation。仿照确定的体系，考虑从终止时间 \(T\) 往前数 \(\tau\) 个时间，考虑从\(t=T-\tau\)以后的未来回报： \[ \begin{equation} \begin{aligned} R(X_{T-\tau},\pi) &= \mathbb{E}_{\tau}\left[ r(X_T) + \sum_{i=T-\tau}^{T-1}r(X_i,\pi_i) \right] \end{aligned} \end{equation} \] 这一段时间的未来回报，也对应了一个动态规划 \(V(\tau,X_{T-\tau})\) : \[ \begin{aligned} V(\tau,X_{T-\tau}) &= \max_{\pi} R(X_{T-\tau}, \pi) \\ &=\max_{\pi} \mathbb{E}_{\tau}\left[ r(X_T) + \sum_{i=T-(\tau-1)}^{T-1}r(X_i,\pi_i) + r(X_\tau,\pi_\tau) \right] \\ &=\max_{\pi}\left\{ \mathbb{E}_{\tau}\left[ r(X_T) + \sum_{i=T-(\tau-1)}^{T-1}r(X_i,\pi_i)\right] + r(X_\tau,\pi_\tau) \right\}\\ &=\max_{\pi}\left\{ \mathbb{E}_{\tau}\left[ \max_\pi\left\{ \mathbb{E}_{\tau-1}\left[ r(X_T) + \sum_{i=T-(\tau-1)}^{T-1}r(X_i,\pi_i)\right]\right\}\right] + r(X_\tau,\pi_\tau) \right\}\\ &= \max_{\pi}\left\{ \mathbb{E}_{\tau}\left[V_{\tau-1}(X_{\tau-1}) \right] + r(X_\tau,\pi_\tau)\right\} \\ &= \max_{\pi}\left\{ \mathbb{E}_{\tau}\left[V_{\tau-1}(f(X_{\tau},\pi_\tau)) \right] + r(X_\tau,\pi_\tau)\right\} \end{aligned} \]

随机最优控制理论1: 动态规划

最近在倒腾订单执行的东西，发现这套数学框架非常满足我的需求，因此现学现卖，做点笔记。

基础的定义

定义1. state, action, rewards

考虑一个离散时间的系统\(t=\{0,1,...T\}\)， 定义:

1.\(x\in\mathcal{X}\)为状态以及所有状态的集合, \(x_t\)为\(t\)时刻的状态.

2.\(a\in\mathcal{A}\)为操作以及所有可能操作的集合

3.在状态\(x\)时采取操作\(a\)获得的回报为\(r=r(a,x)\), 并且定义\(r(x)\)为在最终时间\(T\)，状态为\(x\)时的最终回报

定义2. 动态规划函数

操作\(a\)作用以后，我们会从当前状态\(x\)进入下一个状态\(\hat{x}\), 这个状态转移函数称动态规划函数\(f: \mathcal{X}\times\mathcal{A}\rightarrow \mathcal{A}\) \[ \hat{x} = f(x,a) \] 定义3. 策略和效用函数

定义一个策略\(\pi = (\pi_0,\pi_1,...\pi_{T-1})\), 表示在时刻\(t\)时采用操作\(\pi_t\). 在选定了最初状态\(x_0\)后，该操作与动态规划函数定义了一个状态序列\(x_t\): \[ x_{t+1}=f(x_t,\pi_t) \] 我们定义从时间0到T结束后，每次action的回报之和为效用函数: \[ R(x_0,\pi) = r(x_T) + \sum_{i=0}^{T-1}r(x_i,\pi_i) \] 定义4. 动态规划

整个最优控制理论的目标，就是找到一个策略\(\pi\in\Pi\)，能够使得效用函数达到最大： \[ V(x_0)=\max_{\pi} R(x_0, \pi) \] 其中\(V(x_0)\)是最大效用, \(\Pi\)为所有可能策略的集合。

对于任意时间节点\(t\)，我们也有

一个动态规划用形式化的语言定义就是: \[ \begin{equation} V(x_0)=\left\{ \begin{aligned} \max_\pi& R(x_0,\pi) = r(x_T) + \sum_{i=0}^{T-1}r(x_i,\pi_i)\\ \text{s.t }& x_{t+1} = f(x_t,\pi_t) \\ \text{over }& \pi_t \in \mathcal{A} \end{aligned} \right. \end{equation} \]

Bellman Equation

定理1. Bellman Equation

我们考虑从终止时间\(T\)往前数\(\tau\)个时间，也就是从\(t=T-\tau\)时刻后的的未来回报： \[ \begin{equation} \begin{aligned} R(x_{T-\tau},\pi_{T-\tau}) &= r(x_T) + \sum_{i=T-\tau}^{T-1}r(x_i,\pi_i)\\ &= r(x_T) +\sum_{i=T-(\tau-1)}^{T-1}r(x_i,\pi) + r(x_\tau,\pi_\tau)\\ &= R(x_{T-(\tau-1)},\pi_{T-(\tau-1)}) + r(x_\tau,\pi_\tau) \end{aligned} \end{equation} \] 这一段时间的未来回报，也对应了一个动态规划： \[ \begin{equation} \begin{aligned} V(\tau,x_{T-\tau}) &= \max_{\pi}R(x_{T-\tau},\pi_{T-\tau}) \\ &= \max_{\pi}\left\{ R(x_{T-(\tau-1)},\pi_{T-(\tau-1)}) + r(x_\tau,\pi_\tau) \right\}\\ &= \max_{\pi}\left\{ \max _{\pi}R(x_{T-(\tau-1)},\pi_{T-(\tau-1)}) + r(x_\tau,\pi_\tau) \right\}\\ &= \max_{\pi}\left\{ V(\tau-1, x_{T-(\tau-1)}) + r(x_\tau,\pi) \right\} \\ &= \max_{\pi}\left\{ V(\tau-1,f(x_{T-\tau},\pi)) + r(x_\tau,\pi) \right\} \end{aligned} \end{equation} \] 这个结果称为Bellman Equation。它展示了一个以递归方式总的最优解的寻找方法：先寻找\(t=T\)时的最优策略，再寻找\(t=[T-1,T]\)时间段内的最优策略，以此类推。

例：平衡二叉树路径最大值

给定一个平衡二叉树，每个节点上有一值score:

1
2
3
4
5

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

寻找其从根节点到某个叶子节点的最大score路径。

Solution:

设平衡二叉树的深度为\(T\)，根节点深度为0。\(x \in \mathcal{X}\)为所有的树节点. Bellman Equation为 \[ V_{\tau} = \max_{\pi\in[\text{left, right}]}\left\{ V_{\tau-1}(f(x_\tau,\pi)) + r(x_\tau,\pi) \right\} \] 其中 \[ \begin{aligned} f(x,\text{left}) &:= \text{left}(x) \\ f(x,\text{right}) &:= \text{right}(x) \\ r(x,\pi) &:= \text{value}(x) \end{aligned} \] 于是可以通过递归的方式寻找最大score：

1
2
3
4

def maximum_path(node: TreeNode): int:
	if node == None:
        return 0
   	return node.score + max(maximum_path(node.left), maximum_path(node.right))

对于一个input:

1
2
3
4
5

     1
   /   \
  0     7
 / \   / \
1   5 6   5

最终得到结果为：14 root->right->left->terminated

衍生品的定价理论2：期权

期权(option)是一种以某种资产价格为标的物的衍生品。按照行权可以分为call option和put option. call option就是在行权日能够以某价格购买标的物的权力，put option就是在行权日能够以某价格出售某标的物的权力。按照行权时间，期权可以分为欧式期权和美式期权，欧式期权只有行权日到期那一刻才能行权，美式期权在到期之前任意一天都可以行权。

对于call option的买方，如果在行权时标的物的价格\(S_t\)高于行权价\(K\)，那么持有call option在在行权以后就能以行权价\(K\)买入标的资产，再以\(S_t\)卖出平仓，获得利润\(S_t-K\)，因此够获得的回报为 \[ \max\{S_t-K, 0\}-c \]

其中\(c\)为期权的价格。由于期权是0和游戏，对应卖方的回报就是 \[ c-\max\{S_t-K, 0\} \] 对于put option，如果在行权时标的物价格\(S_t\)低于行权价\(K\)，那持有put option在行权后就能以行权价\(K\)卖出标的资产，在以\(S_t\)买入平仓，获得利润\(K-S_t\)，因此能够获得的回报为 \[ \max\{K-S_t, 0\}-p \] 其中\(p\)为期权的价格。同样，对应卖方的回报为 \[ p -\max\{K-S_t, 0\} \] 由于持有call option在未来资产价格上涨时能获利，持有put option在未来资产价格下跌时能获利，因此call option又叫看涨期权，put option又叫看跌期权。

期权性质

由于欧式期权比的行权日是固定的，比较简单，这里只讨论欧式期权。首先是对于相同行权日和行权价格call/put option，其价格满足以下等式： \[ c+Ke^{-rT}=S_0+p \] 其中\(c,p\)为call/put option的价格，\(K\)为行权价，\(r\)为无风险利率，\(T\)为到期时间，\(S_0\)为标的物当前的价格。这个等式可以通过有效市场假设导出。我们把等号中每一项都当做一个投资组合的开仓，对于等号左边，等同于以价格\(c\)买入一张call option，以价格\(Ke^{-rT}\)买入一张无风险债券。我们计为投资组合1。到行权日时，这个投资组合的价格变为 \[ \max\{S_t-K, 0\} + K = \max\{S_t, K\} \] 同样，对于等号右边，等同于以价格\(p\)买入一张put option，并且以当前价格\(S_0\)买入标的资产，我们计为投资组合2。到行权日时，这个投资组合的价格变为 \[ \max\{K-S_t, 0\} + S_t = \max\{S_t, K\} \] 因此这两个投资组合未来的价格是完全一致的，如果call/put option的价格不满足这个关系，那就获得了无风险套利机会：如果\(c+Ke^{-rT}<S_0+p\)，就开多投资组合1，开空投资组合2，最终获得\(S_0+p-c-Ke^{-rT}\)的无风险利润，反之亦然，这违反了有效市场假设。

上面的证明方法还可以导出call option的价格区间为 \[ \begin{equation} \begin{aligned} S_0 &\geq c \geq \max\{S_0-Ke^{-rT}, 0\} \\ \end{aligned} \end{equation} \] call option价格不会高于标的物价格，\(S_0 \geq c\)是显然的，因为这会导致买call option的收益严格小于直接买入标的物的收益。对于投资组合1，在行权以后获得的收益为 \[ \max\{S_t, K\} - c - Ke^{-rT} \] 如果\(c < \max\{S_0-Ke^{-rT}, 0\}\)，投资组合1也将带来高于无风险利率的无风险收益，违反了有效市场假设。

相似地，put option的价格区间为 \[ \max\{Ke^{-rT}-S_0, 0\} \leq p \leq K \] put option价格不会高于行权价格，\(K \geq c\)是显然的，因为这会导致买put option的收益严格小于直做空标的物的收益。我们假设资产价格不会跌至负数，那么对于下界，投资组合2在行权后获得的收益为 \[ \max\{S_t, K\} - p - S_0 \geq \max\{K-S_0,0\} \] 如果\(\max\{Ke^{-rT}-S_0, 0\} \leq p\)，对于投资组合2也将带来高于无风险利率的无风险收益，违反了有效市场假设。

衍生品的定价理论1：BS模型

所谓的衍生品(derivative)，就是以某金融资产作为标的物而创造的新的金融资产。显然，衍生品的价格也应该由标的物来决定。在对衍生品的价格进行建模时，我们会将标的物与衍生品的价格都当做具有马尔可夫性的随机过程，并且我们认为，金融资产的收益应当服从lognormal分布。当然，定价当然也要假设市场为有效市场，最后作为一个学物理的，在使用求期望的数学符号上，就不用\(E(X)\)而是用\(\langle X\rangle\)了。

Wiener过程和Itô 过程

一个随机变量\(X(t)\)如果满足以下2个性质，我们就称其为Wiener过程:

1.任意 \(\Delta t\) 区间内，随机变量 \(X\) 的变化 \(\Delta z\) 服从正态分布: \[ \Delta z = \epsilon \sqrt{\Delta t} \]

其中\(\epsilon\)为标准正态分布\(\epsilon \sim \phi(0,1)\).

2.对于任意两个不相交的时间区间 \(\Delta t_1, \Delta t_2\) 产生的变化 \(\Delta z_1, \Delta z_2\) 分布相互独立(马尔可夫性).

性质I. 中使用根号，是因为这样能保证\(\Delta z\)的方差为\(\Delta t\)，性质II. 的马尔可夫性，又保证了任意两个不相交区间方差的可加性。考虑这样一个情况，从时间0点开始，一个时间段\(T\)内Wiener过程的变化量为 \[ z(T)-z(0)=z \] 我们将时间段\(T\)一分为二，\(T\)时间的增量应该是二者之和： \[ z = z_T=z_{T_1}+z_{T_2}=z_1+z_2 \] 其中\(T=T_1+T_2\). 由于求均值是线性的算符，天然满足可加性 \[ 0 = \langle z\rangle = \langle z_1+z_2\rangle =\langle z_1\rangle+\langle z_2\rangle = 0 \] 但如果等号两边取方差，等式左边： \[ \begin{equation} \begin{aligned} \langle (z-\langle z\rangle)^2 \rangle &= \langle z^2\rangle \end{aligned} \end{equation} \] 等号右边为 \[ \begin{equation} \begin{aligned} \langle (z_1+z_2-\langle z_1+z_2\rangle)^2 \rangle &= \langle (z_1+z_2)^2 \rangle\\ &= \langle z_1^2+z_2^2+2z_1z_2 \rangle \\ &= \langle z_1^2 \rangle + \langle z_2^2 \rangle + 2\langle z_1z_2 \rangle \\ &= \langle z_1^2 \rangle + \langle z_2^2 \rangle \end{aligned} \end{equation} \] 因此 \[ T =\langle z^2\rangle = \langle z_1^2\rangle + \langle z_2^2\rangle = T_1+T_2 \] 这个well defined的性质要由马尔可夫性才能得出，因为它保证了\(\langle z_1z_2 \rangle = 0\). 对于Weiner过程，我们就可以考虑一个无穷小变化时间\(dt\)内的Weiner过程的变化\(dz\), 在经过时间\(T\)以后有: \[ \Delta z = \int_0^Tdz \sim \phi(0,T) \] 如果一个随机变量\(X(t)\)在\(\Delta t\)区间内的变化\(\Delta z\)服从的是一个\(\phi(a,b^2)\)的正态分布，我们就称其为广义的Weiner过程，一个广义的Wiener过程的变化量可以写作： \[ \Delta x = a\Delta t + b\epsilon\sqrt{\Delta t} \] 资产的价格当然不是均值为0的随机游走，因此我们要把Wiener过程广义化才能用于对资产价格的建模。那么我们就将一个随机变量\(X(t)\)分为两部分，一部分是有确定收益的增量，另一部分是Wiener过程的随机游走项作为风险项： \[ \Delta x = a(x,t)\Delta t + b(x, t)\epsilon\sqrt{\Delta t} \] 这样一个过程就成为Itô 过程, \(a\)称为drift rate, \(b\)称为variance rate。

Black-Scholes模型

在写出了一个资产的价格方程后，我们就可以根据衍生品与标的物的关系，推导出其价格应当满足的方程了。具体来说，如果一个随机变量为Itô 过程，满足 \[ dx = adt + bdz \] 其中\(dz\)是Wiener过程，那么一个以\(x\)为变量的随机过程\(G(x,t)\), 在\(\Delta t\)时间内产生的变化\(\Delta G\)近似为 \[ \Delta G \approx \frac{\partial G}{\partial x}\Delta x+\frac{\partial G}{\partial t}\Delta t + \frac{1}{2}\frac{\partial^2 G}{\partial x^2}\Delta x^2 + \frac{1}{2}\frac{\partial^2 G}{\partial t^2}\Delta t^2 + \frac{\partial^2 G}{\partial x\partial t}\Delta x\Delta t \] 注意到了\(\Delta x = a\Delta t + b\epsilon\sqrt{\Delta t}\)，一阶以上的变化可以略掉，代入得 \[ \begin{equation} \begin{aligned} \Delta G &\approx \frac{\partial G}{\partial x}\Delta x+\frac{\partial G}{\partial t}\Delta t + \frac{1}{2}\frac{\partial^2 G}{\partial x^2}\Delta x^2 + \frac{1}{2}\frac{\partial^2 G}{\partial t^2}\Delta t^2 + \frac{\partial^2 G}{\partial x\partial t}\Delta x\Delta t \\ &= \frac{\partial G}{\partial x}(a\Delta t + b\epsilon\sqrt{\Delta t}) + \frac{\partial G}{\partial t}\Delta t + \frac{1}{2}\frac{\partial^2 G}{\partial x^2}(a\Delta t + b\epsilon\sqrt{\Delta t})^2\\ &= \left( \frac{\partial G}{\partial x}a + \frac{\partial G}{\partial t} + \frac{1}{2}\frac{\partial^2 G}{\partial x^2}\epsilon^2b^2 \right)\Delta t + \frac{\partial G}{\partial x}b\epsilon\sqrt{\Delta t} \end{aligned} \end{equation} \] 对于\(\epsilon^2\)而言，\(\langle\epsilon^2\Delta t\rangle=\Delta t\)，而它的方差是比\(\Delta t\)更高阶的无穷小，所以我们忽略掉其对variance部分的贡献，然后把\(\Delta G\rightarrow dG\)，得到\(G(x,t)\)满足的方程为 \[ dG = \left( \frac{\partial G}{\partial x}a + \frac{\partial G}{\partial t} + \frac{1}{2}\frac{\partial^2 G}{\partial x^2}b^2 \right)dt+\frac{\partial G}{\partial x}bdz \] 这个结果称为Itô 引理。

我们认为，一个金融资产的价格随着时间应当是按照指数增长的。例如一笔利率为\(r\)，借出时面值\(K_0\)的债务，经过时间\(t\)后，按照本息偿还的面值应该为： \[ K(t) = K_0e^{r t} \] 求导可以得到 \[ \frac{dK}{dt} = rK_0e^{rt} = rK \Rightarrow \frac{dK}{K}=rdt \] \(r\)就是无风险资产的收益率。对应到一个资产\(S\)上，其收益率也应当分为确定的无风险部分以及不确定的风险部分: \[ \frac{\Delta S}{S} = \mu \Delta t + \sigma \Delta z \] 也就是 \[ \frac{\Delta S}{S}\sim\phi(\mu \Delta t, \sigma^2 \Delta t) \] 我们称\(\sigma\)为波动率(volatility)。于是一个风险资产的价格应当满足以下Itô 过程 \[ dS = \mu Sdt + \sigma Sdz \] 那么，以该资产为标的物的衍生品价格\(G(S(x,t),t)\)应当满足： \[ dG = \left( \frac{\partial G}{\partial S}\mu S + \frac{\partial G}{\partial t} + \frac{1}{2}\frac{\partial^2 G}{\partial S^2}\sigma^2S^2 \right)dt+\frac{\partial G}{\partial S}\sigma Sdz \] 离散形式为 \[ \Delta G = \left( \frac{\partial G}{\partial S}\mu S + \frac{\partial G}{\partial t} + \frac{1}{2}\frac{\partial^2 G}{\partial S^2}\sigma^2S^2 \right)\Delta t+\frac{\partial G}{\partial S}\sigma S\Delta z \]

资产的对数表达式

利用Itô 引理，我们可以导出一个资产价格的对数满足的分布。对于\(G = \ln(S)\)，有\(\partial G/\partial S = 1/S, \partial^2G/\partial S^2 = -1/S^2, \partial G/\partial t = 0\)，于是 \[ d\ln S = \left(\mu-\frac{\sigma^2}{2}\right)dt+\sigma dz \] 可以得到 \[ \ln (S_T)-\ln S_0 \sim \phi[\left(\mu-\frac{\sigma^2}{2}\right)T,\sigma^2T] \] 注意，连续复利的收益率和离散复利收益率是两个东西，因为离散复利收益率\(\mu = \ln \langle S_T/S_0\rangle\)，而连续复利的收益率是\(\langle \ln S_T/S_0\rangle\). 并且前者具有可加性，后者不具有，而且根据对数函数的凸性，有\(\ln \langle S_T/S_0\rangle > \langle \ln S_T/S_0\rangle\)。

我们将资产价格表达式写成和固定利率的无风险债券相同的形式： \[ S_T = S_0e^{xT} \] 其中 \[ x = \frac{1}{T}\ln\frac{S_T}{S_0}\sim\phi\left(\mu-\frac{\sigma^2}{2}, \frac{\sigma^2}{T}\right) \] 称为连续复利下的收益率。

衍生品价格的表达式

B-S模型利用了有效市场假设，即不存在无风险套利机会。考虑这样一个投资组合，卖出一份衍生品，再以\(\partial f /\partial S\)倍数买入标的物 \[ \Pi = -f+\frac{\partial f}{\partial S}S \] 在一段\(\Delta t\)后，产生的收益为 \[ \Delta \Pi = -\Delta f +\frac{\partial f}{\partial S}\Delta S = \left(-\frac{\partial f}{\partial t}-\frac{1}{2}\frac{\partial^2 f}{\partial S^2}\sigma^2S^2\right)dt \] 随机项被消除了，于是这就是一个无风险的收益。根据有效市场假设，这个收益的收益率一定是无风险利率： \[ \Delta \Pi = r\Pi\Delta t \] 于是有 \[ \left(-\frac{\partial f}{\partial t}-\frac{1}{2}\frac{\partial^2 f}{\partial S^2}\sigma^2S^2\right) = r\left(-f+\frac{\partial f}{\partial S}S\right) \] 最终整理得到 \[ \frac{\partial f}{\partial t} + rS\frac{\partial f}{\partial S}+\frac{1}{2}\frac{\partial^2 f}{\partial S^2}\sigma^2S^2 - rf = 0 \] 这就是BS模型。

微分流形笔记0：一些必要的前置数学工具

微分流形研究的对象是流形，所谓的流形就是曲线和曲面的推广。我们研究可微流形的方法就是让它在局部的性质与欧氏空间一致，也就是让它在某点邻域内的的切空间同构于欧式空间，利用我们所熟知的欧式空间性质进行研究，最后再利用同构映射变换回去。因此，一些研究在坐标变换下保持不变的量，i.e. 张量的性质的掌握是必要的。并且，为了将欧式空间上的微分和积分推广到定义在流形上的函数，我们有必要引入不依赖于坐标系所定义的微分形式，而这些内容也将cover进本章。

注意，以下的内容如果没有另作声明，就默认使用爱因斯坦求和约定, i.e. 遇到相同指标即求和: \[ a_ib_i=\sum_ia_ib_i \]

张量代数

我们知道，一个线性空间就是由其元素以及线性的代数结构(加法,数乘)组成的，我们了解一个线性空间\(V\)，只需要知道它的维数\(n\)以及一组基\(e_i\)，我们就可以将任意的元素\(v\)线性表示出来， i.e. \(v=v^ie_i\)。其中\(v^i\)是元素\(v\)在这组基下的坐标表示，在选用不同的基后，其坐标表示也将不同，坐标的变换恰好是基变换的逆：

\[ e'_i= A^j_{i}e_j \\ v^ie_i=v=v'^ie'_i=v'^iA^j_{i}e_j\Rightarrow v'_i=(A^j_{i})^{-1}v_j \]

至此，一个线性空间的内部结构就已经well known了。现在，我们来继续研究基于一个线性空间的线性函数，我们定义一个空间上的线性函数是从\(V\)到\(\mathbb{R}\)的一个线性映射：

\[ f:V\rightarrow\mathbb{R}\\ \forall u,v\in V,\lambda\in\mathbb{R}:\\f(\lambda u+v)=\lambda f(u)+f(v) \]

我们容易看出，所有定义在\(V\)到\(\mathbb{R}\)的全体线性映射，在加法：

\[ (f+g)(v)=f(v)+g(v) \]

和数乘：

\[ (\lambda f)(v)=\lambda\cdot f(v) \]

下构成一个线性空间，我们记这个空间为线性空间\(V\)的对偶空间\(V^*\)。

定义1：全体\(V\)到\(\mathbb{R}\)的线性映射构成\(V\)的对偶空间\(V^*\)

既然\(V^*\)也是一个线性空间，那么它的维数是多少？它的基和\(V\)种的基有什么关系呢？

定理1. 线性函数\(e^i\)构成\(V^{*}\)的一组基，如果满足\(e^ie_j=\delta^i_j\)

其中\(\delta^i_j\)是Kronecker delta：

\[ \delta^i_j= \begin{cases} 0 & i \neq j \\ 1 & i = j \end{cases} \]

注意，Kronecker delta的定义不管指标\(ij\)在上标还是下标上。

证明：

首先我们要证明\(e^i\in V^*\)。我们设有\(u,v\in V,\lambda \in \mathbb{R}\)，并且在基\(e_j\)下，\(u=u^je_j,v=v^je_j\)，根据\(e^i\)的性质有：

\[ e^i(u+v)=e^i(u^je_j+v^je_j)=u^je^ie_j+v^je^ie_j=e^i(u)+e^i(v)\\ e^i(\lambda u)=e^i(\lambda u^je_j)=\lambda (e^iu^je_j)=\lambda (e^iu) \]

因此\(e^{i}\in V^{*}\)。接下来我们需要证明它是一组基，也就是我们要证明\(\forall\alpha\in V^{*}\)都能被\(e^{i}\)线性表示。这里我们用线性代数里常规的反证法，设存在一组不为0的\(k_{i}\) ，使得\(e^{i}k_{i}=0\)，两边同时作用于\(e_j\)得：

\[ 0=0(e_j)=e^ik_ie_j=k_ie^ie_j=k_i\delta^i_j=k_j \]

这就证明了$ e^i \(是\) V^{*} $的一组基。并且，由定理1可以直接得到推论

\[ \text{dim}(V^*)=\text{dim}(V)=n \]

从对偶基\(e^i\)的定义就可以看到，它和\(V\)的基\(e_i\)是对应的，并且注意到:

\[ e_ie^j=\delta_i^j \]

因此一个线性空间对偶空间的对偶就是其本身，正是这个原因，空间\(V^{*}\)取名为\(V\)的对偶空间(dual space)。

既然\(e_i\)和\(e^i\)是对应的，那么在另一组基下它们的线性变换的关系也可以导出：

\[ e^ie_j=\delta^i_j=e'^ie'_j=e'^iA^k_je_k\\ \Rightarrow e'^i=(A^i_j)^{-1}e'^j \] 我们可以看到，当基\(e_i\)变换到另一组基时，其对偶基的变换关系为逆变换。基于此，我们将\(V\)中的向量成为协变矢量，\(e_i\)称为协变基，其对偶空间\(V^*\)中的向量称为逆变矢量，\(e^i\)称为逆变基。到现在为止，我们就可以解释使用上标和下标的意义了，上标表示对偶和逆变，下标表示协变，这个约定在张量的定义和使用中非常方便。以后的文字中，如果没有特别指出，那么上下标的使用均暗含这个意义。

现在，在得到了线性空间和对偶空间的性质之后，我们可以对张量下定义了，所谓的张量就是在坐标变换下不变的量，它在不同的坐标下可以有不同的表示，但坐标的选取并不会影响到其本身。

定义2：一个\((m,n)\)张量是一个多重线性函数\(T\):

\[ T: \underbrace{V^*\times V^*\times...\times V^*}_m\times\underbrace{V\times V\times...\times V}_n \rightarrow \mathbb{R} \\ T(u_1,u_2,..u_{i-1}, \lambda v+w, u_{i+1}, ...u_{m+n})=\lambda T(u_1,u_2,..u_{i-1}, v, u_{i+1}, ...u_{m+n}) \\+ T(u_1,u_2,..u_{i-1},w, u_{i+1}, ...u_{m+n}) \] 张量的阶数为\(m+n\)。

注意，这里的下标特指序数。多重线性指的是这个线性关系对任意指标下的向量都成立。我们将所有的协变向量\(u^i\)和逆变向量\(v_j\)用基展开，并且我们记它的基为\(T(e^{i_1},e^{i_2},...e^{i_m},e_{j_1},e_{j_2},...e_{j_n})=T^{i_1,i_2,..i_m}_{i_1,j_2,...j_n}\)，得到： \[ T(u_{1i_1}e^{i_1},u_{2i_2}e^{i_2},...u_{mi_m}e^{i_m},v^{1j_1}e_{j_1},v^{2j_2}e_{j_2},...v^{nj_n}e_{j_n})\\ =u_{1i_1}u_{2i_2}...u_{mi_m}v^{1j_1}v^{2j_2}...v^{nj_n}T^{i_1,i_2,..i_m}_{i_1,j_2,...j_n} \] 注意这里使用的爱因斯坦求和约定。既然张量是在坐标变换下不变的量，那么坐标变换只会影响到它的表示，而不会影响到其本身，我们设其中一个逆变基有变换\(e'^{i_k}=(A^{i_k}_{j_k})^{-1}e^{j_k}\)，它对应的线性空间的基变换应该为\(A^{i_k}_{j_k}\)。按照多重线性，那么对应的张量在坐标下的表示对应变换为\(A^{i_k}_{j_k}\)，和常规的坐标变换相反。反之，如果是协变基有变换\(e'_{i_k}=B_{i_k}^{j_k}e_{j_k}\)，那么对应张量在坐标下的表示应该变换为\((B_{i_k}^{j_k})^{-1}\)，和常规的坐标变换相同。因此，我们称\(V^{*} \times V^{*} \times ... \times V^{*} \rightarrow \mathbb{R}\)的张量为逆变张量，基的指标用上标表示，称\(V\times V \times ... \times V \rightarrow \mathbb{R}\)的张量为协变张量，基的指标用下标表示。

并且我们发现，全体\(\underbrace{ V^{*} \times V{^*} \times ... \times V^{*} }_m \times \underbrace{ V \times V \times ... \times V}_n \rightarrow \mathbb{R}\)的\((m,n)\)张量构成一个线性空间\(\mathcal{L}\)。我们自然想要知道这个线性空间的维度，以及基与各个协变基之间的关系。在寻找这个关系前，我们要定义张量积运算。

定义3：张量积\(\cdot\otimes\cdot\)是一个双线性函数：

\[ \forall \alpha \in V^{*}_1, \beta \in V^{*}_2, u \in V_1, v \in V_2; \alpha\otimes\beta(u,v)=\alpha(u)\beta(v) \]

上面的定义是对逆变矢量的，张量积对协变矢量依然成立。我们下面可以证明，\(e^{i_1}\otimes e^{i_2}\otimes ...\otimes e^{i_m} \otimes e_{j_1} \otimes e_{j_2} \otimes... \otimes e_{j_n}\)是\(\mathcal{L}\)的一组基。首先显然它们是属于\(\mathcal{L}\)空间的。因此我们只要证明\(\forall f \in \mathcal{L}\)都可以用它们线性表示。不失一般性，我们这里给出\((2,0)\)张量的证明，注意到\(\forall u\in V_1,v\in V_2\)：

\[ f(u,v)=f(u^ie_i,v^je_j)=e^i_1(u)e_2^j(v)f(e_{1i},e_{2j})=f(e_{1i},e_{2j})(e_1^i\otimes e_2^j)(u,v) \]

即\(f=f(e_{1i},e_{2j})(e_1^i\otimes e_2^j)(u,v)\)，我们仍然按照反证法，设存在\(k_{ij}\)使得\(k_{ij}(e_1^i\otimes e_2^j)=0\)，两边同时作用于\((e_{1r},e_{2s})\)有

\[ 0=k_{ij}(e_1^i\otimes e_2^j)(e_{1k},e_{2l})=k_{ij}e_1^ie_{1r}e_2^je_{2s}=k_{ij}\delta^i_r\delta^j_s=k_{rs} \]

这就证明了上面的命题。因此，张量积就是一种使用\(m\)维对偶空间和\(n\)维线性空间构造一个\((m,n)\)的多重线性映射的方法，因此张量还可以用张量积来进行定义，并且我们立刻可以得到推论：

推论1： \[ \mathcal{L}(m,n) = \underbrace{ V^{*} \otimes V^{*} \otimes ... \otimes V^{*} }_m \otimes \underbrace{ V \otimes V \otimes ... \otimes V}_n \]

群

在搞清楚了张量的定义和基本性质之后，我们要将目光转移到具有一些特殊性质的张量，例如张量的交换对称性。在给出对称性之前，我们需要回顾研究交换对称性的置换群。首先我们给出群的定义：

定义4：一个群\(G\)是一个定义了元素间乘法运算的集合，满足：

1. 封闭性：\(\forall g_1,g_2\in G, g_1\cdot g_2\in G\)
2. 结合律：\(\forall g,h, k\in G, g\cdot(h\cdot k)=(g\cdot h)\cdot k\)
3. 存在单位元：\(\exists e\in G, \forall g\in G, e\cdot g=g\cdot e=g\)
4. 存在逆：\(\forall g\in G, \exists h\in G, g\cdot h = h\cdot g=e\)

从定义中我们可以看出，一个群就是一类变换的集合，这个集合中有单位变换(什么都不做)，并且任何变换都存在对应的逆变换。

置换群

考虑一组序数\((1,2,...q)\)，我们定义置换操作为序数的一个排列\(\sigma=(\sigma_1,\sigma_2,...\sigma_q)\)到另一个排列的变换。显然，全体置换操作构成了一个群，我们称其为置换群，其中序数的数量\(q\)称为置换群的阶数。我们知道，对于一组序数来说，它的排列数量是\(q!\)，因此，一个\(q\)阶置换群的元素为\(q!\)个。

接下来我们定义置换的奇偶性，我们可以简单看出，一个置换\(\sigma\)可以分解为多个两序数对换操作的乘积之和，我们称分解个数奇数的为奇置换，偶数个数的为偶置换，换句话说，一个置换将序数排列\((1,2,...q)\)变换到\((\sigma_1,\sigma_2,...\sigma_q)\)，它分解为序数对换操作的数目就定义了其奇偶性。

定义5：

\[ \text{sign}(\sigma) = \begin{cases} -1 & \sigma \quad is \quad odd \\ 1 & \sigma \quad is \quad even \end{cases} \]

以上群论的知识已经足够覆盖本文内容。

对称张量和反对称张量

我们自然想看看一个张量\(T(u,v)\)，\(u\)和\(v\)的顺序替换之后和原来值的关系，使用置换群的语言，我们能够给出对称张量和反对称张量的定义。下面的张量性质不涉及基变换，因此不区分

定义6：定义\(G_q\)为\(q\)阶置换群，定义\(T\)为\(q\)阶张量，定义其对换元素为：\(\forall\sigma\in G_q,(\sigma T)(v_1,..v_q)=T(\sigma_1,...\sigma_q)\)。则:

• \(T\)是对称张量，当且仅当

\(\forall \sigma\in G_q, \sigma(f)=f\)。

• T是反对称张量，当且仅当

\(\forall \sigma\in G_q, \sigma(f)=\text{sign}(\sigma)f\)

显然，全体\(q\)阶对称张量构成一个线性空间，全体\(q\)阶反对称张量也构成一个线性空间，它们都是\(\mathcal{L}\)的子空间。

由于对称张量的性质是平凡的，这里我们来研究反对称张量的性质。我们记全体\(q\)阶反对称张量构成的线性空间为\(\Lambda^q\)。研究它，我们自然就想要知道它的维数，以及其基和相应线性空间中基的关系。

在得到这个关系前，我们首先要构造出将一个没有对称性的张量对称化或者反对称化的方法。一个好的动机就是观察置换的代数结构，我们注意到了一个\(k+l\)阶置换可以写成一个\(k\)阶置换和\(l\)阶置换的积，并且观察定义6，我们就可以得到答案。

定理2：\(f\)是\(q\)阶张量，\(f\in \mathcal{L}(q)\)，则：

1. \(Sf=\sum_{\sigma\in G_q}\sigma f\)是对称张量

2. \(Af=\sum_{\sigma\in G_q}\text{sign}(\sigma)\sigma f\)是反对称张量

证明：

对于2.\(\forall \tau \in G_q\) \[ \tau Af=\sum_{\sigma\in G_q}\text{sign}(\sigma)\tau(\sigma f)\\ =\sum_{\sigma\in G_q}\text{sign}(\sigma)(\tau\sigma) f \\ =\text{sign}(\tau)\sum_{\sigma\in G_q}[\text{sign}(\tau)\text{sign}(\sigma)](\tau\sigma) f\\ =\text{sign}(\tau)\sum_{\sigma\in G_q}\text{sign}(\tau\sigma)(\tau\sigma) f\\ =\text{sign}(\tau)Af \] 1的证明和上面一样，只需要把sign去掉。

现在我们可以利用这个构造方法得出\(\Lambda^q\)的性质了。首先，我们根据反对称张量的构造来定义两个张量的楔积：

定义7:一个\(k\)阶张量\(f\in\mathcal{L}(k)\)和一个\(l\)阶张量\(f\in\mathcal{L}(l)\)的楔积\((f\wedge g)\)构成一个\(k+l\)阶张量：

\[ f \wedge g (v_1,v_2,..v_{k+l}) =\frac{1}{k!l!} \sum_{\sigma\in G_{k+l}}\text{sign}(\sigma)f(\sigma_1,\sigma_2,...\sigma_k)g(\sigma_{k+1},\sigma_{k+2},...\sigma_{k+l}) \]

注意系数\(k!\)和\(l!\)的来源，它们分别是\(k\)阶置换群和\(l\)阶置换群群元的数目，这里相当于除以了求和符号中项数，因为我们不想要楔积的值随着项数的累计而变得巨大。显然，一个张量和常数的楔积就是定理2中的反对称形式除以系数，下面我们给出楔积的性质。

• 反交换率

\(\forall f\in\mathcal{L}(k)，\forall g\in\mathcal{L}(l)\Rightarrow f\wedge g=(-1)^{kl}g \wedge f\)

• 分配律

\(\forall f_1,f_2\in\mathcal{L}(k)，\forall g_1,g_2\in\mathcal{L}(l)\Rightarrow (f_1+f_2)\wedge g=f_1 \wedge g_1+f_2 \wedge g_1; f_1\wedge (g_1+g_2)=f_1\wedge g_1 + f_1\wedge g_2\)

• 结合律

\(\forall f\in\mathcal{L}(k), \forall g\in\mathcal{L}(l), \forall h\in\mathcal{L}(m)\Rightarrow f\wedge (g \wedge h) = (f \wedge g)\wedge h\)

由于篇幅原因，证明不予给出。

定义完了楔积，我们就可以尝试回答\(\Lambda^q\)的维数和基的问题了。首先，对于\(\forall\alpha,\beta\in\Lambda^q\)，有\(\alpha\wedge\beta=(-1)^{rs}\beta\alpha\)，这说明我们在取基的时候，楔积的顺序不是重要的，因为它们只差一个正负号，那么交换后的基和交换前的是可以相互线性表出的。然后，我们根据顺序无关的性质，就可以发现基数量就是组合数\(C_n^q\)，进一步，我们可以得到\(\Lambda^q\)的基为：

\[ \{e^{i_1} \otimes e^{i_2}... \otimes e^{i_q}\}\\ 1 \leqslant i_1 \leqslant i_2 \leqslant ... \leqslant i_q \leqslant n \]

当然上面的只是猜想思路

关于熵的一些随笔——从物理学到信息理论

在微观的角度，熵是描述一个系统混乱程度的量度，满足玻尔兹曼关系： \[ S=kln\Omega \] 其中Ω是一个系统的可能状态数目。从公式上看，熵只是微观状态可能数量的对数，和混乱程度不是很搭边。但在物理学的语境中，根据热力学第二定律，孤立系统的熵永不减少，也就意味着一个孤立系统在演化的过程中最终会达到一个平衡态，并且这个平衡态的熵是极大值。对应到微观下，就是在总能量与粒子数保持不变的情况下，处于平衡态时这个系统的粒子会处于这样的一个分布：这个分布会让系统中总的可能微观状态数目达到极大值： \[ δS=kδlnΩ=0 \] 当粒子总能量和数目保持不变，但在往平衡态进行演化的时候，可能的微观状态数却越来越多，那么这个系统“看起来”确实就越来越混乱了。

在认识到“混乱程度”和可能粒子数目的关系等价是基于孤立的热力学系统这一基础上，我们注意到了熵的玻尔兹曼关系只表示了系统的可能微观状态数，这里面并没有对系统本身进行任何假设，因此尽管熵最初来自于平衡态或者非平衡态到平衡态之间的准静态过程，但不管系统本身处于什么状况，我们总可以定义这个量度来表示它可能的微观状态数目。

至于为什么取对数，最直接的原因就是熵要满足广延量的需求。对于一个系统1，它可能的微观状态数目是\(Ω_1\)，对于系统2，它可能的微观状态数目是\(Ω_2\)，那么将系统1和系统2看作一个整体\(Ω\)，并且系统1和系统2的成员是互不相交的，我们很容易得出，合系统的可能微观状态数目为： \[ Ω=Ω1⋅Ω2 \] 当一个系统熵的定义和其可能的微观状态数是对数关系时，那么自然满足广延量需求了： \[ lnΩ=lnΩ1+lnΩ2⇒S=S1+S2 \] 并且，注意到对数的底取任意值是不影响到广延量性质时，我们便可以将熵和信息的表示关联起来了。对于一个长度为N的二进制数，其可能的状态数目为2N，假设我们定义它的熵为取2的对数，那么这个二进制数的熵正好就是N。也就是说，在信息理论中，熵又可以表示表示一条可能状态为\(Ω\)的信息需要的最小比特数。

现在我们利用熵来解答leetcode 458. 可怜的小猪：

有buckets桶液体，其中 正好 有一桶含有毒药，其余装的都是水。它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药，你可以喂一些猪喝，通过观察猪是否会死进行判断。不幸的是，你只有minutesToTest分钟时间来确定哪桶液体是有毒的。

喂猪的规则如下：

选择若干活猪进行喂养 可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。 小猪喝完水后，必须有minutesToDie分钟的冷却时间。在这段时间里，你只能观察，而不允许继续喂猪。 过了minutesToDie分钟后，所有喝到毒药的猪都会死去，其他所有猪都会活下来。 重复这一过程，直到时间用完。 给你桶的数目buckets,minutesToDie 和minutesToTest，返回在规定时间内判断哪个桶有毒所需的最小猪数。

buckets桶液体，只有1桶有毒，那么总共有buckets种可能，表示这条信息需要的熵为

log(buckets)

一头小猪死亡后，死亡的原因只能是它所喝的n次水中有一次有毒，一共n种可能。根据题设，小猪最多能喝\([\frac{minutesToDie}{minutesToTest}]+1\)次水，那么小猪能提供的信息熵就是 \[ log([\frac{minutesToDie}{minutesToTest}]+1) \]

我们要用n头猪来得到哪个桶有毒，根据熵的广延性，这n头猪能得到的信息熵为 \[ S=nlog([\frac{minutesToDie}{minutesToTest}]+1) \]

既然熵的意义是表示一条信息所需要的最小比特数，那么要用这几头猪的信息得到有毒桶的信息，猪的熵必须大于等于桶的，因此： \[ n=ceil(\frac{log(buckets)}{log([\frac{minutesToDie}{minutesToTest}]+1)}) \]

code如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
public:
    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        if(buckets == 1) return 0; 
        return ceil((entropy(buckets)/entropy((int)(minutesToTest/minutesToDie)+1)));
    }

    float entropy(int info){
        if(info == 1){
            return 1;
        }
        return log(info);
    }
};

简易内核实现笔记(二)——内存寻址与安全机制

前面叙述了x86架构的CPU在加电后是怎么一步步把内核加载到内存中去运行的，但有的东西说的比较仓促，在这里会结合硬件讲述x86架构的CPU是如何与软件结合进行内存寻址的，并且在保护模式下为内存寻址提供了哪些最基本的安全机制，有的内容会和笔记（一）重复。

内存寻址

在x86 CPU的硬件支持下，保护模式的寻址(假如分页已经打开)是如下的过程：

1

逻辑地址 --分段机制--> 线性地址 --分页机制--> 物理地址

可用看到就是分段与分页机制共同作用的结果。在x86架构的CPU下，分页并不是一个必要的过程，但在将控制寄存器CR0的第31位写为1开启分页模式后，分页机制就会帮助CPU实现虚拟地址空间的寻址，这样的一层抽象能够让各个进程处于好像是自己霸占了所有的内存资源一样，简化了软件对内存的访问与使用，因此linux是使用了虚拟地址空间的。但分段是x86 CPU强加的，这个下面会详细介绍。

分段机制

x86 CPU为段机制的实现提供了专门的寄存器：CS，DS，SS，ES，FS，GS。其中前三个看缩写也明白，分别对应了代码段(code segment)，数据段(data segment)，栈段(stack segment)。后面三个寄存器的用途x86 CPU在硬件实现上没有强加，因此功能是软件定义的，暂且不聊。我们先说前三个寄存器。

所谓的段(segment)，还是得从硬件的角度去理解。CPU通过总线连接了其他硬件设备，并通过总线与它们实现交互，而总线又可以分为三类：地址线，数据线，控制线。本质上说，所有的计算机信息都是二进制0和1，CPU也只认识0和1，不认识什么是代码，什么是数据，什么是地址，对于两个完全相同的01序列，CPU可用有不同的解释：

1
2

1000100111011000 -> 89DH      (数据)
1000100111011000 -> mov ax,bx (代码)

CPU是通过什么机制将一些01序列视为数据，另一些01序列视为代码的呢？答案就是看它们通过什么样的线，通过数据线的就是数据，通过地址线的就是地址，通过控制线的就是指令。自然地，为了在硬件上帮助这个机制实现地更彻底一点，那就创造一种分段的机制，把内存地址空间中的01序列分成一段一段的，如果在数据段中，那这段内存中的01序列CPU就把它当成数据，处于栈段中的，CPU就把它当成栈，处于代码段中的，CPU就把它当成代码。

于是x86 CPU就专门设置了三个寄存器实现分段，CS存储的就是代码段的段基址，DS存储的就是数据段的段基址，SS存储的就是栈段的段基址，然后我们再给它们配套一个寄存器用来存储段的偏移地址，那么CPU只要用段基址:偏移地址的形式就能得到对应段的物理地址，于是就将代码，数据，栈在形式上分了开来，程序就能有条理地被执行了。

8086分段机制

由于8086在硬件架构上是有20位的地址线，也就是寻址上是1MB的内存空间，但寄存器只有16位，为了能够实现20位的寻址模式，分段机制就采用物理地址=段基址*16+偏移地址的方式来凑出20位地址。这里就可用看出分段机制不仅仅是为了将代码，数据和栈分离开，它也是8086 CPU实现20位寻址的必要机制，所以在分段上x86 家族的CPU从8086开始就深入骨髓中了。8086的运行模式在新一代的x86 CPU中也称之为实模式，所有x86家族CPU加电的瞬间都是在实模式下运行，目的就是做到向下兼容。

保护模式分段机制

在保护模式下，除了段寄存器之外，其余寄存器都扩展到了32位（IA32架构），那么寻址空间就从1MB变成了32位4GB，并且理论上只需要提供偏移地址的32位寄存器就可以独立完成32位的寻址，因此在保护模式下，分段机制的作用只剩下了将代码，数据和栈进行分离了。并且保护模式下硬件将与软件一起实现分段机制。

全局描述符表

抛砖引玉，我们先考虑这个问题：既然保护模式下，32位寄存器已经能在理论上脱离段寄存器独立寻址，那么段寄存器在保护模式下的意义除了向下兼容8086实模式以外还有什么？没错，答案就是为描述符表而存在！保护模式下的段寄存器存储的东西不再称为“段基址”，而是“段选择子”(selector)，而这个选择的目标就是对应的段描述符。段选择子的16位二进制结构对应的意义如下：

1
2

|15|      ...   | 3| 2| 1| 0|
|       index      |TI| RPL |

1-0位是请求特权级，这个后面详细说。第2位是表指示符，用于指代后面的指标indexing的是GDT还是LDT，后13位就是段描述符表的index了，从长度来看总共可以索引8192个段描述符。

描述符表分为两种，一个是全局描述符表GDT，另外一个是局部描述符表LDT，GDT是被所有进程共享的，LDT是单个进程独有的，由于linux kernel在2.4之后并不使用LDT，这里就略过了，但它们都是一样的东西，唯一区别只是公用和私用而已。

所谓的全局描述符表就是一个位于内存中的描述符的数组，它的首位地址就是第一个描述符地址，一个描述符大小为8字节64位，每一位分别对应的意义如下：

可以看到这里面是有段基址的，所以保护模式的分段实际过程就是段寄存器通过存储全局描述符表基址的寄存器GDT再加上index*8寻址到对应的段描述符，然后取出对应的段基址再加上偏移地址就可以了。

绕了大半天，其实就是为了让寻址时加上额外的一些段信息，它们意义如下，由于一些向下兼容的原因，一些东西是不连续的，但不妨碍我们理解：

• 段界限：一个段的最大大小是20位，如果索引超过段界限CPU会触发异常。
• G：段界限的粒度，如果G为0就代表粒度是1位，对应到段界限就是20位1MB。G为1就代表粒度为4KB，对应到段界限就是4GB，因此实际的段界限大小等=粒度大小*段界限-1
• 段基址：顾名思义，不用说了
• D/B：一个用来兼容80286保护模式的位，表示有效地址和操作数的位数。D为0表示16位，D为1表示32位（所以对我们不用80286的就没什么用）
• L：为1表示64位代码段，0表示32位
• AVL：available字段，这个available是对于用户来说的，不是硬件，所以是可以随便用的
• P：用于指示段是否存在于内存中，用到这个段时如果它不存在，就会触发CPU的异常，然后跳转到异常处理程序中把它加载到内存中。
• DPL：Descriptor Privilege Level，表示描述符的特权级。
• S：为1表示系统段，0表示非系统段
• type：段的类型，这三位对于系统段和非系统段有不同的定义：

这些信息提供了保护模式下的安全机制，这个后面再说。BTW linux kernel认为段基址是没有意义的，因为偏移地址已经可以给出完整的线性地址，因此linux kernel的全局描述符表中的段基址位全都置为了0用以规避分段机制，因此在linux下偏移地址就等于线性地址。因此GDT对于linux存在的唯一意义就是实现内存访问的安全机制了。

分页机制

分页机制实际上就是将线性地址看作了虚拟地址，通过页表实现了虚拟地址到物理地址的映射，由于笔记(一)已经详细讲述，这里就直接复制粘贴了：

虚拟地址空间

在进入保护模式之后，我们所访问的32位地址仍然是物理地址，虚拟地址为我们提供了一层抽象，使得每个进程都可以在32位地址空间中运行，我们只需要通过页表将它们映射到物理地址即可，这样写程序就不用再自己去管地址从哪里开始了。

页表

页表是虚拟地址与物理地址的映射关系，由于将来每个操作系统下的进程，包括操作系统自己都是在32位虚拟地址空间中运行的，因此每个进程都需要有自己的页表，我们将物理地址分页，每个页占有4kB的大小，一个页表项就占32位4字节，检索4GB的虚拟内存空间总共需要1M个页表，在内存中占4MB，这个大小显然是无法接受的，因此我们再创建一个页表的页表，也就是页目录表，一个页目录项也是32位4字节，因此一个页目录项也可以索引4kB的空间，那么检索4GB的虚拟地址空间只需要4GB/4kB/4kB=1024个页目录，只需要4096个字节就可以了，这样的开销就可以接受。

对于1024个页目录，我们需要10位地址来进行索引，这10位地址就是虚拟地址中的高10位，我们将这10位地址4就是对应页表的偏移地址，再加上页目录表的起始地址就得到了对应页表所在的物理地址，一个页表中有1024个页，因此检索它也需要10位地址，这10位地址就是虚拟地址中的中间10位，我们用这中间10位地址4就得到了所在页的偏移地址，加上前面得到的页表物理地址就得到了对应页所在物理地址，这个页中存储的就是真实物理地址的偏移量，再加上最低12位虚拟地址就得到了对应的真实物理地址了。

因为每个页表项都是4字节，因此它们的值里面低12位全是0，因此为了避免浪费就要往里面加一些关于页表的安全信息：

其中：

• P：该页存在于物理地址中
• R/W：读写权限，0表示只读，1表示可读可写
• US：普通用户/超级用户位，为1表示在普通用户级，普通用户在特权级3
• PWT：通写位，1表示处于通写模式，表示改该页是高速缓存
• PCD：打开使用高速缓存
• A:访问位，如果CPU访问过该页，就会把它置为1，之后的操作系统我们会将它置为0，通过count置为1的次数就能判断它是否常常被使用，是就将这个页存入缓存中
• D：脏页位，CPU对一个页进行写操作时，就会把这个位置为1，仅对页表项有效
• G：global位，若为global，那么这个页表就会一直在高速缓存TLB中保存
• AVL：软件的可用为，CPU不会管，怎么用就是软件定义的了

内存的安全机制

访问特权级

除了页表项以及段描述符中的那些索引界限以及读写权限的设置以外，x86 CPU保护模式还设计了特权级来为操作系统提供安全支持。特权级从0-3一共4级，0级最高，也是操作系统内核的特权级，3级最低，是普通用户的特权级，对于linux来说，只用到了特权级0和3，因此0级特权下又称为内核态，3级特权下又称为用户态。CPU对内核态完全信任，也就是操作系统内核对硬件资源拥有完全的访问权限，低级特权无法访问被指定了高级特权能访问的硬件资源，也就是用户态的进程无法直接访问操作系统的内存空间以及代码，只能通过中断陷入内核，然后调用内核的异常处理程序来向内核请求服务，这样就保证了操作系统基本的安全。

那么这种机制是如何实现的呢？首先就是在段寄存器中储存的段选择子上，选择子的第1-0位上就是请求特权级，编码上的00，01，10，11就对应了0，1，2，3这四级特权级。对于栈段和数据段来说，这个特权级就代表了请求访问它们对应的段所需要的最小特权级，而对于代码段来说，这个特权级就代表了这段代码执行的特权级，因此代码段的RPL叫CPL(current privilege level)，也就是当前指令的特权级。前面说描述符的时候有提到，描述符里也有它自己的特权级DPL，因此DPL也在安全特权检查之列。

在CS:EIP指向了内存中的一个指令地址的时候，如果不考虑特权级转换，CPU会做的完整步骤如下：

• 首先根据CS的index检索到对应代码段的段描述符，得到描述符的DPL，然后用CS的CPL比较，如果CPL>DPL，则报保护错(数字越小特权越高)
• CPL大于等于代码段描述符DPL，则通过描述符提供的段基址+EIP的偏移地址得到指令的线性虚拟地址，然后通过页表缓存或页表查询到物理地址，取指令执行
• 指令执行时会如果访问到相应的数据段或者栈段，则对应段选择则先indexing到对应的段描述符，然后检查保证CPL或者访问段选择子的RPL有一个小于等于该段描述符的DPL，如果max{CPL,RPL}>DPL，则报保护错
• 检查通过，然后访问相应资源，指令执行完毕后加载下一条指令跳回第一步

特权级的提升与降低

CPU还要考虑陷入内核态后上下文的保存问题，进程触发异常后会陷入内核态，然后内核调用相应的异常处理程序，此时特权级就从3提升到0，在执行完内核代码之后（如果不是终止异常）又返回用户态。那么一个进程从3跳到0的过程要有4组栈寄存器来对应每个特权级的栈段和栈底。32位机器下4GB的寻址空间中最高位的1GB是内核才能访问的，这里面就有内核使用的栈段，肯定要和用户用的低3GB地址下的栈段区分，并且在进程陷入内核态之时，用户态的上下文信息肯定要保存下来，等待内核代码做完事情以后恢复现场。实现的方法就是一个叫TSS(task state segment)的数据结构：

可以看到TSS只能保留3组栈，因为用户态本来就是最低权限，已经降不下去了，，而且汇编指令的int,call会将用户态的栈保存，TSS就只用记录0，1，2这三个特权级的栈寄存器就OK。每个进程都有自己的TSS，并且x86 CPU会有专门的寄存器TR(task register)来保存它的地址，当用户态的进程陷入内核态时，除了SS，ESP以外的上下文信息就会被保存，然后使用0级特权栈配合CRL为0的内核代码完成相应异常处理程序，最后再恢复现场，把特权级降回用户态就完事了。

降低特权级可以通过恢复进程上下文实现，但还得考虑怎么提升特权级的问题。CPU又提供了一组和硬件支持的数据结构来实现，这种数据结构称为‘门’。一共四种，任务门，中断门，陷阱门和调用门：

门也是一种描述符，只不过和全局描述符表中的描述符不一样的是，全局描述符表是记录数据的描述符，而门中除了任务门以外记录的是一段历程地址的描述符，用于支持内核的系统调用：

• call和jmp指令的选择子会成为调用门的参数，指令CPL通过调用门的DPL特权检查后call会以调用高CPL函数例程形式实现特权级提升，jmp只能转移到CPL平行的代码上。
• int指令会触发中断，指令CPL通过中断门的DPL特权检查后，linux并根据中断类型调用相应的异常处理程序，然后以中断形式进入内核态实现特权提升。
• int3指令通过触发中断形式在陷阱门中实现特权提升，一般是编译器调试用，不用管
• 任务(进程)在中断发生后如果中断向量号是任务门，则通过任务门以TSS为单位实现任务切换，不过linux并没有使用这样的硬件机制，所以不用管

综上，一个指令在执行的时候，它的CPL必须满足以下条件：

• 访问门（向内核请求服务）：CPL≤DPL(gate) and CPL≥DPL(seg)
• 访问段：max{CPL,RPL}≤DPL

这就是特权在保护模式下提供的安全机制，可见这些安全机制一部分是由硬件实现，一部分是由操作系统内核实现的。