Processing math: 100%

概率论基本概念 · 概率论、数理统计与信息论 01

Hailiang Zhao | 2022/01/19

Categories: math Tags: probability-theory


1 基本概念

1.1 概率空间

离散概率空间 (Ω,Pr) 由一个非空可数集合 Ω 和定义在其上的 概率质量函数(pmf)Pr:ΩR 组成。要求 ωΩ,Pr[ω]0ωΩPr[ω]=1。每一个 ωΩ 被称为一个 样本点

1.2 事件

事件是非空可数集合 Ω 的一个子集(因此也必然是可数的)。事件 A 发生的概率被定义为: Pr[A]:=ωAPr[ω] 事件的组合通常用逻辑运算符号来描述,如 ABAB¬A 等。下面给出了事件组合的一些性质:

1.3 组合事件的一些恒等式

1.4 随机变量

随机变量 X 是一个从 Ω 到某个数值集合 V 的一个映射:X(ωΩ)=xV随机变量既不随机,也不是一个变量,而是一个函数。 显然,有 Pr[X=x]=Pr[A:={ωΩX(ω)=x}] 定义在随机变量上的任意概念总应当回归到事件这一底层概念上去理解。

随机变量 X 的(累积)分布函数 CDF 如下: CDFX(Xx)=Pr[Xx]=Pr[A:={ωΩX(ω)x}]

1.5 期望

定义在随机变量 X 上的期望为: (离散)E[X]:=xxPr[X=x](连续)E[X]:=xfX(x)dx 其中 fX() 是随机变量 X 的概率密度函数。

X 为任意整数随机变量,则 E[X]=x1(Pr[Xx]Pr[Xx]) 这个结论可以通过 Pr[X=x]=Pr[Xx]Pr[Xx+1] 这个等价代换来证明。

1.6 条件期望

事件 A 发生的情况下随机变量 X 的条件期望为: E[XA]:=xxPr[X=xA]=xxPr[X=xA]Pr[A]=xxPr[{ωAX(ω)=x}]Pr[A]

1.7(离散变量的)全期望展开

对于任意事件 A(或随机变量 A),下面两个式子成立: E[X]=E[XA]Pr[A]+E[X¬A]Pr[¬A]E[X]=aE[XA=a]Pr[A=a]

1.8 联合概率(以连续变量为例)

1.9 随机变量的独立性及其特征

2 泊松分布与指数分布

3 使用概率论解决实际问题

3.1 问题 1

对应任意硬币(可能被做假,不妨假设正面落下的概率为 p,反面落下的概率为 qp+q=1),试证明:通过如下方法总能产生公平的抛硬币效果,并求解 BiasedCoin() 的期望调用次数。

图 1 VonNeumannCoin 方法。

求解:若停机,则必然有 xy,所以 Pr[x=0y=1xy]=Pr[x=1y=0xy]=pq2pq=12 这里运用了 xy 相互独立。

令随机变量 TBiasedCoin() 的调用次数,则 E[T]=E[Txy]Pr[xy]+E[Tx=y]Pr[x=y] 其中,Pr[xy]=2pqE[xy]=2(因为一轮就结束了,只运行了两次)。此外有 Pr[x=y]=12pqE[Tx=y]=2+E[T](递归调用),联立可解得 E[T]=1pq

3.2 问题 2

假设有 n 种不同的卡,每次买一包干脆面可以抽出一种卡。假设买了 n 包干脆面,可以抽出多少张不同的卡?为了收集到全部种类的卡,至少要买几包干脆面?

求解:对应第 i 种卡,定义随机变量 Xi{0,1} 表示我们是否拥有它。定义随机变量 X 表示我们拥有的、不同种类的卡的个数。显然有 X=iXi。 所以 E[X]=iE[Xi]=iEPr[Xi=1]

n 次购买中,i,我们没有抽到第 i 种卡的概率为 Pr[Xi=0]=(11n)n1e(这是因为每次购买抽出第 i 种卡的概率服从独立同分布),所以 E[X]ne0.632n

T(n) 为收集了 n 种卡所购买的干脆面的包数。将购买行为划分为 n 个阶段,第 i 个阶段在抽到第 i 种卡之后停止。用 Ti(n) 表示第 i 个阶段购买的干脆面的包数。 则 T(n)=ni=1Ti(n)。在第 i 个阶段,抽到一张新卡的概率为 n(i1)n,此时 Ti(n) 实际上是一个几何分布的随机变量,根据几何分布的期望可知 E[Ti(n)]=nni+1,所以 E[T(n)]=nj=1nj=n(1+12+13+...+1n) 后面这个几何级数满足 ln(n+1)nj=11jlnn+1(借助每段函数 1j 的上下界函数的积分来计算),所以可得结论:至少要买 Θ(nlnn) 包。

转载申请

本作品采用 知识共享署名 4.0 国际许可协议 进行许可,转载时请注明原文链接。您必须给出适当的署名,并标明是否对本文作了修改。