概率论01 计数

概率

概率论研究随机事件。它源于赌徒的研究。赌博中有许多随机事件,比如投掷一个骰子,是否只凭运气呢?

赌徒逐渐发现随机事件的规律。投掷两个骰子是常见的赌博游戏。如果重复很多次,那么总数为2的次数会比总数7的次数少。这就是赌徒把握到的规律:尽管我无法预知事件的具体结果,但我可以了解每种结果出现的可能性。这是概率论的核心。

“概率”到底是什么?这在数学上还有争议。“频率派”认为概率是重复尝试多次,某种结果出现的次数在尝试的总次数的比例。“贝叶斯派”认为概率是主观信念的强弱。幸好,这些争议并不影响我们在日常生活中使用“概率”哲学。天气预报的降雨概率为80%时,很多人会因此带上伞。报纸会分析一场球赛某支球队的赢球概率,如果最终赢球概率为10%的球队取胜,那么球迷会感到惊讶,这毕竟是小概率事件。

要知道某个结果的概率并不容易。上面分析球队的赢球概率,要考虑许多因素。投一个骰子,有6种可能的结果。许多原因会影响到结果,比如撒子是否均匀,比如掷撒子的人是否有技巧偏向。只有在骰子绝对均匀,且没有作弊,每种结果出现的概率才相同。否则的话,根本无法给结果一个确定的概率值。因此,为了能从数学上给结果分配一个概率,我们往往会给随机事件增加一些假设条件。这些条件有理想化的成份,但并不至于偏离现实。比如,我们说掷撒子,撒子均匀,掷的人也没有什么特殊手法,并由此推断每种结果出现的可能相同。那么,其中任意一个结果出现的概率为1/6。

基本计数原理

上面我们谈到了“等概率”的假设。如果每种结果出现的概率相同,那么给结果分配概率的任务就变得简单一些。在计算这种概率时,我们只需要等概率的结果的总数,就可以知道每种结果的概率。比如掷一个撒子会有6种结果,如果等概率,那么每个结果的概率为1/6。对于一些复杂的情况,就需要使用到计数技巧。

计数的基本原理叙述如下:

image.png

种可能的结果。

基本技术原理的核心是“分步”。对于简单的一个步骤的事情,我们能比较直接的分辨结果的总数。比如生一个孩子的性别,比如一个硬币的正反,比如一个撒子的结果。当一个随机事件是多个步骤复合而成的,而每个步骤又都是随机的,那么分布可以简化问题的复杂性。想像一个餐厅,有三个窗口,分别卖三种饮料,五种菜和两种主食。每个学生在每个窗口限选一种,那么学生的餐饮配套会有3x5x2共30种可能的结果。如果每个窗口的师傅都很随意霸道,随手给学生一样东西,那么我们甚至于可以假设等概率条件,每种餐饮拍套出现的概率为1/30。

(当然,作为学生,会抗议这样的“随机”食堂吧?)

基本计数原理的应用并不局限于概率论。在程序员进行算法分析时,无形中使用的就是进行计数。比如嵌套循环,外循环需要M步,内循环需要N步,那么总共进行操作的次数是MxN次。可以说,计数是“离散数学”非常重要的一个组成部分;而离散数学,正是计算机专业的核心数学课程。

基本计数原理是思考的起点。现实中的情况往往会更多变些。特别是当我们“分布”的动作都是作用于同一个群体时,会相对复杂。我们分类了解以下情形:

有序的重复抽样

考虑下面的两个问题:

  • 一个骰子连续掷2次,所有可能的结果有多少个?
  • 一个彩票可选6个号,每个号可以是0到9,共有多少个可能的结果?

我们可以看到,这一类的抽样结果是由多次抽样构成的。每次抽样的样本,在下一次也可能出现。比如骰子第一次为1,第二次还可能为1。这叫做重复抽样 (或者说有放回的抽样,sampling with replacement)。在骰子的例子中,每次抽样的可能出现的结果都有6种。

样本出现的次序影响结果。比如[$(1, 2)$]和[$(2, 1)$]是两个不同结果。

从数学上来说,如果进行m次有放回的抽样,每次抽样都有n种可能。如果最终结果有序,那么将有

n^m种可能。

我们下面模拟骰子的例子:

import itertools

a = [1, 2, 3, 4, 5, 6]
outcomes = list(itertools.product(a, a))

print(outcomes)
print(len(outcomes))

共返回36个可能的结果:

[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), 
 (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), 
 (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), 
 (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), 
 (5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6), 
 (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)]

36

如果每种结果的出现概率相同,那么对于其中的某个具体结果来说,它出现的概率[$P=1/36$]。

有序的非重复抽样

考虑下面两个问题:

  • 从4个人中,挑出2个人分别担任队长和副队长,有多少种可能?
  • 从10们课种,挑选3门,分别放入周一、周三、周五的课表,有多少种可能?

可以看到,这样的抽样是没有重复的。某一次抽样的样本在此后不会出现,前面一个步骤的动作减少了后面一个步骤的选择,这叫做非重复抽样。在非重复的前提下,每次抽样可能的结果数递减,比如从4个人中选一个作为队长,那么副队长只能从3个人中选择。

同样,结果是有序的。A担任队长,B担任副队长,与A担任副队长,B担任队长,是两个不同结果。

image.png

我们用下面的程序来模拟队长组合的状况:

import itertools

a = ["Tom", "Lee", "King", "James"]
outcomes = list(itertools.permutations(a, 2))

print(outcomes)
print(len(outcomes))

结果为

