首页 > 其他分享 >[学习笔记] 概率与期望及其应用

[学习笔记] 概率与期望及其应用

时间：2022-11-05 09:45:49浏览次数：67  
标签：概率 frac 1.1 笔记 times 事件 空门 期望

前言

这是一篇初学者的学习笔记，可能有些不准确或者遗漏的地方，还请各位指出。

可以通过 目录 或者 Ctrl + F 寻找所需内容。

点击展开目录

目录

引入 - 蒙提霍尔问题

如果不需要可以跳过。

你正在参加活动。在你面前有三扇关闭的门，其中一扇门后面是奖品，另外两扇门后面是空的。你希望能获得奖品。

在这个题目背景下，有以下几个问题：

你选定了一扇门后直接打开。

此时获得奖品的概率为 \(\frac {1} {3}\)。

在你选定了一扇门后，主持人随机打开剩下两扇门中的一扇，如果发现是空的，他会问你是否更换选择。你的决定是？

考虑以下情况：

  • 你最开始选的门为奖励门（概率为 \(\frac{1} {3}\)），在主持人开了空门（概率为 \(\frac{1} {2}\)）后，选择换门。获得奖品的概率为 \(0\)。
  • 你最开始选的门为奖励门（概率为 \(\frac{1} {3}\)），在主持人开了空门（概率为 \(\frac{1} {2}\)）后，选择不换门。获得奖品的概率为 \(\frac{1} {3}\)。
  • 你最开始选的门为空门（概率为 \(\frac {1} {3}\)），在主持人开了空门（概率为 \(\frac {1} {2}\)）后，选择换门。获得奖品的概率为 \(\frac {1} {3}\)。
  • 你最开始选的门为空门（概率为 \(\frac {1} {3}\)），在主持人开了空门（概率为 \(\frac {1} {2}\)）后，选择不换门。获得奖品的概率为 \(0\)。
  • 你最开始选的门为空门（概率为 \(\frac {1} {3}\)），在主持人开了奖励门（概率为 \(\frac {1} {2}\)）后，选择换门。获得奖品的概率为 \(0\)。
  • 你最开始选的门为空门（概率为 \(\frac {1} {3}\)），在主持人开了奖励门（概率为 \(\frac {1} {2}\)）后，选择不换门。获得奖品的概率为 \(0\)。

综上，无论换不换门，获得奖品的概率都为 \(\frac{1} {3}\)。

在你选定了一扇门后，主持人打开剩下两扇门中的一扇空门，然后他问你是否更换选择。你的决定是？

考虑以下情况：

  • 你最开始选的门为奖励门（概率为 \(\frac{1} {3}\)），在主持人开了空门后，选择换门。获得奖品的概率为 \(0\)。
  • 你最开始选的门为奖励门（概率为 \(\frac{1} {3}\)），在主持人开了空门后，选择不换门。获得奖品的概率为 \(\frac{1} {3}\)。
  • 你最开始选的门为空门（概率为 \(\frac{2} {3}\)），在主持人开了空门后，选择换门。获得奖品的概率为 $\frac{2} {3} $。
  • 你最开始选的门为空门（概率为 \(\frac{2} {3}\)），在主持人开了空门后，选择不换门。获得奖品的概率为 \(0\)。

综上，换门获得奖品的概率为 \(\frac {2} {3}\)，不换门获得奖品的概率为 \(\frac {1} {3}\)。

通过以上问题的讨论，你已经初步接触了概率论。下文会继续讲解相关内容。

1. 事件的概念、运算与关系

1.1 基础概念

1.1.1 随机试验

具有以下特点的试验称为随机试验：

  • 试验可在相同条件下重复进行。
  • 试验可能出现多种结果，且试验前已知所有结果的可能性。
  • 无法预测试验出现哪一结果。

通常用 \(E\) 来表示随机试验。

举个栗子：

  • E1：摇一次骰子，观察点数出现情况。
  • E2：抛一次硬币，观察正反面出现情况。

1.1.2 基本事件

随机试验中可能出现的每一个结果，也称样本点。记作 \(\omega\)。

