Home
吐槽 源码研究 我的 算法挑战 网络 科学吧 文青 关于我

概率论笔记1

27 Jun 2013 by LelouchHe

初衷

最近看书看的比较勤,越发的感觉自己的弱小了,尤其在基础的数学知识方面,欠缺甚多.在看机器学习的时候,甚至都不知道贝叶斯是什么了,还有那个HMM,压根就不晓得是什么.

在基础数学领域,可能最需要巩固和加强的,就是概率与统计,线代,数分.所以在看代码,写算法的基础上,还要开辟一个纯数学的版面,来督促我这方面的学习

组合

组合数学的经典书应该是Brualdi的组合数学了,自然,我肯定学的还没有那么深入,这里就简单的介绍下概率计算的基础组合

基础

组合的基础应该是加法原理和乘法原理吧

可见,加法原理是针对整个实验来讲的,类似于并联电路,多条电路都通,最后相加即可,而乘法原理更针对实验内部的不同阶段,类似串联电路,需要一步一步的来操作,所以结果需要相乘.从实际的运用来讲,乘法原理更加广泛,需要额外的注意(当然,另一个原因是加法原理比较简单)

2个原理都可以推而广之到自然数集上,即存在r个实验.对于不可数集的情况,我就不清楚了

排列

排列(permutation)是比较基础的组合问题,也可以看作是乘法原理的应用.

有n个不同元素,标号从1到n.这n个元素的每一种不同的排序方式,就是一种排列.针对每个位置而言,位置1有n中选择,位置2有$n - 1$中选择(因为已经挑选了1个),依次类推.整个的排列是由这n个位置的决定而决定的,利用乘法原理,有

\[n (n - 1) (n - 2) \cdots = n ! \approx \sqrt {2 \pi n} (n / e) ^ n\]

不同排列总数就是$n !$,此处,还提供了一个经常用到的斯特灵近似公式,可以比较准确的估计阶乘的大小

刚才说的的不同元素.但是如果其中有不可区分元素则何如?其实很简单,首先不管其相似性,直接来计算排列,有$n !$种,然后根据不可区分性把重复的排列去掉,设有$r$个元素之间不可区分(元素标号从$n _ 1$到$n _ r$,共r个),这r个元素总共会产生$r !$个相同排列,那么最后的不同排列数就是$n ! / r !$.

之所以要用除法,是因为排列计算使用的是乘法原理.试想,按照原始的计算,这r个元素的每一种排列顺序(即在总排列中占有不同位置),都会带来$r !$种不同的排序(位置一致,只是r个元素间的交换,但这是不可区分的),这些额外排序都是作为乘法项并入总结果的,所以除掉即可(平时计算重复利用除法或者减法,其实也是乘法原理或加法原理的应用,只是不自知而已)

阶乘并不是什么好事情,一般意味着复杂度太大,计算量超多

组合

组合很像是上述讨论的那些不可区分元素,不过此时不可区分的是元素的位置.

有n个不同的元素,从中取出r个元素,第1个抽取有n中取法,第2个抽取有$n - 1$种取法,第i个抽取有$n - i$中取法,按照乘法原理,应该有$n (n - 1) (n - 2) \cdots (n - r)$中取法.不过,此处关心的仅仅是抽取出来,对于这r个元素的顺序是忽略的,或者叫不可区分的.按照刚才的讨论,这r个元素有$r !$种不同的排列,都被视为1个,所以需要除掉,得到

\[\binom{n}{r} = \frac{n (n - 1) \cdots (n - r)}{r !} = \frac{n !}{(n - r) ! r !}\]

此处引入了$\binom{n}{r}$记号作为n取r的组合.这个记号还被成为二项式系数,因为它出现在下面的等式中:

\[(x + y) ^ n = \sum _ {k = 0} ^ n \binom{n}{k} x ^ k y ^ {(n - k)}\]

刚好是二项展开的系数(好吧,其实不是刚好,从二项展开可以看到,试图获取$x ^ k$,其实就是从n个相乘的式子里选择k个x和$n - k$个y,这不就是上面的组合么?)

