概率简介
概率,是我们日常生活中的常见概念。
它可以实际的理解为一个事情发生的频率。
例如:
筛(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))。
条件概率
记在(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)
显然(sum^{k=0}_n P(B_{j,k}))构成(P(A_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)的概率如果不考虑之前的路线,就是等价的。而之前的情况,已经在期望里推过了。
文章来源: 博客园
- 还没有人评论,欢迎说说您的想法!