lgswdn-SA > 信概统-离散随机变量

信概统-离散随机变量

2025-10-13

信概统计

概率的公理化

\(S\) 为样本空间，\(F\) 为 \(S\) 的某些子集组成的事件域，定义在 \(F\) 上的函数 \(P\) 满足

  • \(\forall A\in F\)，\(P(A)\ge 0\)
  • \(\sum P(F)=1\)
  • 对于互不相容事件有 \(\sum P(A_i)=P(\bigcup A_i)\)

则称 \(P(A)\) 为事件 \(A\) 的概率，\((S,F,P)\) 为概率空间.

可以简单地用上述公理推导出很多我们熟悉的东西，不再列举.

Union Bound：\(P(\bigcup A_i)\le \sum P(A_i)\). 这个在事件之间有说不清楚的联系的时候可以解决很多问题.

概率证法：如果可以证明 \(P(A)>0\)，那么 \(A\neq \varnothing\).

Eg. 对于 \(k\ge 3\)，存在 \(n=2^{\frac{k}{2}-1}\) 个点的图，使得没有 \(k\) 元团也没有 \(k\) 元独立集.

Pf: 存在 \(k\) 元团和 \(k\) 元独立集的概率由 Union Bound 都知道 \(\le \binom{n}{k}2^{-k(k-1)/2}\). 于是一个图有两者之一的概率 \(\le \binom{n}{k}2^{1-k(k-1)/2}< 1\).

条件概率

若 \(P(B)>0\)，定义条件概率 \(P(A|B)=\frac{P(AB)}{P(B)}\).

乘法公式：\(P(AB)=P(A|B)P(B)\)，可以推广到 \(n\) 个事件.

贝叶斯公式：\(P(B|A)=\frac{P(A|B)P(B)}{P(A)}\).

独立性：事件 \(A,B\) 独立当且仅当 \(P(AB)=P(A)P(B)\). 对于 \(P(B)>0\)，等价于 \(P(A|B)=P(A)\).

对于多个事件，两两独立 不等价于 相互独立. 两两独立且 \(P(ABC)=P(A)P(B)P(C)\) 才有相互独立.

反例：\(x\) 为取 \(\{0,1,2,3\}\) 的随机变量，\(A=[x\in\{0,1\}]\)，\(B=[x\in\{0,2\}]\)，\(C=[x\in\{0,3\}]\).

离散随机变量

期望 方差

离散随机变量：取可列个值的随机变量.

分布列：若 \(X\) 的全部可能取值为 \(x_1,x_2\dots\)，\(p_i=P(X=x_i)\) 为 \(X\) 的分布列.

数学期望：若 \(\sum |p_ix_i|\) 绝对收敛，则定义 \(E(X)=\sum |p_ix_i|\) 为其数学期望.

性质：

  • 一般而言，\(E(g(x))=\sum p_i g(x_i)\).
  • 用 \(1_A\) 表示 \(A\) 的事性函数（是否发生），有 \(P(A)=E(1_A)\).
  • 线性性. \(E(aX+b)=aE(X)+b\).
  • 概率证法：\(P(X\ge E(X))> 0\). 只需要证明一个事情期望发生次数是对的就可以了. 在某给 Yukicoder 的题中亦有提及.
  • Markov 不等式：对于非负随机变量 \(X\)，若 \(E(X)>0\)，则 \(P(X\ge cE(X))\le \frac{1}{c}\).

方差：若 \(E((X-E(X))^2)\) 存在，则定义 \(=Var(X)\) 为其方差. 定义标准差 \(\sigma=\sqrt{Var}\).

性质：

  • 线性性. \(Var(aX+b)=a^2Var(X)\)，\(\sigma(aX+b)=|a|\sigma(X)\).

  • \(Var(X)=E(X^2)-E(X)^2\). 推论是 \(E(X^2)\ge E(X)^2\). 这是很常用的计算方差的办法.

  • 切比雪夫不等式：\(P(|X-E|\ge c\sigma)\le\frac{1}{c^2}\).

    证明考虑对随机变量 \(Y=(X-E)^2\) 使用 Markov 不等式.

常见离散分布

二项分布

二项分布 \(B(n,p)\). \(P(X=k)\) 为 \(n\) 重伯努利实验中概率为 \(p\) 的事件 \(A\) 发生次数为 \(k\) 的概率.

  • \(E(X)=np\)
  • \(E(X^2)=n(n-1)p^2+np\)
  • \(Var(X)=np(1-p)\)
泊松分布

泊松分布 \(\pi(\lambda)\)：\(B(\lambda m,\frac{1}{m})\) 在 \(m\to +\infty\) 的情况.

  • \(P(X_i=k)= \frac{\lambda^ke^{-\lambda}}{k!}\).
  • \(E(X)=\lambda\)
  • \(Var(X)=\lambda\)

实际上，任意一列 \(p_1,\dots\)，只要 \(p_nn\to \lambda\)，皆有 \(P(X_n=k)\to \frac{\lambda ^ke^{-\lambda}}{k!}\).

几何分布

几何分布 \(G (p)\)：结果 \(A\) 首次出现时的试验次数.

  • \(P(X_i=k)=p(1-p)^{k-1}\).
  • \(E(X)=\frac{1}{p}\).
  • \(Var(X)=\frac{1-p}{p^2}\).
  • 无记忆性：\(P(X>n+m|X>m)=P(X>n)\).
负二项分布

负二项分布 \(NB(r,p)\)：结果 \(A\) 首次发生 \(r\) 次时的试验次数.

  • \(P(X_i=k)=\binom{k-1}{r-1}p^{r}(1-p)^{k-r}\).

  • \(NB(1,p)=G(p)\).

  • 如何证明其的确是概率分布？即 \(\sum \binom{k-1}{r-1}p^r(1-p)^{k-r}=1\)？

    令 \(l=k-r\)，则即证 \(\sum \binom{l+r-1}{r-1}(1-p)^l=p^{-r}\)

    将 \(p^{-r}\) 写作 \((1-(1-p))^{-r}\) 后展开，得 \(\sum (-1)^{l}\binom{-r}{l}(1-p)^l=\sum \binom{l+r-1}{l}(1-p)^l\)，即证.

  • \(NB(r,p)\) 可以看作 \(r\) 个 \(G(p)\) 之和.