概率与数学期望

文章目录

• 概率与数学期望
• • 引入
  • • 期望
    • 概率 DP
    • • DP 求概率
      • DP 求期望
  • 例题
  • • 绿豆蛙的归宿
    • • 思路
      • 代码
    • 扑克牌
    • • 思路
      • 代码

引入

期望

离散型随机变量
设离散型随机变量 X 的概率分布为 pi=P{X=xi}p_i = P\{ X = x_i \}pi​=P{X=xi​}，若和式
∑xipi\sum x_i p_i∑xi​pi​绝对收敛，则称其值为 X 的 期望，记作 E(X)E(X)E(X)。
连续型随机变量
设连续型随机变量 X 的密度函数为 f(x)。若积分∫Rxf(x)dx\int_{\mathbb{R}} xf(x) \text{d} x∫R​xf(x)dx绝对收敛，则称其值为 X 的 期望，记作 E(X)E(X)E(X)
期望的性质
线性性
若随机变量 X, Y 的期望存在，则

对任意实数 a, b，有 E(aX+b)=a⋅E(X)+bE(aX + b) = a \cdot E(X) + bE(aX+b)=a⋅E(X)+b。
E(X+Y)=E(X)+E(Y)E(X + Y) = E(X) + E(Y)E(X+Y)=E(X)+E(Y)。
随机变量乘积的期望
若随机变量 X,Y 的期望存在且 X,Y 相互独立，则有E(XY)=E(X)⋅E(Y)E(XY) = E(X) · E(Y)E(XY)=E(X)⋅E(Y)

概率 DP

一般情况下，解决概率问题需要顺序循环，而解决期望问题使用逆序循环

DP 求概率

这类题目采用顺推，也就是从初始状态推向结果。同一般的 DP 类似的，难点依然是对状态转移方程的刻画，只是这类题目经过了概率论知识的包装。

DP 求期望

这类题目采用逆推，也就是从最终状态推向结果。难点在于建图，一般状态定义为从某个状态节点到最终状态的期望。

例题

绿豆蛙的归宿

给出一个有向无环的连通图，起点为 1，终点为 N，每条边都有一个长度。

数据保证从起点出发能够到达图中所有的点，图中所有的点也都能够到达终点。

绿豆蛙从起点出发，走向终点。

到达每一个顶点时，如果有 K 条离开该点的道路，绿豆蛙可以选择任意一条道路离开该点，并且走向每条路的概率为 1/K。
现在绿豆蛙想知道，从起点走到终点所经过的路径总长度的期望是多少？

输入格式
第一行: 两个整数 N，M，代表图中有 N 个点、M 条边。

第二行到第 1+M 行: 每行 3个整数 a,b,c，代表从 a 到 b 有一条长度为 c 的有向边。

输出格式
输出从起点到终点路径总长度的期望值，结果四舍五入保留两位小数。

数据范围
1≤N≤105,1≤M≤2N
输入样例：
4 4
1 2 1
1 3 2
2 3 3
3 4 4
输出样例：
7.00

思路

状态表示:f[i]
1. 集合：表示从i到终点n路径的集合
2. 属性：E(i)
状态计算：did_{i}di​表示节点有通向其他节点的路径数,wijw_{ij}wij​表示路径长度
f[i]=∑1di(f[j]+wij)f[i] = \sum \frac{1}{d_i}(f[j] + w_{ij})f[i]=∑di​1​(f[j]+wij​)

代码

'''
对于概率题，一般从后往前分析递推公式
状态表示f[i] :集合：从i点走到终点的路径集合数学：期望
状态计算：d表示走每条路的概率，j表示可以通向的节点f[i] = sum(d * (f[j] + w_j))
'''
import syssys.setrecursionlimit(6000)N = 100010
M = N * 2h = [-1] * N
e = [0] * M
w = [0] * M
ne = [-1] * M
idx = 0
d = [0] * N
f = [-1] * Ndef add(a, b, c) :global idxe[idx] = bw[idx] = cne[idx] = h[a]h[a] = idxidx += 1def dfs(u) :if f[u] != -1 : return f[u]f[u] = 0i = h[u]while ~ i :j = e[i]f[u] += 1 / d[u] * (w[i] + dfs(j))i = ne[i]return f[u]n, m = map(int, input().split())for i in range(m) :a, b, c = map(int, input().split())add(a, b, c)d[a] += 1print(f"{dfs(1):.2f}")

