子采样的数学期望、方差推导

假设ZZ的期望和方差分别为μ\mu、σ2\sigma^2，由于Z1,Z2,…,ZKZ_1,Z_2,\dots,Z_K是独立同分布的随机变量，每个ZkZ_k的期望和方差也是μ\mu、σ2\sigma^2。SKS_K的定义如下：

SK=1K∑k=1KZkS_K = \frac{1}{K} \sum_{k=1}^K Z_k

  1. E(SK)\textbf{E}(S_K)

    E(SK)=E(1K∑k=1KZk)=1K∑k=1KE(Zk)=1K∑k=1Kμ=μ\textbf{E}(S_K) = \textbf{E}(\frac{1}{K} \sum_{k=1}^K Z_k) = \frac{1}{K}\sum_{k=1}^K\textbf{E}(Z_k)=\frac{1}{K}\sum_{k=1}^K\mu=\mu

  2. Var(SK)\textbf{Var}(S_K)

    Var(SK)=Var(1K∑k=1KZk)\textbf{Var}(S_K) = \textbf{Var}(\frac{1}{K}\sum_{k=1}^KZ_k)

    根据方差的定义，可以提取出常数的平方：

    Var(SK)=1K2Var(∑k=1KZk)\textbf{Var}(S_K) = \frac{1}{K^2}\textbf{Var}(\sum_{k=1}^KZ_k)

    由于Z1,Z2,…,ZKZ_1,Z_2,\dots,Z_K是独立同分布的随机变量，独立随机变量的方差可以直接相加，因此：

    Var(∑k=1KZk)=∑k=1KVar(Zk)=∑k=1Kσ2=Kσ2\textbf{Var}(\sum_{k=1}^KZ_k) = \sum_{k=1}^K \textbf{Var}(Z_k) = \sum_{k=1}^K \sigma^2 = K\sigma^2

    综上：

    Var(SK)=σ2K\textbf{Var}(S_K) = \frac{\sigma^2}{K}

0−10-1损失函数与随机变量的方差

随机变量ZZ从0−10-1损失中抽取，则ZZ是一个取值为00或者11的随机变量，其方差计算公式为：

Var(Z)=E[Z2]−(E[Z])2\textbf{Var}(Z) = \textbf{E}[Z^2]-(\textbf{E}[Z])^2

由于ZZ为0−10-1分布，有Z2=ZZ^2=Z，因此E[Z2]=E[Z]\textbf{E}[Z^2] = \textbf{E}[Z]。设E[Z]=p\textbf{E}[Z] = p，那么：

Var(Z)=p−p2=p(1−p)\textbf{Var}(Z) = p - p^2 = p(1 - p)

对于0−10-1分布的随机变量ZZ，pp是其取值为1的概率，为了找到方差的最大值，考虑函数f(p)=p(1−p)f(p)=p(1-p)的最大值。显然其最大值在p=0.5p = 0.5时取得，即ZZ的方差最大值为0.250.25。

Boole 不等式

布尔不等式也叫union bound，即并集的上界。描述至少一个事件发生的概率 P(⋃Ai)\textbf{P}(\bigcup A_i) 不大于单独事件发生的概率之和 ∑P(Ai)\sum \textbf{P}(A_i)，即P(⋃Ai)≤∑P(Ai)\textbf{P}(\bigcup A_i) \leq \sum \textbf{P}(A_i)。（i∈{1,2,…,N}i \in \{1,2,\dots,N\}）

