首页 > 代码库 > Introduction to Probability (4) Counting

Introduction to Probability (4) Counting

当我们计算概率的时候,假设样本空间中的各个样本发生的概率均等,那么,时间A发生的概率为:


所以我们只需要计算时间A包含的样本个数,比上总的样本数,就能得到事件A发生的概率。

基本的counting原则

假设一次实验共有r个阶段,每个阶段有ni种选择,那么总的样本空间是各个阶段的各种选择的乘积。


排列permutation与组合combination

当我们要从n个样本中选取k个样本时,我们所面临的是一个组合问题,这个时候如果需要考虑顺序,那么就变成了一个排列问题。

组合

以下是从n个样本中选取k个的组合表达式:

我们有两种方法去得到从n个样本中选取k个,并考虑顺序的结果。


第一种方法是直接用排列的方式,k个座位虚位以待,按照次序从n个样本中选取样本放入座位,那么选择的个数从n递减至n-k+1

第二种方法是首先用组合的方式选出来k个样本,然后再排序。

所以通过两种方法,我们得到:


组合的经典应用场景是binomial分布的计算,如下例,掷硬币n次,其中k次是head,那么用组合的方式从n中选取k次。


Partitions 

最后要讲一下分堆的问题,比如将一个含有n个样本的集合分成n1,n2........nr堆,那么我们总共的选择有多少种呢?

首先从n中选取n1个样本,接下来从n-n1个样本中选取n2个样本,一直到最后,表达如下式:


接着将其展开:


整理可得:



总结:

一个常见的概率问题可以分为以下几步:

1.样本空间的描述,即一个实验的所有可能输出。

2.每个事件发生的概率。

3.根据要求计算概率或者条件概率。

几种常用的方法:

1.counting

2.sequential method

3.divide-conquer