扑克牌

Admin 生日那天，Rainbow 来找 Admin 玩扑克牌。玩着玩着 Rainbow 觉得太没意思了，于是决定给 Admin 一个考验。Rainbow 把一副扑克牌(54 张)随机洗开，倒扣着放成一摞。
然后 Admin 从上往下依次翻开每张牌，每翻开一张黑桃、红桃、梅花或者方块，就把它放到对应花色的堆里去。
Rainbow 想问问 Admin，得到 A 张黑桃、B 张红桃、C 张梅花、D 张方块需要翻开的牌的张数的期望值 E 是多少？
特殊地，如果翻开的牌是大王或者小王，Admin 将会把它作为某种花色的牌放入对应堆中，使得放入之后 E 的值尽可能小。
由于 Admin 和 Rainbow 还在玩扑克，所以这个程序就交给你来写了。

输入格式
输入仅由一行，包含四个用空格隔开的整数，A,B,C,D。

输出格式
输出需要翻开的牌数的期望值 E，四舍五入保留 3 位小数。

如果不可能达到输入的状态，输出 -1.000。

数据范围
0≤A,B,C,D≤15
输入样例：
1 2 3 4
输出样例：
16.393

思路

状态表示：f[a, b, c, d, x, y]

1. 集合：表示黑桃、红桃、梅花、方块、大王、小王（放在哪个牌堆）取到的状态为(a, b, c, d, x, y)时，到达终点得到 A张黑桃、B 张红桃、C 张梅花、D 张方块的方案集合
2. 属性：最小数学期望
   状态计算：

代码

INF = 10000010
N = 14
f = [[[[[[-1] * 5 for _ in range(5)] for _ in range(N)] for _ in range(N)] for _ in range(N)] for _ in range(N)]def dfs(a, b, c, d, x, y) :if f[a][b][c][d][x][y] != -1: return f[a][b][c][d][x][y]# 记录a,b,c,d的牌堆As = a + (x == 0) + (y == 0)Bs = b + (x == 1) + (y == 1)Cs = c + (x == 2) + (y == 2)Ds = d + (x == 3) + (y == 3)if As >= A and Bs >= B and Cs >= C and Ds >= D : f[a][b][c][d][x][y] = 0return 0s = a + b + c + d +(x != 4) + (y != 4)s = 54 - sif s <= 0 : f[a][b][c][d][x][y] = INFreturn INFf[a][b][c][d][x][y] = 1if a < 13 : f[a][b][c][d][x][y] += (13 - a) / s * dfs(a + 1, b, c, d, x, y)if b < 13 : f[a][b][c][d][x][y] += (13 - b) / s * dfs(a, b + 1, c, d, x, y)if c < 13 : f[a][b][c][d][x][y] += (13 - c) / s * dfs(a, b, c + 1, d, x, y)if d < 13 : f[a][b][c][d][x][y] += (13 - d) / s * dfs(a, b, c, d + 1, x, y)if x == 4 :t = INFfor i in range(4) :t = min(t, 1/s * dfs(a, b, c, d, i, y))f[a][b][c][d][x][y] += tif y == 4 :t = INFfor i in range(4) :t = min(t, 1/s * dfs(a, b, c, d, x, i))f[a][b][c][d][x][y] += treturn f[a][b][c][d][x][y]A, B, C, D = map(int, input().split())res = dfs(0, 0, 0, 0, 4, 4)if res > INF / 2 :print(-1.000)
else : print(f"{res:.3f}")