举个栗子：

  • 前文 E1 有六个基本事件，其中第 \(i\) 个基本事件为出现点数为 \(i\)。
  • 前文 E2 有两个基本事件，出现正面 和 出现反面。

1.1.3 样本空间

随机试验中所有基本事件构成一个集合，称为样本空间。记作 \(\Omega\)。

举个栗子：

  • 前文 E1 的样本空间为 \(\{1,2,3,4,5,6\}\)。
  • 前文 E2 的样本空间为 \(\{正面,反面\}\)。

1.1.4 随机事件

随机试验中部分基本事件构成一个集合，称为随机事件。随机事件是样本空间的子集。使用大写字母进行表示。

举个栗子：

  • 前文 E1 中出现偶数点数的事件可表示为 \(A=\{2,4,6\}\)。
  • 前文 E1 中出现奇数点数的事件可表示为 \(B=\{1,3,5\}\)。

1.1.5 事件发生

当某一事件所包含的基本事件中至少有一个发生，那么该事件发生了。

好像有点废话

1.1.6 必然事件

一定发生的事件。也就是样本空间 $ \Omega$。

1.1.7 不可能事件

一定不发生的事件。记作 \(\Phi\)。（然而我并不是很清楚这是什么符号，有没有大佬给个解答）

1.2 事件运算

1.2.1 事件的和（并）

事件 \(A\) 与 事件 \(B\) 至少有一个发生，这个事件称为 事件 \(A\) 与 事件 \(B\) 的和（并），记作 \(A+B\) 或 \(A\cup B\)。

举个栗子：

\(A=\{1,2\}\)

\(B=\{3,4,5\}\)

\(A+B=\{1,2,3,4,5\}\)

1.2.2 事件的差

事件 \(A\) 发生而 事件 \(B\) 不发生，这个事件称为 事件 \(A\) 与 事件 \(B\) 的差，记作 \(A-B\)。\(A-B=\complement_A(A\cap B)\)

举个栗子：

\(A=\{1,2,4,5\}\)

\(B=\{1,4\}\)

\(A-B=\{2,5\}\)

1.2.3 事件的积（交）

事件 \(A\) 与 事件 \(B\) 同时发生，这个事件称为 事件 \(A\) 与 事件 \(B\) 的积（交），记作 \(AB\) 或 \(A\cap B\)。

1.2.4 推广

事件的和与积可推广到多个事件，而差不可以。

为什么差不可以推广？

和与积的推广长这样：

\(A+B+C=A\cup B\cup C\)

\(ABC=A\cap B\cap C\)

然而当你计算差时：

\(A-B-C=(A-B)-C=\complement_A(A\cap B)-C=\complement_{\complement_A(A\cap B)}(\complement_A(A\cap B)\cap C)\)

它似乎……不大一样呢？

1.3 事件关系

1.3.1 包含

若 事件 \(A\) 发生，那么事件 \(B\) 必然发生。

具体表示 \(A\subset B\) 或者 \(B\supset A\)。

注意：\(\Phi \subset A\subset\Omega\)。

1.3.2 相等

若 \(A\subset B\) 且 \(B\subset A\)，那么 \(A=B\)。

1.3.3 互斥

若 事件 \(A\) 与 事件 \(B\) 不能同时发生（\(AB=\Phi\)），则称 事件 \(A\) 与 事件 \(B\) 互不相容或互斥。\(A\) 与 \(B\) 互不相容意味着 \(A\) 与 \(B\) 不含公共基本事件。

1.3.4 对立（互逆）

若 事件 \(A\) 与 事件 \(B\) 发生了有且仅有一个，且 \(A\cup B=\Omega\)、\(A\cap B=\Phi\)，则称 事件 \(A\) 与 事件 \(B\) 对立（互逆）。

其中 事件 \(B\) 叫做 事件 \(A\) 的逆事件，记作 \(B=\overline{A}\)。事件 \(A\) 叫做 事件 \(B\) 的逆事件，记作 \(A=\overline{B}\)。

1.3.5 举例理解

进行三次射击，\(A_i\) 表示第 \(i\) 次击中。

