专题·数学概率与期望【including 条件概率，叶贝斯定理， 全概率公式，数学期望， 绿豆蛙的归宿

初见安~~~又开启数论的探索啦~~：）

一。概率

1.基本定义

在概率论中，我们把一个随机事件的一个可能结果称为其样本点，其所有样本点构成的集合称之为样本空间。（注意，随机事件并不一定只有一种可能结果）在样本空间中，我们称事件所包含的子集为随机事件。

概率的定义就很简单了，我们也都知道样本空间中的任意随机事件的概率不会超过1不会小于0.

就比如我们抛硬币连续扔三次（不考虑侧面稳落地），有8中可能：AAA，AAB，ABB，BAA，BBA， ABA， BAB， BBB。对于这个大小为8样本空间，事件A“至少有两次正面朝上”的可能为：AAA，AAB，ABA，BAA 4种。所以P（A）= 0.5 。

 

2.叶贝斯定理

其中，P（A | B）是指在事件B发生的前提下事件A发生的概率。也就是条件概率。

这个定理怎么证明呢~会利用到一个叫做条件概率公式的东西。

两式整理即可得到叶贝斯定理。

可能这两个式子（当然原理就是一个）不太好理解，这里我们也区分一下：

P( A | B), P( B | A)和P（AB）的区别。

首先P（ＡＢ）也就是图中ＡＢ相交的部分的概率了。

对于Ｐ（Ｂ｜Ａ），首先得确保Ａ事件发生，再者才是Ｂ事件，也就是说必须是在Ｐ（A）的前提下发生P（ＡＢ），所以Ｐ（Ｂ｜Ａ）相当于是在Ｐ（A）中发生Ｐ（ＡＢ）的概率，套用我们之前对于概率的认识，所以就有了Ｐ（Ｂ｜Ａ）＝P（ＡＢ）／P（A）。如果这样都理解不了的话，那就把等式移项成乘法，应该一眼就懂了。

所以这三个变量一般情况下是不相等的，如果ＡＢ有包含的关系才可能存在某两个量相等。

３.全概率公式

把样本空间划分成若干个不相交的部分Ｂ１，Ｂ２，……，Ｂｎ；则有：

证明方法类似于乘法分配律，就不解释了：）以上基本上都是数学理论基础。

 

二。数学期望

1.定义

随机变量x的期望值E（x）为其所有可能值乘上其概率的和。

2.公式

期望是线性规划，所以这个公式是满足的：

这个公式其实非常方便，很多时候也并不是直接套用公式，化用的情况更多，比如下面这个例题——

3.绿豆蛙的归宿

题目来自洛谷P4316

题目描述

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

输入格式：

第一行: 两个整数 N M，代表图中有N个点、M条边 第二行到第 1+M 行: 每行3个整数 a b c，代表从a到b有一条长度为c的有向边

输出格式：

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

输入样例： 

4 4 
1 2 1 
1 3 2 
2 3 3 
3 4 4

输出样例： 

7.00

说明

对于100%的数据 N<=100000，M<=2*N

 

题解

求期望的题可能一般考的就是你怎么求而不是反应过来要求。这道题的话要求从1出发走到n的路径长度的期望值，看似我们需要枚举各个路并计算出值最后来求期望，看到 N <= 100000 的时候相信你也明白了绝对不能这么做。

我们试着模拟一下——从1出发，经过各个点，再从各个点发散出路——是不是想到什么了！！（反正我当时没有）如果我们先看期望，会发现：如果各个路径长度的概率是一样的，那么我们求的期望就是各个路径之和的平均值。尽管我们可能会遇到同一长度多次出现，我们也多次计算即可。所以这道题就跟概率没什么关系了——我们需要思考的只是怎么维护各个路径的长度来计算期望。

如果我们设dis[ x ]表示从x到n的路径长度，那么一个变量的位置绝对存不下；存路径之和是行得通的，但是题目并没有说路径长度的范围，所以很有可能一累加就RE了，所以我们最后采取得方法是——边找边算期望边累加。这一思路是基于期望的定义的，加之我们视其等概率不计出现次数，在乘法分配律下求平均值就可以了。

按照我们对dis的定义，我们要求的是dis[ 1 ]。所以要从点n开始找，建一个反图（但是每个点连出去的k条边的存储不能反过来），拓扑遍历即可。

下面就是代码及详解啦！！！！——

#include<bits/stdc++.h>//参考lyd代码
#define maxn 100005
using namespace std;
int n, m, in[maxn], deg[maxn];
struct edge//邻接表
{
	int to, far, nxt;
	edge(){}
	edge(int tt, int ff, int nn)
	{
		to = tt; far = ff; nxt = nn;
	}
	
}e[maxn << 2];

queue<int> q;
double dis[maxn];

int head[maxn], k = 0; 
void add(int u, int v, int w)
{
	e[k] = edge(v, w, head[u]);
	head[u] = k++;
}

int main()
{
	memset(head, -1, sizeof head);
	scanf("%d%d", &n, &m);
	int a, b, c;
	for(int i = 1; i <= m; i++)
	{
		scanf("%d%d%d", &a, &b, &c);
		add(b, a, c);
		in[a]++; deg[a]++;//in反，deg正
	}
	
	q.push(n);
	
	while(q.size())
	{
		int x = q.front();
		q.pop();
		for(int i = head[x]; ~i ;i = e[i].nxt)
		{
			int y = e[i].to;
			dis[y] += (e[i].far + dis[x]) / deg[y];//反图中y是入读，事实上是出度
			in[y]--;
			if(!in[y]) q.push(y);//拓扑
		}
	}
	
	printf("%.2f\n", dis[1]);
	return 0;
}

简洁的清新脱俗~

做的题多了你就会发现其实期望只是一个概念，很多时候求期望都是要用到动态规划的。（所以回去刷动规一百题吧。

迎评：）
——End——