数学归纳法证明

  1. 当n=1n=1时，显然P(A1)≤P(A1)\textbf{P}(A_1) \leq \textbf{P}(A_1)。

  2. 对于nn，假设下式成立：

    P(∪i=1nAi)≤∑i=1nP(Ai)\textbf{P}(\cup_{i=1}^nA_i) \leq \sum_{i=1}^n\textbf{P}(A_i)

  3. 对于N=n+1N = n+1：

    P(∪i=1NAi)=P({∪i=1nAi}  ∪  An+1)\textbf{P}(\cup_{i=1}^{N}A_i) = \textbf{P}(\{\cup_{i=1}^nA_i\} \;\cup\; A_{n+1})

    又由：

    P(A  ∪  B)=P(A)+P(B)−P(A  ∩  B)\textbf{P}(A\;\cup\;B) = \textbf{P}(A) + \textbf{P}(B) - \textbf{P}(A\;\cap\;B)

    则：

    P({∪i=1nAi}  ∪  An+1)=P({∪i=1nAi})+P(An+1)−P({∪i=1nAi}  ∩  An+1)≤∑i=1NP(Ai)−P({∪i=1nAi}  ∩  An+1)≤∑i=1NP(Ai)\textbf{P}(\{\cup_{i=1}^nA_i\} \;\cup\; A_{n+1}) = \textbf{P}(\{\cup_{i=1}^nA_i\}) + \textbf{P}(A_{n+1}) - \textbf{P}(\{\cup_{i=1}^nA_i\} \;\cap\; A_{n+1})\\ \leq \sum_{i=1}^N\textbf{P}(A_i) - \textbf{P}(\{\cup_{i=1}^nA_i\} \;\cap\; A_{n+1})\\ \leq \sum_{i=1}^N\textbf{P}(A_i)

二项分布

有 35 个用户，每个用户活跃的概率为 10%（相互独立），计算任一时刻超过 10 个用户活跃的概率。

这是一个 二项分布 问题。设 XX 是活跃用户的数量，则 XX 服从参数为 n=35n = 35 和 p=0.1p = 0.1 的二项分布：

X∼Binomial(n=35,p=0.1)X \sim Binomial(n = 35, p = 0.1)

求概率 P(X>10)P(X > 10)，即超过 10 个用户活跃的概率。根据概率的性质，计算该概率的方式为：

P(X>10)=1−P(X≤10)P(X > 10) = 1 - P(X \leq 10)

其中，P(X≤10)P(X \leq 10) 是 XX 小于或等于 10 的概率，可以通过二项分布的累积分布函数（CDF）计算。

**二项分布的概率质量函数（PMF）**公式如下：

P(X=k)=(nk)pk(1−p)n−kP(X = k) = \binom{n}{k} p^k (1 - p)^{n - k}

其中：

  • n=35n = 35 为试验次数（用户数）
  • kk 是活跃用户的数量
  • p=0.1p = 0.1 是每个用户活跃的概率

组合数公式为：

(nk)=n!k!(n−k)!\binom{n}{k} = \frac{n!}{k!(n - k)!}

累积分布函数（CDF） 表示 XX 小于或等于某个值 kk 的概率，即：

P(X≤k)=∑i=0kP(X=i)P(X \leq k) = \sum_{i=0}^{k} P(X = i)

因此，我们可以用 CDF 计算 P(X≤10)P(X \leq 10)：

P(X≤10)=∑i=010(35i)(0.1)i(0.9)35−iP(X \leq 10) = \sum_{i=0}^{10} \binom{35}{i} (0.1)^i (0.9)^{35 - i}

最后，将 P(X≤10)P(X \leq 10) 代入以下公式，得到最终概率：

P(X>10)=1−P(X≤10)P(X > 10) = 1 - P(X \leq 10)

排列组合计算公式

排列（Permutation）

排列是从 nn 个不同元素中选出 kk 个元素的所有可能的排列方式。排列的计算公式为：

P(n,k)=n!(n−k)!P(n, k) = \frac{n!}{(n - k)!}

其中：

  • nn 是元素总数
  • kk 是选取的元素数
  • !! 表示阶乘

组合（Combination）

组合是从 nn 个不同元素中选出 kk 个元素的所有可能的组合方式。组合的计算公式为：

C(n,k)=(nk)=n!k!(n−k)!C(n, k) = \binom{n}{k} = \frac{n!}{k!(n - k)!}

其中：

  • nn 是元素总数
  • kk 是选取的元素数
  • (nk)\binom{n}{k} 是组合数，表示从 nn 个元素中选出 kk 个元素的组合方式
  • !! 表示阶乘