[('Tom', 'Lee'), ('Tom', 'King'), ('Tom', 'James'), 
 ('Lee', 'Tom'), ('Lee', 'King'), ('Lee', 'James'), 
 ('King', 'Tom'), ('King', 'Lee'), ('King', 'James'), 
 ('James', 'Tom'), ('James', 'Lee'), ('James', 'King')]

共有12种可能的结果。

无序的非重复抽样

考虑下面的问题:

  • 从4个人中抽出2个人,有多少种可能?
  • 从一副扑克中抽3张牌,有多少种可能?

在上面的问题中,每次抽样同样是非重复的。但这里,抽样结果是无序的。比如说,抽出"Lee"和"Tom",以及抽出"Tom"和"Lee",是同一个结果。这样的抽样方式叫做组合(combination)。

m个样品有[$m!$]种排列方式。如果是从n个样品中抽取m个作为组合,所有的这[$m!$]种排序方式应该看做一种。因此,有

image.png

我们下面来模拟第一个问题:

import itertools

a = ["Tom", "Lee", "King", "James"]
outcomes = list(itertools.combinations(a, 2))

print(outcomes)
print(len(outcomes))

有以下结果

[('Tom', 'Lee'), ('Tom', 'King'), ('Tom', 'James'),
 ('Lee', 'King'), ('Lee', 'James'),
 ('King', 'James')]

可以看到,从4个中挑选2个,有6种可能的组合。这是排列的一半。

image.png

无序的重复抽样

考虑下面的问题:

  • 刮奖彩票有4种奖品。购买3张彩票的话,有多少种中奖可能?

在上面的每次抽样中,都是重复抽样,即抽出后有放回。比如刮奖中,可以多次刮到同一奖品。我们在一个表中记录结果:

台灯

手表

电脑

汽车

可能1

3

0

0

0

可能2

2

0

1

0

可能3

0

1

1

1

可以看到,我们实际上是将3张彩票分成4份,每份的数目不定[$( \geq0 )$]。

这与下面的问题类似,将5个相同物品放入三个不同的容器中:

图片来源

我们用2个黑色分隔物,来将5个相同的物品分为3堆。比如这里,将物品分为(0, 2, 3)的结果。

从7个位置中挑选2个作为分割物的位置,共有

image.png

阶乘与组合

我们在上面多次使用了阶乘运算,在Python中,它可以使用math.factorial实现:

import math
print(math.factorial(5))

此外,组合可以使用scipy.misc.comb来近似计算,比如:

import scipy.misc
print(scipy.misc.comb(4, 2))

练习

每一部分都提出了两个问题,思考第二个问题的结果。

总结

基本计数原理

排列

组合

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能头条

深度学习一种变相的马尔可夫链吗?

2034
来自专栏一名叫大蕉的程序员

大数据计数原理1+0=1这你都不会算(六)No.57

照例甩一波链接。 大数据计数原理1+0=1这你都不会算(一)No.47 <- HashSet 大数据计数原理1+0=1这你都不会算(二)No.5...

2106
来自专栏AI派

【Github 5K星】BAT头条滴滴小米等笔试面经+深度学习/算法/NLP资源汇总!

最近,在GitHub上有位id为imhuay的热心人带头建立了一个关于国内知名互联网企业笔试和面试经验的资源库,光从名称上就能看出其内容有多丰富:《2018/2...

1251
来自专栏PPV课数据科学社区

深度学习( Deep Learning )软件资源列表

? 列表源自http://deeplearning.net/software_links/,本文进行分类整理。 星号代表对软件库的推荐度,考虑了适用范围、开发...

3097
来自专栏社区的朋友们

Steering Behaviors 详解

Steering Behaviors 意在使游戏中的AI个体具备真实的运动行为,通过对力的施加与整合,使游戏个体具备类生命体般的运动特征。

9761
来自专栏小樱的经验随笔

利用向量积(叉积)计算三角形的面积和多边形的面积

利用向量积(叉积)计算三角形的面积和多边形的面积: 向量的数量积和向量积: (1)  向量的数量积 ? (1)  向量的向量积 两个向量a和b的叉积(向量积)可...

4399
来自专栏大数据风控

评分卡上线后如何进行评分卡的监测

有一段时间没来写博了,一直忙我司申请评分卡、催收评分卡的上线工作,那么我们的评分卡上线后,如何对评分卡的效果进行有效监测,监测哪些指标,监测的指标阈值达到多少我...

9325
来自专栏程序猿

算法Blog之博弈原理

博弈入门 寻找平衡状态(也称必败态, 奇异局势),(满足:任意非平衡态经过一次操作可以变为平衡态) 一.巴什博奕(Bash Game) 只有一堆n个物品,两个人...

37710
来自专栏一个会写诗的程序员的博客

勾股定理·圓周率·無窮級數·微積分勾股定理圓圓周率定义1定义2定义3代数数学分析数论概率论统计学圆的内接正多边形和外接正多边形歐拉公式三角函數分析微積分宇宙運行軌道萬有引力定律電磁場方程相對論量子力學

量子力学理论在20世纪初期诞生,而沃利斯圆周率公式已经存在了数百年,但这两者之间的内在关联直到今天才被发现。

1031
来自专栏磐创AI技术团队的专栏

【Github 4K星】BAT头条滴滴小米等笔试面经+深度学习/算法/NLP资源汇总!

最近,在GitHub上有位id为imhuay的热心人带头建立了一个关于国内知名互联网企业笔试和面试经验的资源库,光从名称上就能看出其内容有多丰富:《2018/2...

2433

扫码关注云+社区

领取腾讯云代金券