概率, 期望及习题

  • 做这篇文章的目的其实就是防止自己在日后的题目下懵逼, 而做了一些总结, 结果如下…

先举个很简单的例子 : (某射击比赛)

选手名字 shooting 1 shooting 2
d1t 9 8
d2t 10 7
d3t 7 8

\ \ \ \ \ \ \ 我们可以知道对于射击次数相同的事件来说, 一个人的命中环数越多, 在某种意义下来说可以认为是水平越高, 但是我们需要注意这种命中总环数并不是一个特征量, 比如在100次射击中命中90环, 而在10次射击中命中了60环, 而我们这次显然不能通过总环数来比较一个人的水平高低

\ \ \ \ \ 但是平均数却可以做到这一点, 我们可以将射中某环数的次数转化成概率, 而将一张统计表转化成分布律图, 那么平均值也就是 \sum_xx_i\cdot p_i

概率

概率就是对事情发生的可能性的度量

研究题目的背景如下, 小丁有一个不透光的袋子, 内部有3个黄球, 2个红球, 2个绿球, 1个蓝球, 问拿出黄球的概率?

首先, 先声明一些变量

  • 样本空间(Sample\ Space): 对于某事件所有可能结果的集合(例子中袋子里的球)
  • 试验(trial) : (尝试从袋子中取出一个球)
  • 互斥( Mutually \ exclusive ): 如果两件事物互斥, 也意味着它们不可能同时发生Pr(X\ or \ Y)=Pr(X)+Pr(Y)
  • 独立事件(independte\ events): 互相独立, 一件事情的发生并不会影响下一件事情

\ \ \ \ \ \ 关于概率这一方面, 我们往往是被弄得晕头转向, 所以在这里我们往往需要规范或者疏导一下思路, 再此直接引用论文中的例子: 如某A大学的男女比例为 99: 1, 而B大学的是 1:99, 在两所学校人数相同的情况之下, 那么从两所大学中的人取出一个人, 是男生的概率是多少?

不难发现, 总的来看, 男女比例就是1 : 1, 所以答案就是 50%, 但是当我们得知如果他是A大学的, 那么概率就变成了99%, 可见当知道了更多的信息, 事件发生的概率是会变化的! 于是我们引入Pr[A|B]的概念, 表示在B事件已经发生的情况之下, A事件发生的概率是多少.

  • Pr[A|B]=\frac{Pr[AB] }{Pr[B]} {Pr[AB]=Pr[A\cap B]}

全概率公式

假设S是对全集的一个划分, 即s_1\cup s_2\cup…\cup s_{|S|} 是全集

那么有
Pr[A]=\sum_{i=1}^{|S|}Pr[A|s_i]\cdot Pr[s_i]

Bayes 公式

我们拆解一下公式会有Pr[A|B]\cdot Pr[B]=Pr[B|A]\cdot Pr[A]

于是就有了:
Pr[A|B]=\frac{Pr[B|A]\cdot Pr[A]}{Pr[B]}

Pr[A_k|B]=\frac{Pr[B|A_k]Pr[A_k]}{\sum_iPr[B|A_i]\cdot Pr[A_i]}

接着, 我们要声明随机变量\chi的概念:

它其实并不能够算得上是一个变量, 它把我们从随机化过程带到了实际数世界

it’s\ just \ function \ mapping…

也就是随机试验的各种结果的实值函数 随机事件不论与数量是否直接有关,都可以数量化,即都能用数量化的方式表达

随机变量分为 离散型变量( discrete \ random )和连续型变量(continuous\ random)

离散型: 即取值(结果)是有限的, 以 1 的总概率分布在各个事件中

连续型: 取值无限


Pr(X\leq x)\begin{cases} \sum_{y:y\leq x} Pr(y)& discrete\\ \int_{-\infty}^xPr(y){\rm d}y& continuous \\ \end{cases}

期望相关

概率论统计学中,一个离散性随机变量期望值是试验中每次可能的结果乘以其结果概率的总和

