概率基础

前言

最近连续几天看了一些概率的东西,也做了几题。
颇有些感触,也有些伤感(伤感?)。。。咳咳,跑题了。

全概率公式

假设 是一个概率空间的有限或者可数无限的分割。
且每个集合Bn 是一个可测集合。
则对任意事件A 有全概率公式:

其中P(A | Bn)是Bn 发生后A 的条件概率。
这句话是汤可因说的,其实也是比较容易理解的。

举个例子:

全期望公式

和条件概率类似,当时,Y的条件数学期望用表示。

全期望公式:

(中间过程略)

其实和全概率公式类似,举个例子:

usaco猪猡

什么叫猪猡?他有一个简称,就是猪。

题意:给你一个无向图,炸弹放在一号节点,每一单位的时间内,有P的概率爆炸,否则等概率的走向某个邻点。

以下有两种状态的设计:
(1) 表示从1出发到达i的概率。
(2) 表示从1出发到达i并在i处爆炸的概率。

这两种状态表示都是可以的,列方程后,小心一下实数的精度问题就可以了。

我的疑问是:
如果选择第(1)种状态,那么的值是大于1的,这似乎无法理解。

到了后来我再想一下,我们是不是可以这样理解:
从1出发到达i,这样的状态本来就是由若干个互不相斥、互相包含的事件组成。
那么他们的概率相加大于1,也就可以理解了。?

tyvj1953 normal

点解叫normal?
因为他的难度就很normal啊。
这题出自陈立杰先生的noip模拟赛。
QQ截图20140702152345.png
陈立杰先生很友好的留下了hint
QQ截图20140702152624.png

真是很有用的信息呢。

和很多蒟蒻一样,看完题目后,我便发现这道题没有办法写暴力。
也和很多蒟蒻一样,我第一反应就是找题解。

我们其实可以把问题转化成:
随机选取一个未标记的点将其标记。
并从此点出发遍历所有未标记的点。
累加遍历的点数,所有点被标记时结束,问总值的期望值。

我们发现,在点a删除时,点b对点a有1的贡献,当且仅当在a到b的路径上,a是第一个被删除的。
显然,路径上每个点被首删的概率是相同的。

所以他对期望值的贡献就是:

那么我们也可以得出:

dis(u,v)就是u到v的路径上的点数。

那么有以下两个算法:
(1) 暴力,
(2)点分治+FFT,

NOI2006 神奇的口袋

QQ图片20140704220944.jpg
其实从上一道题开始,概率题就不再是简单的在一个有向图上面走来走去,
缩缩点啊,
列列方程啊,
分分层啊,
就可以解决的。

但显然我还不适应这种节奏,总结了一下,要做出这种题目,无非要做好以下三点:
(1)认真理解。
(2)努力思考。
(3)百度一下。

但当我问起一个本校屌丝师兄的时候,
他居然这样回答:
QQ图片20140704214827.jpg
我想我可以退役了。。。不,应该说:
QQ截图20140704215836.png

你好棒耶!

怎么办?
那我只能给下一位看我题解的人说一句:
这TM在逗我?这么简单你也不会做?

那么接下来是对此题的讲解:希望你们有耐心看完吧~
解决此题,主要是要知道:随机抽球后每个球被抽到的概率不变。

证明(伪证明?):
针对一种颜色,定义:
为第i次抽球时抽到此颜色的概率。
为第i次抽球时(不是抽球后),此颜色的期望球数。
表示第i次抽球时的总球数。
一个命题:

证明:

有了这个,我们解题就得心应手了,随机取球不改变抽球概率。
那么第一次定向取球后,该颜色被抽中的该概率又变为多少?

那该死的的屌丝师兄拍拍我的后肩:想太多了。

QQ图片20140708114057.png

comments powered by Disqus