封面图来自pixiv illustration collection(带你们打开新世界的大门)这个习题是最难的一次，看好了(1.按通常的做法使用Chernoff界就可以： P(X\geq i)\leq\mathrm e^{-it}(p\mathrm e^t+1-p)^n 。使用求导方法算出右边关于 t 的函数的最小值就可以得到要证的结论。不过想要展示真正的技术的话也可以使用不等式：\mathrm e^{-it}(p\mathrm e^t+1-p)^n=\left( p\mathrm e^{\frac{n-i}{n}t}+(1-p)\mathrm e^{-\frac{i}{n}t} \right)^n ，而由平均值不等式\begin{align} p\mathrm e^{\frac{n-i}{n}t}+(1-p)\mathrm e^{-\frac{i}{n}t}&=i\cdot\frac{p\mathrm e^{\frac{n-i}{n}t}}{i}+(n-i)\cdot\frac{(1-p)\mathrm e^{-\frac{i}{n}t}}{n-i}\\
&\geq n\sqrt[n]{\left( \frac{p\mathrm e^{\frac{n-i}{n}t}}{i} \right)^i\left( \frac{(1-p)\mathrm e^{-\frac{i}{n}t}}{n-i} \right)^{n-i}}\\ &=n\sqrt[n]{\frac{p^i(1-p)^{n-i}}{i^i(n-i)^{n-i}}} \end{align} 就得到答案。2.回忆一下二元函数的Taylor公式，证明就很明显了。3.用全概率公式计算 P(X>65) 。志愿者医生数量为 i 时接诊数为参数为 30i 的Poisson随机变量，分别用中心极限定理计算三种情况下的概率，然后代入全概率公式。4.(1)用定义，如果 \bigcup_{k=1}^{n}A_k 成立，则至少有一个
S_k|\geq x ，从而 \max_{1\leq j\leq n}\left|S_j\right|\geq x 。反过来，设 \max_{1\leq j\leq n}\left|S_j\right|\geq x ，则存在一个最小的 k 使得
S_k|\geq x ，这时 A_k 成立。(2)用Markov不等式：P(A_k)=P(S_k^2I_k\leq x^2)\leq\frac{E[S_k^2I_k]}{x^2} ，或者用条件期望。(3)记 \overline{S_k}=S_n-S_k 。由(1)(2)得(注意 A_k 不相容)\begin{align} P\left( \max_{1\leq j\leq n}|S_j|\geq x \right) &=\sum_{k=1}^nP(A_k)\\ &\leq\frac{1}{x^2}E\left[ \sum_{k=1}^nS_k^2I_k \right]\\ &=\frac{1}{x^2}E\left[ \sum_{k=1}^n(S_n^2I_k-2S_k\overline {S_k}I_k-\overline {S_k}^2I_k) \right]\\ &\leq\frac{1}{x^2}E\left[ S_n^2\sum_{k=1}^nI_k \right](S_k,\overline{S_k}独立)\\ &\leq\frac{\mathrm{Var}(S_n)}{x^2}\left( \sum_{k=1}^nI_k\leq 1,E[S_n]=0 \right)\\ \end{align}其中有一步代数运算是这样做的：S_k^2=(S_n-\overline{S_k})S_k=(S_n+\overline{S_k}-2\overline{S_k})S_k=S_n^2-\overline{S_k}^2-2\overline{S_k}S_k 。5.(1) \mathrm e^{tx} 是一个关于 x 的凸函数。(2)对(1)中的式子，令 x=X 并取期望得 M(t)\leq\frac{b}{b-a}\mathrm e^{ta}-\frac{a}{b-a}\mathrm e^{tb} 。令 h=t(b-a),p=-\frac{a}{b-a} ，并对右边取对数(所得记为 L(h) )则L(h)=-hp+\ln(1-p+p\mathrm e^h) 。我们只需证明 L(h)\leq\frac{1}{8}h^2 ，而这可以靠Taylor公式实现： L(0)=L'(0)=0,L''(h)\leq\frac{1}4 。(3)用Chernoff界的推论。设 X_i 的矩母函数为 M_i(s) 。则\begin{align} P(S_n-E[S_n]\geq t)&\leq\mathrm e^{-st}\prod_{i=1}^nM_i(s)\\ &\leq\exp\left( \frac18\sum_{i=1}^n(b_i-a_i)^2s^2-st \right)\\ &=\exp\left( \frac18\sum_{i=1}^n(b_i-a_i)^2\left( s-\frac{4t}{\displaystyle\sum_{i=1}^n(b_i-a_i)^2} \right)^2-\frac{2t^2}{\displaystyle\sum_{i=1}^n(b_i-a_i)^2} \right)\\ \end{align}
取 s=\frac{4t}{\displaystyle\sum_{i=1}^n(b_i-a_i)^2} 就得到结果。6.令 N>k 。设 A_i 表示事件 \left\{ (t_i+a)^2\leq (X-\mu+a)^2< (t_{i+1}+a)^2 \right\} ，示性变量为 I_i 。则有\begin{align} \sum_{i=1}^N P(X-\mu\geq i)&=\sum_{i=1}^NiP(t_i\leq X-\mu< t_{i+1})\\ &\leq\sum_{i=1}^NiP((t_i+a)^2\leq (X-\mu+a)^2< (t_{i+1}+a)^2)\\ &=\sum_{i=1}^NiP(A_i)\\ &=\sum_{i=1}^NiP((X-\mu+a)^2I_i\geq(t_i+a)^2)\\ &\leq\sum_{i=1}^N\frac{i}{(i+a)^2}\cdot E[(X-\mu+a)^2I_i]\\ &\leq\max_{1\leq i\leq N}\frac{i}{(i+a)^2}E[(X-\mu+a)^2]\\ &=\max_{1\leq i\leq N}\frac{i}{(i+a)^2}\cdot(\sigma^2+a^2) \end{align}其中第五行用到Markov不等式。然后只需要求出右边关于 a 的函数的最小值。这并不太容易，需要先证明当\sqrt{k(k-1)}\leq a\leq \sqrt{k(k+1)} 时，上式的 \max 在 i=k 取到。7.回忆极限的定义： X_n\to X 表示对任意 \varepsilon>0 ，当 n 充分大时
X_n-X|\leq \varepsilon 。这可以用事件 \bigcup_{n=1}^{\infty}\bigcap_{i=n}^{\infty}\left\{
X_i-X|\leq \varepsilon \right\} 成立表示。(假设 n>N 时
X_n-X|\leq \varepsilon ，则 \bigcap_{i=N+1}^{\infty}\left\{
X_i-X|\leq \varepsilon \right\} 成立。反之亦然)故 X_n 几乎必然收敛于 X 等价于\begin{align} &P\left(\bigcap_{\varepsilon>0}\bigcup_{n=1}^{\infty}\bigcap_{i=n}^{\infty}\left\{
X_i-X|\leq \varepsilon \right\}\right)=1\\ &\Leftrightarrow P\left(\bigcup_{\varepsilon>0}\bigcap_{n=1}^{\infty}\bigcup_{i=n}^{\infty}\left\{
X_i-X|\leq \varepsilon \right\}\right)=0\\ &\Leftrightarrow P\left( \bigcap_{n=1}^{\infty}\bigcup_{i=n}^{\infty}\left\{
X_i-X|\leq \varepsilon \right\} \right)=0,\forall \varepsilon>0\\ &\Leftrightarrow P\left(\limsup_{n\to\infty} \left \{
X_n-X|\geq \epsilon \right \}\right)=0,\forall \epsilon>0 \end{align} 8.直接用期望的定义来估计。取小的 \delta,\varepsilon>0 ，可以断言当 n 充分大时 P(|X_n-c|>\varepsilon)<\delta 。取一个比 \varepsilon 稍大一点点的 \epsilon (比如取一个小的 \phi ， \epsilon=(1+\phi)\varepsilon )，则\begin{align} \delta&>P(|X_n-c|>\varepsilon)\\ &=P(X_n>c+\varepsilon)+P(X_n<c-\varepsilon)\\ &\geq P(X_n>c+\varepsilon)+P(X_n\leq c-\epsilon)\\ &=F_n(c-\epsilon)+1-F_n(c+\varepsilon) \end{align} 其中 F_n 为 X_n 的分布函数。然后，对于充分小的 \varepsilon ，由连续性，当 x\in[c-\epsilon,c+\varepsilon] 时有
g(x)-g(c)|<\theta ， \theta 充分小。我们估计式子 E[g(X_n)]-g(c)\int_{c-\epsilon}^{c+\varepsilon}\mathrm dF_n(x) 。注意到 g 的有界性，有
g(x)|<M 。事实上\begin{align} &\left|E[g(X_n)]-g(c)\int_{c-\epsilon}^{c+\varepsilon}\mathrm dF_n(x)\right|\\ &=\int_{c-\epsilon}^{c+\varepsilon}|g(x)-g(c)|\mathrm dF_n(x)+\left( \int_{-\infty}^{c-\epsilon}+\int_{c+\varepsilon}^{+\infty} \right)|g(x)|\mathrm dF_n(x)\\ &< \int_{c-\epsilon}^{c+\varepsilon}\theta\mathrm dF_n(x)+\left( \int_{-\infty}^{c-\epsilon}+\int_{c+\varepsilon}^{+\infty} \right)M\mathrm dF_n(x)\\ &\leq \theta+M(F_n(c-\epsilon)+1-F_n(c+\varepsilon))\\ &<\theta+M\delta \end{align} 这可以充分小。注意到 \int_{c-\epsilon}^{c+\varepsilon}\mathrm dF_n(x)=-F_n(c-\epsilon)+F_n(c+\varepsilon)>1-\delta ，命题得证。9.设随机变量 \xi_1,\cdots,\xi_n 为独立同分布的Bernoulli随机变量，每一个的期望都为 x 。则可以证明： f_n(x)=E\left[ f\left( \frac{1}{n}\sum_{i=1}^n\xi_i \right) \right] 。(1)由于 f(x) 在 [0,1] 上连续，故有界。由弱大数定律得：对任何 \varepsilon>0，有\lim_{n \rightarrow \infty}{P\left( \left|\frac{1}{n}\sum_{i=1}^n\xi_i-x\right|> \varepsilon \right)}=0 。再由第8题就证得结论。(2)只须证明\lim\limits_{n\to\infty}\sup\limits_{x\in[0,1]}|f_n(x)-f(x)|=0 。由于 f(x) 在 [0,1] 上连续，故有界 M ，且在 [0,1] 上一致连续(Cantor定理)，即 \forall\varepsilon>0,\exists\delta>0,\forall x,y\in[0,1],|x-y|<\delta\Rightarrow|f(x)-f(y)|<\varepsilon 。由于
x
是凸函数，有 E[|X|]\geq
E[X]
。结合Chebyshev不等式：对 \forall x\in[0,1]
\begin{aligned}
f_n(x)-f(x)
=&\left|E\left[f\left(\dfrac{1}{n}\sum\limits_{i=1}^n\xi_i\right)\right]-f(x)\right
\\
\leq&\left|E\left[f\left(\dfrac{1}{n}\sum\limits_{i=1}^n\xi_i\right)-f(x)\right]
I_{\left[\left|\frac{1}{n}\sum\limits_{i=1}^n\xi_i-x\right|\geq\delta\right]}\right
\\
&+
\left|E\left[f\left(\dfrac{1}{n}\sum\limits_{i=1}^n\xi_i\right)-f(x)\right]
I_{\left[\left|\frac{1}{n}\sum\limits_{i=1}^n\xi_i-x\right|<\delta\right]}\right
\\
\leq&2M\cdot E\left[I_{\left[\left|\frac{1}{n}\sum\limits_{i=1}^n\xi_i-x\right|\geq\delta\right]}\right]
+\varepsilon
\\
=&2M\cdot P\left(\left|\dfrac{1}{n}\sum\limits_{i=1}^n\xi_i-x\right|\geq\delta\right)+\varepsilon\\
\leq&2M\dfrac{1}{n\delta^2}\mathrm{Var}(\xi_i)+\varepsilon \\
=&2M\cdot \dfrac{1}{n\delta^2}x(1-x)+\varepsilon \\
\leq& \dfrac{M}{2n\delta^2}+\varepsilon.
\end{aligned} 取个极限就得到 \lim\limits_{n\to\infty}\sup\limits_{x\in[0,1]}|f_n(x)-f(x)|=0
。10.令 S_n=\sum_{k=1}^n(X_k-E[X_k]) 。原来的问题等价于 S_n-S_m 几乎必然收敛于零，由7也就是 \forall \varepsilon>0,P\left( \bigcap_{k=1}^{\infty}\bigcup_{m,n=k}^\infty\left\{
S_n-S_m|\geq \varepsilon \right\} \right)=0 。由概率的连续性这等价于\begin{align} &\forall \varepsilon>0,\lim_{k\rightarrow \infty}P\left( \bigcup_{m,n=k}^\infty\left\{
S_n-S_m|\geq \varepsilon \right\} \right)=0\\&\Leftrightarrow\forall \varepsilon>0,\lim_{k\rightarrow \infty}P\left( \bigcup_{l=1}^\infty\left\{
S_{l+k}-S_k|\geq \varepsilon \right\} \right)=0 \end{align} 对某个 k ，有\begin{align} &P\left( \bigcup_{l=1}^\infty\left\{
S_{l+k}-S_k|\geq \varepsilon \right\} \right)\\ &\ \ \ \ =\lim_{t \rightarrow \infty}{P\left( \bigcup_{l=1}^t\left\{
S_{l+k}-S_k|\geq \varepsilon \right\} \right)}\\ &\ \ \ \ =\lim_{t \rightarrow \infty}{P\left( \max_{1\leq l\leq t}\left\{
S_{l+k}-S_k|\geq \varepsilon \right\} \right)}\\ &\ \ \ \ \leq\lim_{t \rightarrow \infty}\frac{1}{\varepsilon^2}\mathrm{Var}(S_{t+k}-S_k)\\ &\ \ \ \ =\frac{1}{\varepsilon^2}\lim_{t \rightarrow \infty}\sum_{i=k+1}^{k+t}\mathrm{Var}(X_i)\\ &\ \ \ \ =\frac{1}{\varepsilon^2}\sum_{i=k+1}^{\infty}\mathrm{Var}(X_i)\\ \end{align} 其中用到Kolmogorov不等式(第4题)。由级数的Cauchy收敛准则知上式在 k\to\infty 时趋于零。11.懒得写了...直接看之前写的参见的网站吧(才不是不会做呢第九章
概率论的其他课题这一章就是对概率论后面的各种发展方向做一个简单的介绍。教材提到了三个方面：Poisson过程，Markov链以及信息论。下面一一地简要介绍一下。(第十章不会写，因为我不太想学...)Poisson过程我们之前接触过Poisson过程，这里会用另一条途径来研究它。一个随机过程是指一组(随某参数而变的)随机变量。比如，时间轴上区间 [0,t] 内发生某种事件的个数为 N(t) ，则 \left\{ N(t):t\geq 0 \right\} 就是一个随机过程。上面所述的随机过程叫做具有强度 \lambda>0 的Poisson过程，如果：(1) N(0)=0 ；(2)在不相交的时间段上发生多少事件相互独立；(3)对任意 N(s+t)-N(t) 与 t 无关(即发生事件数只与时间区间长度有关)；(4) P(N(h)=1)=\lambda h+o(h) ；(5) P(N(h)\geq 2)=o(h) 。由定义，显然 N(t) 是不减的。我们先证明：对于强度为 \lambda 的Poisson过程， P(N(t)=0)=\mathrm e^{-\lambda t} 。记 P_0(t)=P(N(t)=0) ，则\begin{align} P_0(t+h)&=P(N(t+h)=0)\\ &=P(N(t)=0\ \wedge\ N(t+h)-N(t)=0)\\ &=P(N(t)=0)P(N(t+h)-N(t)=0)\\ &=P_0(t)(1-\lambda h+o(h)) \end{align} 其中用到条件(2)(4)(5)。故 \frac{P_0(t+h)-P_0(t)}{h}=-\lambda P_0(t)+\frac{o(h)}{h} 。令 h\to0 得P_0'(t)=-\lambda P_0(t)\\ 这玩意是一个微分方程，结合 P_0(0)=1 可以解出 P_0(t)=\mathrm e^{-\lambda t} 。下面设 T_i 为第 i-1 个事件与第 i 个事件的时间间隔。(第 0 个事件视为开始时间)我们来探求一下 T_i 的分布。序列 T_n 相互独立，且都服从期望为 \frac{1}{\lambda} 的指数分布。注意到由(2)我们只要证明相邻时间段的独立性。 n=1 时我们有 P(T_1>t)=P(N(t)=0)=\mathrm e^{-\lambda t} 。故这是一个指数分布，期望为 \frac{1}{\lambda} 。一般情况下由全期望公式P(T_{n+1}>t)=E[I_\left\{ T_{n+1}>t \right\}]=E[E[I_\left\{ T_{n+1}>t \right\}|T_n]] 。而\begin{align} E[I_\left\{ T_{n+1}>t \right\}|T_n=s]&=P(T_{n+1}>t|T_n=s)\\ &=P(N(t+s)-N(s)=0|T_n=s)\\ &=P(N(t)=0)=\mathrm e^{-\lambda t} \end{align} 故 P(T_{n+1}>t)=\mathrm e^{-\lambda t} ，且 P(T_{n+1}>t|T_n=s)=P(T_{n+1}>t) 。故 T_{n+1} 与 T_n 独立且服从期望为 \frac{1}{\lambda} 的指数分布。最后我们再导出之前得到过的结论。对于强度为 \lambda 的Poisson过程， N(t) 是一个参数为 \lambda t 的Poisson随机变量。设 S_n=\sum_{i=1}^nT_i 。之前证明过Gamma分布的可加性，所以 S_n 服从参数为 (n,\lambda) 的Gamma分布，其概率密度为 f_n(x)=\frac{\lambda\mathrm e^{-\lambda x}(\lambda x)^{n}}{n!} 。则\begin{align} P(N(t)=n)&=P(N(t)\geq n)-P(N(t)\geq n+1)\\ &=P(S_n\leq t)-P(S_{n+1}\leq t)\\ &=\int_0^t\left( \frac{\lambda\mathrm e^{-\lambda x}(\lambda x)^{n-1}}{(n-1)!}-\frac{\lambda\mathrm e^{-\lambda x}(\lambda x)^{n}}{n!} \right)\mathrm dx \end{align} 注意到 \int\frac{\lambda\mathrm e^{-\lambda x}(\lambda x)^{n}}{n!}\mathrm dx=-\int\frac{(\lambda x)^{n}}{n!}\mathrm d\mathrm e^{-\lambda x}=-\frac{\mathrm e^{-\lambda x}(\lambda x)^{n}}{n!}+\int\frac{\lambda\mathrm e^{-\lambda x}(\lambda x)^{n-1}}{(n-1)!}\mathrm dx 有 P(N(t)=n)=\frac{\mathrm e^{-\lambda t}(\lambda t)^{n}}{n!} 。也就是 N(t) 是一个参数为 \lambda t 的Poisson随机变量。Example 1
设 N_1(t),N_2(t) 为两个相互独立的Poisson过程，强度分别为 \lambda_1,\lambda_2 。设 X,Y 分别为两个过程的第一个事件发生的时刻，求 P(X<Y) 。首先，之前已经证明 X,Y 都服从指数分布，参数分别为 \lambda_1,\lambda_2 。由全期望公式： P(X<Y)=E[I_\left\{ X<Y \right\}]=E[E[I_\left\{ X<Y \right\}|Y]] 。而由独立性 E[I_\left\{ X<Y \right\}|Y=y]=P(X<y|Y=y)=P(X<y)=1-\mathrm e^{-\lambda_1 y} ，故有 E[I_\left\{ X<Y \right\}|Y]=1-\mathrm e^{-\lambda_1 Y} 。从而 P(X<Y)=1-E[\mathrm e^{-\lambda_1 Y}] 。注意到指数分布的矩母函数，有 E[\mathrm e^{-\lambda_1 Y}]=\frac{\lambda_2}{\lambda_1+\lambda_2} 。(参数为 \lambda 的指数分布，其矩母函数为 M(t)=\frac{\lambda}{\lambda-t} )故 P(X<Y)=\frac{\lambda_1}{\lambda_1+\lambda_2} 。Markov链Markov链通俗说来就是一个变量，如果它在时刻 n 为 i ，那么在时刻 n+1 为 j 的概率对于 n 而言是固定的。它们被称为转移概率。你可以把它画成图：在画一些圆圈在里面写可能取值，外面画一些箭头，上面写转移概率。比如这样：直观表述说完了，现在表述严格定义。考虑一系列随机变量 X_0,\cdots,X_n,\cdots ，取值为 \left\{ 0,1,\cdots,M \right\} (可以理解为不同状态的代号)，满足对于任意的 i,j ，存在一个属于 [0,1] 的数 P_{ij} 使得P(X_{n+1}=j|X_n=i,X_{n-1}=i_{n-1},\cdots,X_0=i_0)=P_{ij},\forall i_0,\cdots,i_{n-1} ，则这一列随机变量称为Markov链。定义中 M=\infty 是允许的。这个定义可以理解为：随机变量装在一列黑盒子里(系统)，在时刻 n 照亮第 n 个盒子展示出随机变量 X_n 的值。而这些黑盒子之间有一些奇妙的联♂系以保证转移概率。由此可得 \sum_{j=0}^MP_{ij}=1 ，这是因为 i 总是要转移到一个数。我们把矩阵 \bm A=(P_{ij}) 称为转移概率矩阵。矩阵的每一行元素之和都为1。有了转移概率，我们就可以计算一些相关的概率，比如联合分布：P(X_n=i_n\ \wedge\ \cdots\ \wedge\ X_0=i_0)=P(X_0=i_0)P_{i_0i_1}\cdots P_{i_{n-1}i_n} 。这个式子的意思是，系统在时刻 s 处于 i_s ， 0\leq s\leq n 的概率，等于初始概率乘以一系列转移概率。证明也不难，直接使用条件概率乘法公式和转移概率的定义即可。在Markov链的研究中还常需要 \bm n 步转移概率 P_{ij}^n ，也就是经过 n 个时刻从状态 i 变成状态 j 的概率，即 P_{ij}^n=P(X_{m+n}=j|X_m=i) 。为了探索 n 步转移概率的计算方法，我们先计算 P_{ij}^2 ：\begin{align} P_{ij}^2&=P(X_2=j|X_0=i)\\ &=\sum_{k=0}^MP(X_2=j\ \wedge\ X_1=k|X_0=i)\\ &=\sum_{k=0}^MP(X_2=j|X_1=k,X_0=i)P(X_1=k|X_0=i)\\ &=\sum_{k=0}^MP_{ik}P_{kj} \end{align} 可以发现这实际上就是矩阵 \bm A^2 的 (i,j) 元素。一般地，我们可以证明：n 步转移概率可以用矩阵来表示：\bm A^n=(P_{ij}^n) 。仿照上面的计算，借助归纳法可以给出证明：P_{ij}^{n+1}=\sum_{k=0}^MP_{ik}^nP_{kj} 。Example 2
假设今天下雨而明天下雨的概率是0.7，今天不下雨而明天下雨的概率是0.6。假设今天下雨，计算从今天开始的第4天下雨的概率。用0表示下雨，1表示不下雨。转移概率矩阵为 \bm A= \begin{pmatrix} 0.7&0.3\\ 0.6&0.4\\ \end{pmatrix} ，计算得出 \bm A^4= \begin{pmatrix} 0.5749&0.39\\ 0.5668&0.4332\\ \end{pmatrix} 。故所求概率为 P_{00}^4=0.5749 。由于 \bm A^n=\bm A^r\bm A^{n-r} ，还可以得到下面的实用计算公式：Chapman–Kolmogorov方程： P_{ij}^n=\sum_{k=0}^MP_{ik}^rP_{kj}^{n-r},0\leq r\leq n 。如果需要计算时刻 n 系统处于状态 j 的概率 P(X_n=j) ，我们只需要知道初始概率以及计算出 n 步转移概率： P(X_n=j)=\sum_{i=0}^MP(X_n=j|X_0=i)P(X_0=i)=\sum_{i=0}^MP_{ij}^nP(X_0=i) 。如果设 \bm x_n=(P(X_n=0),\cdots,P(X_n=M)) ，则 \bm x_n=\bm x_0\bm A^n 。下面我们研究一种特别的Markov链，称为遍历的Markov链。这种链满足对某个 n\in\mathbb N^* ，所有的 n 步转移概率都不为零。用图的语言也就是说，这个图在 n 条边以内都是连通的，每一个状态只要运气足够好都可以不超过 n 步到达另一个状态。抽象起来就是P_{ij}^n>0,i,j=0,1,\cdots,M\\ 关于这样的Markov链，有很好的结论。在 n 很大时，无论 i 是多少，在 n 步达到状态 j 的转移概率 P_{ij}^n 都会趋近于一个定值，也就是随着 n 增大， \bm A^n 的每一列元素逐渐趋同化。这就是下面的定理：一个遍历的Markov链一定满足：(1)极限 \pi_j=\lim_{n \rightarrow \infty}{P_{ij}^n} 存在；(2) \pi_j(j=0,\cdots,M) 是方程组 \begin{cases} \pi_j=\displaystyle\sum_{k=0}^M\pi_kP_{kj},j=0,\cdots,m\\ \displaystyle\sum_{j=0}^M\pi_j=1 \end{cases} 的唯一非负解。这个定理证明需要许多矩阵论的知识。首先要做一个转置把上面的 \bm x_n=\bm x_0\bm A^n 变成熟悉的左乘；这并不会影响任何东西。设 \bm B=\bm A^T,\bm y_n=\bm x_n^T ，我们可以证明 \bm B 的特征值均满足
\lambda|\leq 1 ，且 \bm B 有一个特征值1(注意， \bm B 与 \bm A 相似，用 \bm A 的性质来证明。前者是因为考虑合适的矩阵范数，比如每一行的绝对值之和的最大者，则
\bm A
=1 ，且 \bm{Ax}=\lambda \bm x 推出
\lambda|\cdot
\bm x
=
\bm{Ax}
\leq
\bm A
\cdot
\bm x
。后者是因为 \bm A 有一个特征值1，而这是因为 \bm A 的每一行之和为1，令 \bm x=(1,\cdots,1) 则 \bm{Ax}=\bm x )。我们有Perron定理：设方阵 \bm A 的元素都大于零，则存在 \bm A 的正实特征值 r 满足：(1) r 为特征方程的单根；(2) r 有一个正的特征向量 \bm x ；(3)其余特征值的模都小于 r 。由Perron定理得 \bm B 的特征值除了1以外模都小于1(首先是 \bm B^n )。利用这个特点，设 \bm B=\bm Y\bm J\bm Y^{-1} ， \bm J 为Jordan标准形。设 \bm E 表示除了左上角为1以外所有元素为0的矩阵，证明当 n\to\infty 时 \bm J^n\to\bm E 。(注意由Perron定理，特征值1只有一个1阶Jordan块)这样可以证明序列 \left\{ \bm y_n =\bm B^n\bm y_0\right\} 的极限存在，设为 \bm y 。注意，这个结论对于任何 \bm y_0 都成立，所以我们可以通过取特殊的 \bm y_0 来得到 \lim_{n \rightarrow \infty}{P_{ij}^n} 。我们还可以证明 \bm y 关于 \bm y_0 是不变的(留作习题)，所以分别取 \bm y_0=\bm e_i(i=0,1,\cdots,M) 就得到 P_{ij}^n 收敛于共同的值 \pi_j=y_j ( \bm y 的第 j 个分量)。(1)得证。对于(2)，首先由Chapman–Kolmogorov方程得 P_{ij}^{n+1}=\sum_{k=0}^MP_{ik}^nP_{kj} ，两边取极限得 \pi_j=\displaystyle\sum_{k=0}^M\pi_kP_{kj} 。而另一个式子是因为 \sum_{j=0}^My_j=1 。还是Perron定理，矩阵 \bm I-\bm A 的零空间维数为1，从而上述方程组有唯一解。(2)得证。关于 \pi_j 这个量有一个比较好的直观解释。如果设前 n 个时刻处于状态 j 的时刻数为 \mu_{nj} ，由强大数定律可以证明 \frac{\mu_{nj}}{n} 几乎必然收敛于一个数 P_j ，它表示在所有时间里状态 j 的时长比例。由这个含义可知 P_j=\sum_{k}P_kP_{kj},\sum_jP_j=1 。由上面的定理中关于唯一解的描述得 P_j=\pi_j 。所以， \pi_j 这个数表示状态 j 的时长比例。这足以解决许多实际问题。惊奇，不确定性和熵对一件让我们惊讶的事情，我们常说「信息量过大」。这表示惊奇的程度与信息量有关。而惊奇的程度通常与概率有关，小概率事件才会让我们惊奇。美国《纽约太阳报》19世纪70年代的编辑主任约翰·博加特把新闻解释为「狗咬人不是新闻，人咬狗才是新闻」。为了研究这种问题，我们定义事件的惊奇为一个定义域为 [0,1] 的函数 S(p) ，其中 p 表示事件的概率。这个函数满足下面的四个条件：(1) S(1)=0 ；(2) S(p) 严格单调递减；(3) S 是一个连续函数；(4) S(pq)=S(p)+S(q) 。我们稍微解释一下这些条件。(1)表示必然事件听起来一点也不令人惊奇。(2)表示概率越小的事件越让人惊奇。(3)表示概率差距很小的事件也只会引起惊奇程度的很小差别。(4)比较抽象，想象独立事件 E,F 发生的概率分别为 p,q ，则 EF 的惊奇为 S(pq) 。但是这两个事件独立，所以可以看成我们知道这两件事情之后惊奇程度往上累加，即 S(p)+S(q) 。这些条件在日常视角看来都是合理的。下面严格推导 S 的解析表达式。S(p)=-C\log_2p,C>0 。这就是一个经典的解函数方程问题。首先证明对任意正整数 n 有 S(p^n)=nS(p) ，然后扩充到全体整数，再扩充到全体有理数 x 。(这些都可以用数学归纳法完成。)最后对任何实数 x ，设有理数序列 \left\{ x_n \right\} 满足 x_n\to x ，由函数连续性知S(p^x)=\lim_{n\to\infty}S(p^{x_n})=\lim_{n\to\infty}x_nS(p)=xS(p) 。现在对某个 p ，令 x=-\log_2p ，则 S(p)=S\left( \left( \frac 12 \right)^x \right)=xS\left( \frac 12 \right)=-C\log_2p,C=S\left( \frac 12 \right)>S(1)=0 。得证。在实际中常常令 C=1 ，并给惊奇强行赋予一个单位 \mathrm{bit} (比特)。下面考虑一个随机变量的平均惊奇。对于离散型随机变量 X ，设它的取值为 x_1,\cdots,x_n ，取值为 x_i 的概率为 p(x_i) 。则事件 \left\{ X=x_i \right\} 的惊奇为 S(p(x_i))=-\log_2p(x_i) 。从而平均惊奇就是每一个事件惊奇的加权平均，即 H(X)=-\sum_{i=1}^np(x_i)\log_2p(x_i)\\ 在式子中规定 0\log_20=0 ，事实上由L'Hopital法则可以证明 \lim_{x \rightarrow 0^+}{x\log_2x}=0 。这个平均惊奇在信息论中被称为 X 的熵。以下为了方便，用 \log 代替 \log_2 。与物理学里的熵一样，这里的熵可以表示随机变量 X 的不确定程度。还可以表示观测到 X 的值以后接收的平均信息量。如上所述，还可以表示惊奇程度。首先我们有下面的结论。当 p(x_i) 全都相等(等于 \frac 1n )时， H(X) 取得最大值。设 f(x)=x\log x ，则 f''(x)=\frac{1}{x\ln 2}>0 ， f(x) 是一个凸函数。所以由分析学中的Jensen不等式： f\left( \frac{x_1+\cdots+x_n}{n} \right)\geq\frac 1n(f(x_1)+\cdots+f(x_n)) 。令 x_i为 p(x_i) 就证得命题。结论很直观，所有取值概率相等的时候最难预测随机变量的值。现在推广熵的定义，考虑两个离散型随机变量 X,Y ，它们的各自取值分别为 x_1,\cdots,x_n;y_1,\cdots,y_m 。设它们的联合分布列为 p(x_i,y_j) ，各自分布列为 p_X(x_i),p_Y(y_j) 。则它们的熵为 H(X,Y)=-\sum_{i=1}^n\sum_{j=1}^mp(x_i,y_j)\log p(x_i,y_j)\\ 同理可以定义 n 个离散型随机变量的熵：H(X_1,\cdots,X_n)=-\sum_{p(x_1,\cdots,x_n)>0} p(x_1,\cdots,x_n)\log p(x_1,\cdots,x_n)\\ 我们还可以定义条件熵 H(X|Y) ，它定义为 H(X|Y)=-\sum_{i=1}^n\sum_{j=1}^mp(x_i|y_j)\log p(x_i|y_j)p_Y(y_j)\\ \ \ \ \ \ \left(=-\sum_{i=1}^n\sum_{j=1}^mp(x_i,y_j)\log p(x_i|y_j)\right) 其中 p(x_i|y_j) 是 X 关于 Y 的条件分布列： p(x_i|y_j)=P(X=x_i|Y=y_j) 。这个式子可以解释为： -\sum_{i=1}^np(x_i|y_j)\log p(x_i|y_j) 表示观察到 Y=y_j 后 X 的不确定性，而关于 Y 的分布列加权平均以后就得到观察到 Y 以后 X 的不确定性。下面的结论也很好理解：H(X,Y)=H(Y)+H(X|Y) 。这是因为\begin{align} H(Y)+H(X|Y)&=-\sum_{j=1}^mp_Y(y_j)\log p_Y(y_j)-\sum_{i=1}^n\sum_{j=1}^mp(x_i|y_j)\log p(x_i|y_j)p_Y(y_j)\\ &=-\sum_{i=1}^n\sum_{j=1}^mp(x_i,y_j)(\log p_Y(y_j)+\log p(x_i|y_j))\left(p(x_i|y_j)=\frac{p(x_i,y_j)}{p_Y(y_j)}\right)\\ &=-\sum_{i=1}^n\sum_{j=1}^mp(x_i,y_j)\log p(x_i,y_j)=H(X,Y) \end{align} 也就是说， X,Y 的总熵等于 Y 的熵加上知道 Y 条件下 X 的熵。下面的引理经常要用到，请大家自行证明。对任何 x>0 ，有 \log x\leq \log \mathrm e(x-1) ，等号成立当且仅当 x=1 。这里还有另一个结论，它表示看到另一个随机变量总是会减少一个随机变量的不确定性。对任何离散型随机变量 X,Y 有 H(X|Y)\leq H(X) ，等号成立当且仅当 X,Y 相互独立。我们有 \begin{align} H(X|Y)-H(X)&=-\sum_{i=1}^n\sum_{j=1}^mp(x_i,y_j)\log p(x_i|y_j)+\sum_{i=1}^n\sum_{j=1}^mp(x_i,y_j)p_X(x_i)\\ &=\sum_{i=1}^n\sum_{j=1}^mp(x_i,y_j)\log \frac{p_X(x_i)}{p(x_i|y_j)}\\ &\leq\sum_{i=1}^n\sum_{j=1}^mp(x_i,y_j)\cdot\log \mathrm e\left(
\frac{p_X(x_i)}{p(x_i|y_j)}-1 \right)\\ &=\log \mathrm e \left( \sum_{i=1}^n\sum_{j=1}^mp_X(x_i)p_Y(y_j)-\sum_{i=1}^n\sum_{j=1}^mp(x_i,y_j) \right)=0 \end{align} 其中用到引理。等号成立当且仅当 p_X(x_i)=p(x_i|y_j),\forall i,j ，即 X,Y 独立。还可以定义多个随机变量互相之间的条件熵，请大家写出合适的定义。差值 H(X)-H(X|Y) 叫做互信息 I(X;Y) ，之所以说「互」是因为 I(X;Y)=\sum_{i=1}^n\sum_{j=1}^mp(x_i,y_j)\log \frac{p(x_i,y_j)}{p_X(x_i)p_Y(y_j)}\\ 互信息表示 X 从 Y (或者反过来)获取的确定性的度量。由此可以得到 I(X;Y)\geq 0 ，等号成立当且仅当 X,Y 相互独立。类似的我们还可以定义多元的互信息： I(X_1,\cdots,X_n;Y)=I(X_1,\cdots,X_n)-I(X_1,\cdots,X_n|Y) ，以及各种条件互信息。这个定义请大家完成。下面我们考虑熵概念在信号传输中的应用。假设离散型随机变量(向量) X 的值需要在信道中传输。为了计算机方便识别，需要把取值编码为 (0,1) 序列。为了不出现混淆，不能出现一个序列是另一个序列的(右)延长。比如说，如果随机变量取值为 x_1,x_2,x_3 ，编码为 1,10,010 。那么如果发来的编码序列是 1010 ，就有 x_1x_3 和 x_2x_2 两种读法，因为 10 是 1 的延长。如果不存在这种延长，容易证明任何一个合法的编码序列都存在唯一的读法。我们的任务是，尽量减小期望码长。一个著名的结论是：期望码长的一个下界是随机变量(向量)的熵。也就是下面的无噪声编码定理：设 X 的取值为 x_1,\cdots,x_N ，把它们编码为符合上述要求的二进制序列， x_i 对应的码长为 n_i 。设 p(x_i) 为 X 的分布列，则\sum_{i=1}^Nn_ip(x_i)\geq H(X)\\ 书上的证明有点故弄玄虚，我把它重制了一下。首先由上面的引理：\begin{align} \sum_{i=1}^Nn_ip(x_i)-H(X)&=\sum_{i=1}^N(n_i+\log p(x_i))p(x_i)\\ &=-\sum_{i=1}^N\log \frac{1}{2^{n_i}p(x_i)}p(x_i)\\ &\geq-\log\mathrm e\sum_{i=1}^N\left( \frac{1}{2^{n_i}p(x_i)}-1 \right)p(x_i)\\ &=\log \mathrm e\left( 1-\sum_{i=1}^N\frac{1}{2^{n_i}} \right) \end{align} 下面我们证明： \sum_{i=1}^N\frac{1}{2^{n_i}}\leq 1 。设 w_j 表示 n_i 中等于 j 的个数。由于任意一个长为 j 的编码不能是长为 k<j 的编码的延长，而长为 k 的编码的长度为 j 的延长个数为 w_k\cdot 2^{j-k} ，这些延长不重复。故有 w_j\leq2^j-\sum_{k=1}^{j-1}w_k\cdot 2^{j-k} ，即 \sum_{k=1}^j\frac{w_k}{2^k}\leq 1 。令 j\to\infty 就得到： \sum_{i=1}^N\frac{1}{2^{n_i}}=\sum_{k=1}^\infty w_k\cdot\frac{1}{2^k}\leq 1 。从而 \sum_{i=1}^Nn_ip(x_i)-H(X)\geq0 ，得证。这里，可以证明：上述编码序列可以做成的充要条件是： \sum_{i=1}^N\frac{1}{2^{n_i}}\leq 1 。必要性已经证明，充分性只需要一步步根据估计的结果构造即可。另外，上述定理的等号不一定能成立，但是可以构造一个例子，这个方案的期望码长与熵的差值小于1。在实际传输过程中，可能出现传输错误的情况。这时的解决方案是把编码再进行一次加密，实现接收端解密时可以忽略一些错误信息。比如需要传输 0 ，我们把它变成 000 传过去，并规定接收端取较多的数码作为接收信息。那么即使出现一点错误变成了 001 ，接收端依然会得到正确的信息。类似这样的方法就叫做编码译码系统。上面所说的编码译码系统的缺陷在于降低了传输效率，编码变得冗长。然而，我们有Shannon建立的有噪声编码定理，保证存在一个传输效率的临界点，如果传输效率比它更低，就存在一个编码译码系统使得错误概率可以任意小。详情请见信息论的书籍。1.某个零售店的客流是强度为 \lambda (人每小时)的Poisson过程。已知在开门的第一个小时内有两位顾客进入。求下列事件的概率：(1)两个人都在前20分钟内到达；(2)至少有一个人在前30分钟内到达。2.设 \left\{ N(t):t\geq0 \right\} 为Poisson过程，计数事件 A 的发生次数。假设时间区间 [0,t] 内事件 A 发生了 n 次。设这 n 次的时刻分别为 W_1<\cdots<W_n 。求 W_1,\cdots,W_n 的联合密度。3.在路上，每5辆卡车中有4辆的后面跟着一辆小汽车，每6辆小汽车后面跟一辆卡车。求路上卡车所占的比例。4.在Markov链中，证明之前提到的极限向量 \bm y 的唯一性。5.设 X_0,X_1,\cdots,X_n,\cdots 为Markov链， i<j<k 。证明已知 X_j 情况下 X_i,X_k 条件独立。6.设 X_1,\cdots,X_n 为独立同分布离散型随机变量，联合分布列为 p(\bm x) 。证明：对于任意的 \varepsilon>0 ，有 \lim_{n\to\infty}P\left( \left|\frac{1}{n}\log p(X_1,\cdots,X_n)+H(X_1)\right|>\varepsilon \right)=0 。7.设 X 为在A处传出的 (0,1) 信号， Y 为在B处接收的 (0,1) 信号，互信息 I(X;Y) 叫做从A到B的信息传输率。假设 P(Y=1|X=1)=P(Y=0|X=0)=p 。求传输率的最大值。8.构造一个之前在无噪声编码定理那里所说的例子。因为是最后一篇笔记，提示会写在下面。1.(1)需要计算 P\left( N\left( \frac 13 \right)=2\bigg|N(1)=2 \right)=\frac{\displaystyle P\left( N\left( \frac 13 \right)=2\right)P\left( N\left( \frac 23 \right)=0 \right)}{P(N(1)=2)}=\frac 19(2)需要计算 P\left( N\left( \frac 12 \right)\geq1\bigg|N(1)=2 \right) ，类似做就可以了。2.证明这个联合密度等于 n 个 [0,t] 均匀随机变量的顺序统计量的联合密度。3.在路上取一个观察点，用 X_n=0 表示通过它的第 n 辆车是小汽车， X_n=1 表示是卡车。则这可以看成一个Markov链，转移概率为P_{00}=\frac 56,P_{01}=\frac 16,P_{10}=\frac 45,P_{11}=\frac 15 。用 \pi_0,\pi_1 分别表示小汽车与卡车的比例，则 \begin{cases} \pi_0=\displaystyle\frac 56\pi_0+\frac 45\pi_1\\ \pi_1=\displaystyle\frac 16\pi_0+\frac 15\pi_1\\ \pi_0+\pi_1=1 \end{cases} ，解得 \pi_0=\frac{24}{29},\pi_1=\frac 5{29} 。故卡车的比例为 \frac 5{29} 。4.先证明 \bm y 为 \bm B 的特征值1的特征向量，然后用Perron定理第一条以及 \bm y 的各位之和为1。5.只须证明 P(X_i=u,X_k=w|X_j=v)=P(X_i=u|X_j=v)P(X_k=w|X_j=v) 。事实上\begin{align} P(X_i=u,X_k=w|X_j=v)&=\frac{P(X_i=u,X_j=v,X_k=w)}{P(X_j=v)}\\ &=\frac{P(X_i=u,X_j=v)P_{vw}^{k-j}}{P(X_j=v)}\\ &=P(X_i=u|X_j=v)P(X_k=w|X_j=v) \end{align} 6.用弱大数定律以及变量的独立性。设各自的分布列为 p(x) ，则\frac 1n\log p(X_1,\cdots,X_n)=\frac 1n\sum_{i=1}^n\log p(X_i) 。7.设联合分布列为 p(x,y) 。设 p(1,1)=x,p(0,1)=y,p(1,0)=z,p(0,0)=w 。由条件： p=P(Y=1|X=1)=\frac{p(1,1)}{p_X(1)}=\frac{p(1,1)}{p(1,1)+p(1,0)} ，得到 y=\left( \frac 1p-1\right)x 。同理 z=\left( \frac 1p-1 \right)w 。而 x+y+z+w=1 ，故 x+w=p,y+z=1-p 。而 P(X=1|Y=0),P(X=0|Y=1)=1-p ，从而\begin{align} I(X;Y)&=x\log\frac{p}{x+y}+y\log\frac{1-p}{x+y}+z\log\frac{1-p}{z+w}+w\log\frac{p}{z+w} \\ &=p\log p+(1-p)\log(1-p)-(x+y)\log(x+y)-(z+w)\log(z+w) \end{align} 只需证明函数 f(t)=t\log t+(1-t)\log(1-t)(0\leq t\leq 1) 的最小值是 -1 。8.令 n_i=\left[ -\log p(x_i) \right] ，则 \sum_{i=1}^N\frac{1}{2^{n_i}}\leq\sum_{i=1}^N2^{\log p(x_i)}=\sum_{i=1}^Np(x_i)=1 。所以满足要求的编码序列存在，且容易证明 H(X)\leq\sum_{i=1}^Nn_ip(x_i)<H(X)+1 。}