\(A_1+A_2\) 表示前两次射击至少击中一次

\(\overline{A_2}\) 表示第二次未击中。

\(A_2-A_3=\complement_{A_2}(A_2\cap A_3)=A_2\overline{A_3}\) 表示第二次击中而第三次未击中。

2. 概率

2.1 概率的数学定义

设 \(\Omega\) 是随机试验 \(E\) 的样本空间，找到一个对应法则，使得 \(E\) 的每一个事件 \(A\) 都对应一个实数，这记为 \(P(A)\)。

2.2 概率的性质及应用

2.2.1 概率的性质

  • \(P(\Omega)=1\)。（正则性）
  • \(P(\emptyset)=0\)。
  • \(0\leq P(A)\leq1\)。（非负性）
  • 若 \(A_1,A_2,A_3,...,A_n,...\) 互不相容，则 \(P\left(\bigcup_{i=1}^{\infty}A_i \right)=\sum_{i=1}^{\infty}P(A_i)\)。（可列可加性）
  • 若 \(AB=\Phi\)，则 \(P(A\cup B)=P(A)+P(B)\)。（有限可加性）（可推广到 \(n\) 个互不相容的事件）
  • \(P(A)=1-P(\overline{A})\)。
  • \(P(B-A)=P(B)-P(AB)\)。
  • \(P(A\cup B)=P(A)+P(B)-P(AB)\)。

应该不用证明吧？

2.3 条件概率

设 \(E\) 为一随机试验，\(A\) 和 \(B\) 为其中的两个事件且 \(P(A)>0\)，那么 \(\frac{P(AB)} {P(A)}\) 为发生 事件 \(A\) 的情况下 事件 \(B\) 发生的条件概率，记作 \(P(B|A)\)。所以 \(P(B|A)=\frac{P(AB)}{P(A)}\)。（公式可变形为 \(P(AB)=P(A)\times P(B|A)\)）

举个栗子：

布袋中有 \(3\) 个黑球和 \(2\) 个白球，每次随机取出一颗球（不放回），求第两次摸到白球的概率。

  • 如果第一次取出了黑球（概率为 \(\frac{3} {5}\)），那么袋子中还剩下 \(2\) 个黑球和 \(2\) 个白球，第二次摸到白球的概率为 \(\frac{1} {2}\)，该情况的概率为 \(\frac{3} {5}\times\frac{1} {2}=\frac{3} {10}\)。
  • 如果第一次取到了白球（概率为 \(\frac{2} {5}\)），那么袋子中还剩下 \(3\) 个黑球和 \(1\) 个白球，第二次摸到白球的概率为 \(\frac{1} {4}\)，该情况的概率为 \(\frac{2} {5}\times\frac{1} {4}=\frac{1}{10}\)。

第二次摸到白球的总概率就是 \(\frac{3} {10}+\frac{1} {10}=\frac{2} {5}\)。

由条件概率公式可推得 \(P(AB)=P(A\cap B)=P(B)P(A|B)=P(A)P(B|A)\)。

3. 公式与模型

3.1 全概率公式

如果事件 \(B_1,B_2,...,B_n\) 两两互不相容，且和为全集，\(\forall P(B_i)>0\)。

那么对于任一事件 \(A\) 有：。\(P(A)=\sum_{i=1}^nP(AB_i)=\sum_{i=1}^n(P(A|B_i)\cdot P(B_i))\)。

特别地，对于任意两个随机事件 \(A\) 和 \(B\)（\(A,B\) 对立），有式子 \(P(B)=P(B|A)P(A)+P(B|\overline{A})P(\overline{A})\)。

3.2 贝叶斯公式

设 \(B1,B2,...\) 是样本空间 $\Omega $ 的一个划分，则对任一 事件\(A\) （\(P(A)> 0\)），有：

\(P(B_i|A)=\frac{P(B_i)P(A|B_i)} {\sum_{j=1}^nP(B_j)P(A|B_j)}\)。

上式即为贝叶斯公式，\(B_i\) 常被视为导致试验结果 \(A\) 发生的”原因“。