E[\chi]=\sum_xPr(\chi=x)\cdot x, 也可以理解为是加权平均

个人理解: 这里的\chi依旧是随机变量, 而E这个变换规则只是声明了随着这个变量的不断”随机”而最后的加权平均值罢了…

具有以下性质:

  1. If \ c\ is\ a \ constant, E [c] = c.
  2. If \ a\ and\ b\ are\ constants, E [aX + b] = a\cdot E [X] + b. 这证明了对于一个变量的期望的线性
  3. E[g(X)]=\sum_xg(x) \cdot Pr(X=x)
  • 那么我们接下来再继续思考一下, 如果两个随机变量X, Y 会有什么好玩的反应

\begin{aligned} E [X + Y ] &= \sum_{x,y} (x + y)Pr (X = x, Y = y) \tag{1}\\ &= \sum_{x,y} x\cdot Pr (X = x, Y = y)+\sum_{x,y} y\cdot Pr (X = x, Y = y) \\ &=\sum_{x} x\cdot \sum_yPr (X = x, Y = y)+\sum_{y} y\cdot \sum_xPr (X = x, Y = y) \end{aligned}\\ by \ total\ probability,\sum_yPr (X = x, Y = y)=Pr(X=x),\\ and \sum_xPr (X = x, Y = y)=Pr(Y=y)\\

于是我们就有了:

\begin{aligned} E [X + Y ] &= \sum_{x} x\cdot Pr(X=x)+\sum_{y} y\cdot Pr (Y = y)\\ &=E[X]+E[Y]\\ \end{aligned}\\
4. (if X, Y independent) E[XY]=E[X]\cdot E[Y], (自己利用类似与E[X+Y]=E[X]+ E[Y]).

\ \ \ \ \ \ 而且通过上面的式子的推导过程之中我们发现了, 其实对于随机变量X, Y 并不需要两者的关系是互斥的, 因为我们利用到了就是: \sum_yPr (X = x, Y = y)=Pr(X=x), 这与X, Y的关系如何并无关系, 只是知道离散型随机变量是以总的 100% 的概率随机分配再每个结果中的!

这下, 都可以看出这就像Mean(平均值)一样的…

下面再来说一下方差(variance), 方差就是 (E(X)-X)^2 的期望, 记为Var(X).

同上, 既然是期望, 我们也可以轻松得到了定义式: Var(X)=\sum_xPr(X=x)\cdot(x-E(X))^2.

同时, 它也有一些类似上述的公式. 根据定义, 我们有:
\begin{aligned} Var[X]&=E[(X-E[X])^2]\\ &=E[X^2-2XE[X]+(E[X])^2]\\ &=E[X^2]-E[2XE[X]]+E[(E[X])^2] \end{aligned}
此时我们注意到其实E(X)俨然变成了一个constant, 那么我们可以进一步转化
\begin{aligned} Var[X]&=E[X^2]-E[2XE[X]]+E[(E[X])^2]\\ &=E[X^2]-2E[x]\cdot E[x] + (E[x])^2\\ &=E[X^2]-E^2[X] \end{aligned}
稍微完善一下, 有

  • Var[X+c]=Var[X]
  • Var[aX]=a^2Var[X]

自己去推好了, 博主懒…

tips: 利用刚刚证明的关于Var[X]的式子

It’s not generally true that Var (X + Y ) = Var (X) + Var (Y ); we’ll see when
it’s true later.

还有就是如果两件事情是独立的, 那么我们显然有
Pr(x=X,y=Y)=Pr(x=X)\cdot Pr(y=Y)
而且有E[XY]=E[X]\cdot E[Y].

那么联系Var[X], 与E[X], 什么时候才有Var[X+Y]=Var[X]+Var[Y]?

经过推导(略) Var[X+Y]=Var[X]+Var[Y]+2E[XY]-2E[X]\cdot E[Y] 那么我们可以显然看出来, 当两件事情是独立事件的时候, 那么我们就会有
Var[X+Y]=Var[X]+Var[Y]

