概率简介

概率,是我们日常生活中的常见概念。
它可以实际的理解为一个事情发生的频率。

例如:
(30)次色子,(4)次筛出(10)
我们就可以认为筛出(4)的频率,即筛出(4)这一事件的概率为(frac{10}{30}=frac{1}{3})
显然当筛的次数较小时,其频率会有相对大的起伏。
但随着筛的次数的增大,其频率就会逐渐趋向于稳定,并最终变为一个定值。

因此这引出了我们对于概念的定义:
我们定义一个随机变量(x)的概率为(=frac{x发生的次数}{总实验次数})
记做(P(x))
严谨来说,事件的概率会是一个定值,且是由上述很多个简单到无法继续分解的互斥(即(A)发生时(B)不发生,(B)发生时(A)不发生)随机变量组成的。

加法法则

公式:
(P(A cup B)=P(A)+P(B)-P(AB))
推论:
对于互斥事件(A)(B)(即(Acap B=phi))。
有:
(P(AB)=0)
(P(A cup B)=P(A)+P(B))

[tips:P(A cup B)至少有一个发生的概率。 ]

[P(A cap B)=P(AB)两者全都发生的概率。 ]

条件概率

记在(B)发生的条件下(A)发生的概率,记为:(P(A|B))
额外:
(A)(B)无关时,(P(A|B)=P(A))
公式:
(P(A|B)=frac{P(AB)}{P(B)}(P(B)neq 0))
推论(乘法法则):
(P(AB)=P(A|B)times P(B)=P(B|A)times P(A))

乘法法则

见上:
(P(AB)=P(A|B)times P(B)=P(B|A)times P(A))

全概率公式

设有互斥事件(A_1)~(A_n)。若(sum_{i=1}^n A_i=Omega)(称(A)构成一个完备事件组)
则对于任一事件(B)有公式:
(P(B)=sum_{i=1}^n P(B|A_i)times P(A_i))
(感性的理解为所有情况下(B)发生的概率)

OI概率应用

知名(OIer)鲁迅曾经曾经说过鲁迅:我没说过

概率顺推,期望逆推。

这并非没有道理的。
以下是概率问题的推导:

题面

给出一张(n)个点(m)条边的有向无环图,起点为(1),终点为(n),并且从起点出发能够到达所有的点,所有的点也都能够到达终点。

(hhx)从起点出发,走向终点。到达每一个顶点时,如果该节点有(k)条出边,(hhx)可以选择任意一条边离开该点,并且走向每条边的概率为(frac{1}{k})。现在(hhx)想知道,经过每个节点的概率是多少?

顺推

设事件(A_i)为经过(i)
考虑递推,很容易想到将(P(A_i))用全概率公式展开给入边点集。
但是一个痛苦的问题是入边的点之间可能相互有连边,并不互斥。
考虑添加限制使其互斥。
设事件(B_{j,k})为第(k)步到(j)
此时(B)事件互斥。
推导:
首先展开给入边点集,然后枚举(k)展开给每一步。
我们考虑(k)的边界情况:
(k=0):不可能走到非起点节点。即(P(B_{j,0}=0))
(k=n): 在最差情况为一条链时,任不可能走到任意节点。即(P(B_{j,n})=0)
所以(forall 1leq kleq n-1)等价于(forall 0leq kleq n)

[P(A_i)=sum^{jin IN_i}sum^{k=0}_n P(B_{j,k})times frac{1}{OUT_j} ]

显然(sum^{k=0}_n P(B_{j,k}))构成(P(A_j))

[=sum^{jin IN_i}P(A_j)times frac{1}{OUT_j} ]

倒推

倒推就显得很不靠谱了。
关键的点在于所求的概率的事件为经过而并非去终点,因此无法推导和确定状态。

期望简介

期望可以理解为实验结果的平均权,也可以理解为带权概率和。
感性的理解为某个权在结果中的情况占比的贡献之和。
这也引出了期望的定义式:
对于某随机变量(x),记其期望为(E(x))
(E(x)=P(x)times w)(其中(w)为权)。

期望的线性性

期望的线性性指的是两个随机变量(X)(Y)
(E(X+Y)=E(X)+E(Y))
对于额外的常数(k),也有(E(ktimes X)=ktimes E(X))
性感的理解这个性质,这里的(E(X+Y))不是交集,也不是并集,可以看做两个单独的事件(尽管他们可能并不互斥)。而期望是个权,权是可以相加的,而这也是概率不具备线性性的原因:他们会互相影响。

条件概率

记在(B)发生的条件下(A)发生的期望,记为:(E(A|B))
易知有(E(A|B)=frac{E(A)}{P(B)})
移项得:
(E(A|B)times P(B)=E(A))

全期望公式

对于事件(X)
(E(X)=P(X)times w)
用全概率公式展开,有:
(sum^{i=1}_n B_i构成一个完备事件组)
(E(X)=sum^{i=1}_n P(B_i)times P(X|B_i)times w)
这一步可以感性理解为(w)只于(X)有关,而(P(X|B_i))相当于又补了个概率:
(E(X)=sum^{i=1}_n P(B_i)times E(X|B_i))

OI期望应用

题面

给出一张(n)个点(m)条边的有向无环图,起点为(1),终点为(n),并且从起点出发能够到达所有的点,所有的点也都能够到达终点。

(hhx)从起点出发,走向终点。到达每一个顶点时,如果该节点有(k)条出边,(hhx)可以选择任意一条边离开该点,并且走向每条边的概率为(frac{1}{k})。现在(hhx)想知道,到达终点经过的边数的期望是多少?

顺推

(A_i)为起点到(i)的步数,(B_{j,k})(k)步走到(j)
其中(k)的范围在概率已经证过,不再赘述。
(E(A_i)=sum^{k=0}_nktimes P(B_{i,k}))
用之前的概率公式展开得:
(E(A_i)=sum^{k=0}_n sum^{j in OUT_i}(ktimes frac{P(B_{j,k})}{OUT_j}+frac{P(B_{j,k})}{OUT_j}))
(E(A_i)=sum^{j in OUT_i}frac{E(A_j)+P(A_j)}{OUT_j})
然而这样并不方便,因为我们还要求一个概率,这使我们的难度和码量翻倍。

倒推

(A_i)为到终点的步数(B_{j,i}为j一步到i)
则有:
(E(A_i)=sum^{j in IN_i} P(B_{j,i})times E(A_i|B_{j,i}))
(E(A_i)=sum^{j in IN_i} frac{E(A_j)+1}{IN_i})
(E(A_i)=frac{sum^{j in IN_i} E(A_j)}{IN_i}+1)
(tips:)关于这里的概率可能有人觉得不对,应该用(frac{到j方案数}{总方案数})但其实,从(j)(i)的概率如果不考虑之前的路线,就是等价的。而之前的情况,已经在期望里推过了。

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/everyday2023/p/17234302.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!