贝叶斯公式建立在条件概率的基础上，寻找事件发生的原因。（即大事件A已经发生的条件下，分割中的小事件Bi的概率）

3.3 波利亚瓦罐模型

一个瓦罐中有 \(n\) 个黑球和 \(m\) 个白球。每次取出一个，记录其颜色，再将它和另外 \(r\) 个与它同色的球放入瓦罐中，如此循环。

结论1：第 \(k\) 次取到黑球的概率为 \(\frac{n} {n+m}\)，取到白球的概率为 \(\frac{m} {n+m}\)。

证明：

当 \(k=1\) 时，取到黑球的概率为 \(\frac{n} {n+m}\)，取到白球的概率为 \(\frac{m} {n+m}\)。

假设第 \(k\) 次成立。

考虑取到黑球的概率：

\(P(k+1)=\frac{n} {n+m}\cdot\frac{n+r} {n+m+r}+\frac{m} {n+m}\cdot\frac{n} {n+m+r}=\frac{n(n+m+r)} {(n+m)(n+m+r)}=\frac{n}{n+m}\)。

取到白球的概率：

\(P(k+1)=\frac{n} {n+m}\cdot\frac{m} {n+m+r}+\frac{m} {n+m}\cdot\frac{m+r} {n+m+r}=\frac{m(n+m+r)} {(n+m)(n+m+r)}=\frac{m} {n+m}\)。

由数学归纳法得证。

结论2：无论 \(a,b(a\neq b)\) 取什么值，第 \(a\) 次与第 \(b\) 次同时取出黑（白）球的概率始终相等。

证明：

设 \(P_{a,b}(n,m)\) 为对应的概率，不难求出 \(P_{1,b}=\frac{n} {n+m}\times\frac{n+r} {n+m+r}\)。

同样考虑数学归纳法。

\(P_{a,b}(n,m)=\frac{n} {n+m}\cdot\frac{n+r} {n+m+r}\cdot\frac{n+2r} {n+m+2r}+\frac{m}{n+m}\cdot\frac{n}{n+m+r}\cdot\frac{n+r}{n+m+2r}=\frac{n(n+r)(n+m+2r)}{(n+m)(n+m+r)(n+m+2r)}=\frac{n} {n+m}\cdot\frac{n+r} {n+m+r}=P_{1,2}(n,m)\)。

得证。

4. 例题

两道期望DP题。似乎和上文没什么关系？？？

4.1 绿豆蛙的归宿

https://www.luogu.com.cn/problem/P4316

4.1.1 题目大意

给一张 \(n\) 个点 \(m\) 条边的有向图，每条边有边权。现从 \(1\) 走到 \(n\)，每次等概率选取一条边走，求路径总长度的期望。

4.1.2 思路

考虑进行期望DP。

设 \(f_i\) 表示从点 \(i\) 出发走到点 \(n\) 的期望路径长度，答案即为 \(f_1\)。初始状态 \(f_n=0\)。

反向连边建图，在图上跑拓扑进行转移。

具体地讲，每次取出一个入度为零的点 \(x\)，枚举它能到的点 \(v\)，在正常拓扑的同时转移，转移式为 \(f_v=\frac{f_x+w(x,v)} {deg_v}\)。

4.1.3 代码实现

int n, m;
int last[N], cnt;
struct edge {
	int to, next, w;
} e[N << 1];
void addedge(int x, int y, int w) {
	e[++cnt].to = y;
	e[cnt].next = last[x];
	e[cnt].w = w;
	last[x] = cnt;
}
int deg[N], lne[N]; //deg为拓扑所用的入度数, lne为出边数 
queue <int> s;
double f[N];
void topsort() {
	for (int i = 1; i <= n; i++)
		if (deg[i] == 0) s.push(i);
	while (s.size()) {
		int x = s.front(); s.pop();
		for (int i = last[x]; i; i = e[i].next) {
			int v = e[i].to; deg[v]--;
			f[v] += (f[x] + e[i].w) * 1.0 / lne[v];
			if (!deg[v]) s.push(v);
		}
	}
}
int main() {
	n = read(), m = read();
	for (int i = 1; i <= m; i++) {
		int u = read(), v = read(), w = read();
		addedge(v, u, w); deg[u]++, lne[u]++; //反向建边 
	}
	topsort();
	printf("%.2lf", f[1]);
	return 0;
}