二项分布

emmm. 一句话带过好了, 就是概率是与二项式系数有关的, 如

  • flip 5 coins, the probablity that you get 3 heads equals Pr=(\frac 1 2) ^{\binom 5 3}

So … Prob[X=x]=\binom n xp^x(1-p)^{n-x} 超简单, 逃

习题

那…接下来就会将一些题目, 再在中间穿插一些公式, 重点是培养期望的感觉

No.1 CF123 E

题意:

一个迷宫是一棵树(即一张无向图,其中任意两点之间仅有一条路径)

迷宫的起点和终点都按照某种概率选取, 人们会在迷宫中用深度优先搜索的方法搜寻终点.

如果有许多条可能的路径,会等概率地选取一条未访问过的路径

考虑如下伪代码:

DFS(x)
    if x == exit vertex then
        finish search
    flag[x] <- TRUE
    random shuffle the vertices' order in V(x) // here all permutations have equal probability to be chosen
    for i <- 1 to length[V] do
        if flag[V[i]] = FALSE then
            count++;
            DFS(y);
    count++

求期望边数

分析

好…绕的题面

好….dark的期望….

\ \ \ \ \ \ \ \ 我会尽量分析的详细一点的, 尽量让大家入门, 我们首先来分析一下单考虑起, 终点为S, T的情况是怎么样的. 不难发现, 就是求E[X], X表示S -> T的搜索路径上经过的边数, 即X这个实值函数表示的意思是对于每一个搜索路径的局面, 返回的值是经过的边数, 那么我们设原来的边集是e, 那么设Y_i 这个随机变量表示第i条边在某一个局面取或者不取, 那么我们可以得到两个的关系式:

\begin{aligned} E[X]&=E[\sum_{i=1}^{|e|}Y_i]\\ &=\sum_{i=1}^{|e|}E[Y_i] \ \ \ by\ linear\ property\\ \end{aligned}
那么就转换成了每一条边在S, T 的众多搜索局面之中是否被经过的期望次数:

以下讨论以S为根来阐述, 结果不影响但方便表述

  • 这一条边是必经路上的边, 那么我们会发现, 这种边有且仅会被经过一次, 因为考虑搜索过程无论一开始是怎么样的, 一定要经过这一条边, 而且经过这条遍之后一定不需要回溯, 因为已经可以枚举到了T
  • 考虑不在必经路上的边集, 那么我们假设需要下阶段经过的必经路上的边是第i条边(u-w), 而且假设最接近必经路上的点是u, 经过它的儿子v, 也就是说第i条边与u相邻, 那么我们考虑如果在枚举第i条边之前搜索到了v, 那么我们会对它进行访问, 否则不会.

换句话来说就是如果搜索时w在u前, 则不会枚举到, 否则, 就会经过2次!

那么我们来算一算概率, 不难发现, 经过u这个节点的概率是1(必经过), 那么也就是说, 概率就是”五五开” 的局面, 期望同样是0.5\cdot 0+0.5\cdot 2=1 那么这个神奇的结论告诉我们, 在S->T的搜索路径上, 设可能经过n条边, 那么E[X]=n​

当然, 会有一些边是永远不会枚举的, 那就是T的子树一部分

接下来讲解法:

我们可以在一遍dfs中就求出答案, 假设我们令当前枚举的节点u作为终点, 那么如果起点在u的子树内, 我们就会发现,

中途有一点我们需要说明的就是对于一个拓扑图形状的期望题来说, 当前节点的期望相当于是所有后继节点的概率乘上它的期望, 如图所示

其实解释的话我们可以考虑期望的定义是结果乘上期望, 那么yy一下就可以解释这个命题了!

文中牵扯到的链接可能需要到 wiki 上查找…

或者可以参考可汗学院的视频… 在网易公开课上哦 🙂

参考文献

该博文Markdown下载

Made \ By\ Bartholomew…

发表评论

电子邮件地址不会被公开。 必填项已用*标注