Chapter 06 : 随机模型¶
随机性¶
- 必然性与偶然性：揭示客观事物发生、发展和灭亡趋势的一对范畴。
- 必然性（Necessity）：客观事物联系和发展中一定要发生的、确定不移的趋势
- 偶然性（Contingency）：客观事物联系发展中并非确定发生的，可以这样出现也可以那样出现的不确定趋势
- 随机性（Randomness）：偶然性的一种形式
- 可重复性：事件可以在基本相同的条件下重复进行。只有单一的偶然过程而无法判定它的可重复性则不称为随机事件
- 多样性：在基本相同条件下某事件可能以多种方式表现出来，事先不能确定它以何种特定方式发生。只有唯一可能性的过程不是随机事件
- 概率性：事先可以预见该事件以各种方式出现的所有可能性，预见它以某种特定方式出现的概率。在重复发生时没有确定概率的现象不是同一过程的随机事件
疾病检测¶
- 记 \(A\) 为患病，\(B\) 为检测结果为阳性，疾病检测方法的性能指标为：
- 灵敏度（Sensitivity）\(p=P(B|A)\)：患病者被检测为阳性（Positive）的概率
- 特异度（Specificity）\(q=P(\overline{B}|\overline{A})\)：未患病者被检测为阴性（Negative）的概率
- 设疾病的发病率为 \(r\) ，则被检测出阳性的情况下患病的概率为
概率群式¶
概率群式：假定 \(n\) 个人相互独立地以概率 \(p\) 患病，如何找出全部的病人，使平均检测次数尽可能少？
对于选择群式方案，我们要考虑平均检测次数、检测阶段数、每人最大检测次数、每组最多样本数、方案的可操作性、检测的灵敏度与特异度等多个因素
两阶段群式¶
- 将 \(n\) 人的样本混合后检测。若结果为阴性，说明这 \(n\) 人均未感染。若结果为阳性，说明这 \(n\) 人中至少有一人已感染。此时逐个检测每个人样本
对于这样的检测方案，检测次数如下：
- 混合样本阴性概率为 \((1−p)^n\) ，总检测次数为 1
- 混合样本阳性概率为 \(1−(1−p)^n\)，总检测次数为 \(n+1\)
- 检测次数的数学期望为 \(1⋅(1−p)^n+(n+1)⋅(1−(1−p)^n)\)
所以平均检测次数的数学期望为 \(\frac{1⋅(1−p)^n+(n+1)⋅(1−(1−p)^n)}{n}\)
矩阵检测方案¶
矩阵检测方案是二阶段群式的改进方案
矩阵检测方案
将 \(m\times n\) 个人按矩阵排好，先检测每行样本，若结果为阴性，说明这 \(n\) 人均未感染。若结果为阳性，说明这 \(n\) 人中至少有一人已感染。此时逐个检测每列样本。
这样每行就相当于两阶段群式中的混合样本，每列就相当于两阶段群式中的每个人样本，检测次数数学期望为 \(m\times(1⋅(1−p)^n+(n+1)⋅(1−(1−p)^n))\)，平均检测次数数学期望仍然为 \(\frac{1⋅(1−p)^n+(n+1)⋅(1−(1−p)^n)}{n}\)
将 \(m\times n\) 个人按矩阵排好，对每行每列分别进行检测。通过检测结果确定感染者的位置。
这样需要的检测次数恒为 \(m+n\)
三阶段检测方案¶
三阶段检测方案也是二阶段群式的改进方案
- 第一阶段：有 \(n\) 个人，进行总体的混合检测，若结果为阴性，说明这 \(n\) 人均未感染。若结果为阳性，说明这 \(n\) 人中至少有一人已感染。进入第二阶段
- 第二阶段：将这 \(n\) 人分成 \(A,B\) 两组，每组 \(\frac{n}{2}\) 人，先对 \(A\) 组进行检测，若结果为阴性，说明这 \(\frac{n}{2}\) 人均未感染，且确定感染者在 \(B\) 组。若结果为阳性，说明这 \(\frac{n}{2}\) 人中至少有一人已感染，但仍需确定 \(B\) 组是否有感染者，此时对 \(B\) 组进行总体的混合检测
- 第三阶段：对有感染者的组进行逐个检测，确定感染者的位置
检测次数
- 对于第一阶段，结果为阴性的概率为 \((1-p)^n\)，总检测次数为 1
- 对于第二阶段：
- \(A\) 组结果为阴性的概率为 \((1-p)^{\frac{n}{2}}\)，此时 \(B\) 组必然为阳性，这发生的概率为 \(1-(1-p)^{\frac{n}{2}}\)，总检测次数为 \(1+1+\frac{n}{2}=2+\frac{n}{2}\)
- \(A\) 组结果为阳性的概率为 \(1−(1−p)^{\frac{n}{2}}\)，\(B\) 组结果为阴性的概率为 \((1−p)^{\frac{n}{2}}\)，总检测次数为 \(1+1+\frac{n}{2}+1=3+\frac{n}{2}\)
- \(A\) 组结果为阳性的概率为 \(1−(1−p)^{\frac{n}{2}}\)，\(B\) 组结果为阳性的概率为 \(1−(1−p)^{\frac{n}{2}}\)，总检测次数为 \(1+1+\frac{n}{2}+1+\frac{n}{2}=3+n\)
所以总检测次数的数学期望为：
平均检测次数的数学期望为 \(1+\frac{3}{n}-(1+\frac{1}{n})(1-p)^{\frac{n}{2}}-\frac{1}{n}(1-p)^n\)
随机变量¶
详见 概统 笔记
赠券收集问题¶
问题描述
一套赠券共有 \(N\) 种，商家在每件商品中随机放入一张赠券。假设每件商品中放入各种赠券的概率相同，那么集齐全套赠券平均需购买多少件商品？
De Morgan 定律¶
定义随机变量 \(X\) 为“集齐全套赠券需购买的商品件数”，\(E(X)=\sum\limits_{i=1}^Ni⋅P(X=i)\)。记 \(B_i\) 为事件“购买 \(i\) 件商品后集齐全套赠券”，记 \(A_i^j\) 为事件“购买 \(i\) 件商品后收集到第 \(j\) 种赠券”。则有:
分析括号中的第二项，对任意固定的 \(j,k,1\leq j<k\leq N\)，\(\overline{A_i^j}\cap\overline{A_i^k}\) 表示购买 \(i\) 件商品后未收集到第 \(j\) 种和第 \(k\) 种赠券，有 \(P(\overline{A_i^j}\cap \overline{A_i^k})=(1-\frac{2}{N})^i\)
同理，对任意 \(1\leq j_1<j_2<...<j_k\leq N\)，\(\overline{A_i^j}\cap\overline{A_i^k}\) 表示购买 \(i\) 件商品后未收集到第 \(j_1\) 种、第 \(j_2\) 种、...、 第 \(j_k\) 种赠券，有 \(P(\overline{A_i^{j_1}}\cap\overline{A_i^{j_2}}\cap...\cap\overline{A_i^{j_k}})=(1-\frac{k}{N})^i\)。因此，有：
所以其期望为 \(\sum\limits_{i=1}^N i·P(X=i)=\sum\limits_{i=1}^N i·\sum\limits_{j=0}^N(-1)^jC_N^j(1-\frac{j}{N})^i\)
几何分布¶
记随机变量 \(X\) 为“集齐全套赠券购买的商品件数”，定义随机变量 \(Y\) 为“从收集到 \(k−1\) 种赠券到 \(k\) 种赠券购买的商品件数”，则有：\(X=Y_1+Y_2+⋯+Y_N\)
我们考察 \(Y_k\)。\(Y_k=j\) 意味着先购买的 \(j−1\) 件商品中的赠券均为已收集到的 \(k−1\) 种中的一种，第 \(j\) 件商品中有未收集到的 \(N−k+1\) 种赠券中的一种。可知，\(Y_k\) 服从参数为 \(\frac{N−k+1}{N}\) 的几何分布
所以，根据几何分布的性质，有 \(E(Y_k)=\frac{N}{N−k+1}\)。因此，\(E(X)=\sum\limits_{k=1}^NE(Y_k)=\sum\limits_{k=1}^N\frac{N}{N−k+1}=N\sum\limits_{k=1}^N\frac{1}{k}\)
显然，方法二的计算量要小于方法一；而且，方法二的思路更加简单，更加容易理解
随机过程¶
随机过程¶
随机过程是描述随机现象随时间推移而演化的一类数学模型。
• 一族随机变量 \(\{X(t),t\in T\}\) ，其中 \(t\) 是参数，\(T\) 为参数集。 \(\cdot T\) 为整数集的随机过程称为随机序列。
Markov 过程¶
Markov 过程意味着：在已知目前的状态（现在）的条件下，它未来的演变（将来）不依赖于它以往的演变（过去）
对随机序列 \(\{X_n,n=0,1,2⋯\}\)（\(X_n\) 为有限个或可数个），\(P(X_{n+1}=i_{n+1})\) 只与 \(X_n\) 有关， 而与 \(X_{n−1},X_{n−2},⋯\) 无关，则称 \(\{X_n,n=0,1,2⋯\}\) 为 Markov 链。用数学语言描述为\(P(X_{n+1}=i_{n+1}|X_n=i_n,X_{n−1}=i_{n−1},⋯,X_0=i_0)=P(X_{n+1}=i_{n+1}|X_n=i_n)\)
赌徒破产问题¶
问题描述
一个赌徒在初始时拥有 \(h\) 个单位财富。在每局赌博中以概率 \(p\) 赢一个单位财富，以概率 \(q=1−p\) 输一个单位财富。各局赌博结果独立。当赌徒的财富达到 \(N\) 个单位或 \(0\) 个单位（破产）时停止赌博。求赌徒破产的概率。
记 \(P_h\) 和 \(Q_h\) 分别为赌徒初始财富为 \(h\) 个单位时，财富最终达到 \(N\) 个单位的和 \(0\) 个单位的概率，显然有初始条件 \(P_N=1,P_0=0,Q_N=0,Q_0=1\)
对 \(P_h\)，可以由如下 Markov 链得到：
那么有 \(P_h=pP_{h+1}+qP_{h-1},1\leq h\leq N-1\)，即 \(P_h-P_{h+1}=\frac{q}{p}(P_{h-1}-P_h)\)
解递推关系，可得 \(P_h=\begin{cases}\frac{1-(\frac{q}{p})^h}{1-(\frac{q}{p})^N}, & q\not=p\\\frac{h}{N}, & q=p\end{cases}\)
对 \(Q_h\)，设想赌徒与另一位在初始时拥有 \(N−h\) 个单位财富的虚拟赌徒赌博。在每局赌博中虚拟赌徒以概率 \(q\) 赢一个单位财富，以概率 \(p\) 输一个单位财富。赌徒破产时，虚拟赌徒财富达到 \(N\) 个单位。
所以真实赌徒从 \(h\) 输到破产就相当于虚拟赌徒从 \(N−h\) 的赚到 \(N\) 个单位，即 \(Q_h=P_{N−h}'\)
因为 \(P_h'=\begin{cases}\frac{1−(\frac{p}{q})^h}{1−(\frac{p}{q})^N}, & p\not=q\\\frac{h}{N}, & p=q\end{cases}\)（输赢需要对调），所以 \(Q_h=P_{N-h}'=\begin{cases}\frac{1−(\frac{p}{q})^{N-h}}{1−(\frac{p}{q})^N}=\frac{(\frac{q}{p})^N-(\frac{q}{p})^h}{(\frac{q}{p})^N-1}, & p\not=q\\\frac{N-h}{N}, & p=q\end{cases}\)
Pascal 问题¶
问题描述
A,B 两人玩一种游戏，初始时两人各有 12 分。一次掷三枚骰子，若点数恰为 11 则 A 胜 B 负，点数恰为 14 则 B 胜 A 负，其他点数不分胜负。对出现胜负的一次投掷，胜一方增 1 分，负一方减 1 分。分数先为 0 分的一方失败。求双方获胜的概率之比
我们采用多项式的方法计算掷三枚骰子，点数恰为 \(j\) 的概率。
总可能性为 \(6^3=216\) ，所以点数恰为 \(j\) 的概率为 \(\frac{a_j}{216}\) ，其中 \(a_j\) 为上式中 \(x_j\) 的系数。
一次投掷，A 胜的概率为 \(p=a_{11}{216}=\frac{27}{216}\) ，B 胜的概率为 \(q=\frac{a_{14}}{216}=\frac{15}{216}\)，不分胜负的概率为 \(1−p−q=\frac{1−a_{11}−a_{14}}{216}=\frac{174}{216}\)
我们从获胜的角度来看，就是判断从 12 分到 24 分的概率。我们可以用 Markov 链来解决这个问题
记 \(P_h\) 为 A 从 \(h\) 分到 24 分的概率，\(Q_h\) 为 B 从 \(h\) 分到 24 分的概率，显然有初始条件 \(P_{24}=1,P_0=0,Q_{24}=1,Q_0=0\)
根据 Markov 链，我们可以得到如下递推关系：
即：
解递推关系，有 \(P_h=\frac{1-(\frac{q}{p})^h}{1-(\frac{q}{p})^{24}},Q_h=\frac{1-(\frac{p}{q})^h}{1-(\frac{p}{q})^{24}}\)
代入 \(h=12\)，得到：
所以 \(\frac{P_{12}}{Q_{12}}=\frac{3^{48}-3^{24}5^{12}}{3^{24}5^{12}-5^{24}}=\frac{3^{24}}{5^{12}}=\frac{282429536481}{244140625}\)
显然 A 获胜的概率要远大于 B 获胜的概率