4.2 [NOIP2016 提高组] 换教室

https://www.luogu.com.cn/problem/P1850

4.2.1 题目大意

一共有 \(n\) 个时间节点上安排了课程，对于每个时间节点 \(i\)，两节内容相同的课会占用 \(c_i\) 和 \(d_i\) 两间教室。

一般来讲，学生需按时间在 \(c_i\) 教室完成第 \(i\) 节课。但他们也可以通过提交申请尝试更换教室。具体地，申请更换第 \(i\) 节课的教室通过的概率为已知实数 \(k_i\)，如果申请通过，学生就可以去 \(d_i\) 教室上课。

牛牛可以提交最多 \(m\) 次申请。由于两教室间的距离和拥堵程度不同，牛牛在前往教室时耗费的体力也不同。当第 \(i(1\leq i<n)\) 节课结束后，他会从这间教室沿耗费体力最少的路径前往下个教室。

问申请更换教室后 在教室间移动耗费的体力值的总和 的期望值 最小是多少。

4.2.2 思路

需要知道每两间教室直接的最短路长度时多少。这可以用 Floyed 解决。

然后考虑DP，设 \(f_{i,j,0/1}\) 表示前 \(i\) 个时间节点换了 \(j\) 次教室，第 \(i\) 个时间节点 换/没换 教室，耗费的体力值的总和的期望最小是多少。

怎么转移？

\(f_{i,j,0}=\min\{f_{i-1,j,0}+dis(c_{i-1},c_i),f_{i-1,j,1}+dis(d_{i-1},c_i)\times k_{i-1}+dis(c_{i-1},c_i)\times(1-k_{i-1}) \}\)

\(f_{i,j,1}=\min\{f_{i-1,j-1,0}+dis(c_{i-1},d_i)\times k_i+dis(c_{i-1},c_i)\times(1-k_i),\)\(f_{i-1,j-1,1}+dis(d_{i-1},d_i)\times k_{i-1}\times k_i+dis(d_{i-1},c_i)\times k_{i-1}\times(1-k_i)\)\(+dis(c_{i-1},d_i)\times(1-k_{i-1})\times k_i+dis(c_{i-1},c_i)\times(1-k_{i-1})\times(1-k_i) \}\)

答案即为 \(\min_{i=0}^mmin(f_{n,i,0},f_{n,i,1})\)。

4.2.3 代码实现

dp转移太长了，代码很丑，见谅~

const int N = 2010, M = 90010;
const double INF = 1e17;
int n, m, cntroom, cntedge, c[N], d[N];
ll dis[N][N];
double f[N][N][2], k[N];
int main() {
	n = read(), m = read(), cntroom = read(), cntedge = read();
	for (int i = 1; i <= cntroom; i++)
		for (int j = i + 1; j <= cntroom; j++)
			dis[i][j] = dis[j][i] = INF;
	for (int i = 1; i <= n; i++) c[i] = read();
	for (int i = 1; i <= n; i++) d[i] = read();
	for (int i = 1; i <= n; i++) scanf("%lf", &k[i]);
	for (int i = 1; i <= cntedge; i++) {
		int u = read(), v = read(), w = read();
		dis[u][v] = dis[v][u] = min(dis[u][v], w * 1ll);
	}
	for (int p = 1; p <= cntroom; p++)
		for (int i = 1; i <= cntroom; i++)	
			for (int j = 1; j <= cntroom; j++)
				dis[i][j] = min(dis[i][j], dis[i][p] + dis[p][j]);
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= m; j++)
			f[i][j][0] = f[i][j][1] = INF;
	f[1][0][0] = f[1][1][1] = 0;
	for (int i = 2; i <= n; i++) f[i][0][0] = f[i - 1][0][0] + dis[c[i - 1]][c[i]];
	for (int i = 2; i <= n; i++)
		for (int j = 1; j <= min(i, m); j++) {
			f[i][j][0] = min(f[i - 1][j][0] + dis[c[i - 1]][c[i]], f[i - 1][j][1] + dis[d[i - 1]][c[i]] * k[i - 1] + dis[c[i - 1]][c[i]] * (1 - k[i - 1]));
			f[i][j][1] = min(f[i - 1][j - 1][0] + dis[c[i - 1]][d[i]] * k[i] + dis[c[i - 1]][c[i]] * (1 - k[i]), f[i - 1][j - 1][1] + dis[d[i - 1]][d[i]] * k[i - 1] * k[i] + dis[d[i - 1]][c[i]]* k[i - 1] * (1 - k[i]) + dis[c[i - 1]][d[i]] * (1 - k[i - 1]) * k[i] + dis[c[i - 1]][c[i]] * (1 - k[i - 1]) * (1 - k[i]));
		}
	double ans = INF;
	for (int i = 0; i <= m; i++) ans = min(ans, min(f[n][i][0], f[n][i][1]));
	printf("%.2lf\n", ans);
	return 0;
}