上面说的组合,是一种最为简单的组合,因为只挑选出一组r个作为不可区分的元素.假设我们要挑选s组,每组有$r_i$个元素,此时,根据乘法原理,不同的组合数有

\[\binom{n}{r _ 1, r _ 2 \cdots r _ s} = \frac{n !}{ (r _ 1) ! (r _ 2) ! \cdots (r _ s) !}\]

上式被称为”多项组合数”.其实这里”组”的概念很宽泛,不要把它想象成非要进行划分分组一样,只要在特定条件下,需要将元素当作相同而不区分,也就是只有数量关系,没有位置和元素关系时,都可以使用.可以看到,二项式系数就是多项组合数的特殊情况,只针对一个变量的数量关系

由二项式系数类比而来的一个公式,自然也是二项展开的扩展:

\[(x _ 1 + x _ 2 + \cdots + x _ r) ^ n = \sum _ {n _ 1 + n _ 2 + \cdots + n _ r = n} {x _ 1} ^ {n _ 1} {x _ 2} ^ {n _ 2} \cdots {x _ r} ^ {n _ r}\]

具体的求法还是可以按照二项展开的推理来进行,此处不赘言了.

有趣的角度

直接利用组合原理的问题,一般都是从原始集合中进行抽取,但是有一些问题的求解角度很有趣,通过变换,将一些本来不是组合的问题,变成组合可解的问题.

方程的正整数解

如下的方程,解为正整数,求其解的数目:

\[x _ 1 + x _ 2 + \cdots + x _ r = n\]

猛的一看,好像这个和组合没有关系,但是题目着重指出的一点–正整数解,指明了一个方向,即解其实就是1的组合,解由s个1组成,那么s就是方程的一个解.

这样,我们就把角度转移到了如何分配这n个1.假设有n个1并排放在平面上,分配问题其实转换为了切割问题,即如何在n个1中切$r - 1$刀,分成r份,那么每一份都由整数个1组成,而这显然就是问题的解.n个1,总共有$n - 1$个中间位置(切到外头,解就为0了,不满足题意;重复切割,中间的解就是0,也不满足提议),所以,此时的解的数量为$\binom{n - 1}{r - 1}$个

方程的非负整数解

如果上面的方程的解为非负数,怎么办?

这里,$n - 1$个中间位置的前提不成立了,因为我们可以切到外头,或者中间重复切割了.如果还是利用刚才的思路,就比较难找合适的分割位置了.

非要这样做的话,可以假设解为0的数量,设其为z

$z = 0$时,解有$\binom{n}{1} \binom{(n - 1) - 1}{(r - 1) - 1}$ $z = 1$时,解有$\binom{n}{2} \binom{(n - 2) - 1}{(r - 2) - 1}$

依次类推,直到$z = r$为止,然后相加即可(乘法原理和加法原理的使用)

当然,这个比较繁杂了,甚至利用了穷举的方法(“拿不准就穷举”).另一个角度也是利用变换,不过不是排除0值,而是将解提升.

设$y _ i = x _ i + 1$,因为$x _ ｉ\geq 0$,所以$y _ i \geq 1$为正整数,这样$y _ 1 + y _ 2 + \cdots + y _ r = n + r$,$y _ i$就是该方程的正整数解,解的数量(很快计算出)为$\binom{(n + r) - 1}{r - 1}$

看到了吧,这样有多快.

为什么可以这样

为什么可以这么神奇的解决呢?

一个很重要的原因在于处理的集合范围为自然数,自然数是处理很多问题的根基(比如是数学归纳法的前提之一).自然数有一个很好的特性是下限为0,另一个是相邻2个数必然差1,这样在可数的情况下,通过0/1的操作就能带来问题的变换,而保持解的唯一.试想,如果这些方程的解为整数(可正可负),怎么办?

下限是很多问题可以解决的关键,0作为下限,和1作为差值,都是问题求解的关键因素,以后的问题中,还会看到很多的