参考资料

蒙提霍尔问题（又称三门问题、山羊汽车问题）的正解是什么？ - 知乎

第一章, 随机事件 - 帅爆太阳的男人

概率与期望及其应用 - 曹文

全概率公式、贝叶斯公式推导过程 - ohshit

标签：概率,frac,1.1,笔记,times,事件,空门,期望
From： https://www.cnblogs.com/shiranui/p/16858780.html

相关文章

  • Vue + Vite + Ts 学习笔记
    1、环境安装#创建项目$npminitvitevue-vite-tsNeedtoinstallthefollowingpackages:[email protected]?(y)y√Selectaframework:»V......
  • 2个一维随机变量的关系的分布和一维变量的2种概率密度的乘积
    令一维变量分别为X1 和X2，概率密度函数分别为f1(x1)和f2(x2)，分布为F1(x1)和F2(x2)。1. 2个一维变量分布（或概率密度）的乘积【=f1(x1)*f2(x2) 】为分量独立的......
  • 笔记3（房产管理）
    1.使用js判断并且跳转到别的jsp页面。可以先写一个function，然后直接调用$("#loginBtn").click(function(){vartype=$("#type").val();var......
  • 图数据挖掘：级联的概率模型和疾病传播
    1导引在上一篇博客《图数据挖掘：网络中的级联行为》中介绍了用基于决策的模型来对级联行为进行建模，该模型是基于效用(Utility)的且是是确定性的，主要关注于单个节点如何根......
  • Agda学习笔记1
    目录Agda学习笔记1快捷键reflNaturalNumber自然数集合operationsrewritecong加法结合律加法交换律乘法分配律比较大小衍生的一些证明begin-qed作业题乘法交换律乘法结合律......
  • 《Unix/Linux系统编程》学习笔记10
    第十二章块设备I/O和缓冲区管理一、知识点归纳（一）块设备I/O缓冲区  在第11章中，我们学习了读写普通文件的算法。这些算法依赖于两个关键操作，即get_block和put_b......
  • MyBatis笔记03------XXXMapper.xml文件解析
    SQL映射文件的配置解析 当我们写好mapper(dao)层接口时，然后在对应的XXXMapper.xml文件中写业务逻辑对应的SQL映射语句，通过这个文件中可以实现CRU操作，那么下面说明如何编......
  • SpringCloud学习笔记
    一、服务注册中心Eurekaeureka-client服务发现：从注册中心上获取服务信息服务注册：将服务信息注册进注册中心依赖引入<!--EurekaClient端依赖-->......
  • 数据分析--学习笔记01
    python数据分析python数据分析工具包Numpy,SciPy.org,matplotlib,lean,pandas,k学习方法：重视理论--》勤于查阅--》身体力行--》联系实际数据获取手段数据仓库将所......
  • kali使用笔记
    当前Kali版本#lsb_release-aNoLSBmodulesareavailable.DistributorID:KaliDescription:KaliGNU/LinuxRollingRelease:2022.2Codename:kali-ro......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99