# 生日悖论

> source: 文章/birthday-paradox/index.md

## 生日悖论

多少人中必定出现两个同一天生日的人（不考虑特殊情况）？

经典概率论告诉我们366人中，根据抽屉原理，可以得到必有两个人同一天生日

如果有两个人，那么这两个人生日不相同的概率为
$$
P_2 = \frac{364}{365}
$$
如果有三个人，那么三个人的生日均不相同的概率为
$$
P_3 =P_2\times \frac{363}{365}
$$
以此类推，如果有$p$个人，那么这$p$个人的生日均不相同的概率为
$$
\begin{aligned}
P_p
&= \frac{364}{365}\times \frac{363}{365}\times \frac{362}{365}\times \cdots \times \frac{366-p}{365} \\
&= \frac{364\times 363\times 362 \times \cdots \times (366-p)}{365^{p-1}} \\
&= \frac{365\times 364\times 363\times 362 \times \cdots \times (366-p)}{365^p} \\
&= \frac{365!}{365^p(365-p)!}
\end{aligned}
$$
根据以上算法得到下面的 C++ 代码

```cpp
double sameBirthdayProbability(int people) {
    double allDifferent = 1.0;
    for (int i = 0; i < people; ++i) {
        allDifferent *= static_cast<double>(365 - i) / 365;
    }
    return 1.0 - allDifferent;
}
```

下图展示了随着人数增加，至少一对同生日的概率是如何上升的：

```echarts
{
  "title": {
    "text": "生日悖论：至少一对同生日的概率",
    "left": "center",
    "textStyle": {
      "fontWeight": 700
    }
  },
  "tooltip": {
    "trigger": "item",
    "formatter": "{a}<br/>人数：{@[0]}<br/>概率：{@[1]}%",
    "axisPointer": {
      "type": "none"
    }
  },
  "grid": {
    "left": 48,
    "right": 24,
    "top": 72,
    "bottom": 48
  },
  "xAxis": {
    "type": "value",
    "name": "人数",
    "min": 1,
    "max": 60,
    "interval": 5,
    "axisLabel": {
      "fontWeight": 600
    },
    "nameTextStyle": {
      "fontWeight": 600
    }
  },
  "yAxis": {
    "type": "value",
    "name": "概率",
    "min": 0,
    "max": 100,
    "axisLabel": {
      "formatter": "{value}%",
      "fontWeight": 600
    },
    "nameTextStyle": {
      "fontWeight": 600
    }
  },
  "series": [
    {
      "name": "出现相同生日",
      "type": "line",
      "z": 2,
      "smooth": true,
      "showSymbol": false,
      "lineStyle": {
        "width": 3
      },
      "areaStyle": {
        "opacity": 0.14
      },
      "data": [[1,0],[2,0.274],[3,0.82],[4,1.636],[5,2.714],[6,4.046],[7,5.624],[8,7.434],[9,9.462],[10,11.695],[11,14.114],[12,16.702],[13,19.441],[14,22.31],[15,25.29],[16,28.36],[17,31.501],[18,34.691],[19,37.912],[20,41.144],[21,44.369],[22,47.57],[23,50.73],[24,53.834],[25,56.87],[26,59.824],[27,62.686],[28,65.446],[29,68.097],[30,70.632],[31,73.045],[32,75.335],[33,77.497],[34,79.532],[35,81.438],[36,83.218],[37,84.873],[38,86.407],[39,87.822],[40,89.123],[41,90.315],[42,91.403],[43,92.392],[44,93.289],[45,94.098],[46,94.825],[47,95.477],[48,96.06],[49,96.578],[50,97.037],[51,97.443],[52,97.8],[53,98.114],[54,98.388],[55,98.626],[56,98.833],[57,99.012],[58,99.166],[59,99.299],[60,99.412]],
      "markPoint": {
        "symbol": "circle",
        "symbolSize": 12,
        "tooltip": {
          "formatter": "{b}"
        },
        "itemStyle": {
          "color": "#ef4444"
        },
        "label": {
          "show": false
        },
        "data": [
          {
            "name": "23 人",
            "coord": [23, 50.73],
            "value": 50.73
          },
          {
            "name": "57 人",
            "coord": [57, 99.012],
            "value": 99.012
          }
        ]
      },
      "markLine": {
        "symbol": ["none", "none"],
        "tooltip": {
          "show": false
        },
        "data": [
          {
            "yAxis": 50,
            "label": {
              "formatter": "50%",
              "fontWeight": 600
            },
            "lineStyle": {
              "type": "dashed"
            }
          },
          {
            "yAxis": 99,
            "label": {
              "formatter": "99%",
              "fontWeight": 600
            },
            "lineStyle": {
              "type": "dashed"
            }
          }
        ]
      }
    }
  ]
}
```

当$x = 57$时，$P > 0.99$，也就是说57人中，出现同一天生日的概率就超过了99%

实际运算后，我们发现主观上的判断和现实竟然有很大的差别啊

## 哈希碰撞

生日悖论的一类重要用途是估算哈希碰撞。哈希函数可以看成把大量输入压缩到一个有限的输出空间中。例如一个$n$ bit 的哈希值，一共有

$$
N = 2^n
$$

种可能结果

如果我们只想让某个输入命中特定哈希值，那么平均需要接近$2^n$次尝试；但如果目标只是找到任意两个输入拥有相同哈希值，难度会下降到大约$2^{n/2}$量级。这就是密码学中的生日攻击（birthday attack）

也就是说，哈希函数的碰撞安全强度大约只有输出长度的一半：

| 哈希长度 | 输出空间 | 碰撞攻击量级 |
| --- | --- | --- |
| 64 bit | $2^{64}$ | $2^{32}$ |
| 128 bit | $2^{128}$ | $2^{64}$ |
| 256 bit | $2^{256}$ | $2^{128}$ |

所以在密码学中，不能只看哈希值有多少位，还要区分两种问题：

- 原像攻击：给定目标哈希值，找一个输入命中它。
- 碰撞攻击：找任意两个不同输入，让它们哈希值相同。

生日悖论影响的是第二类问题。对于签名、证书、文件指纹、内容寻址存储等场景，碰撞风险就非常关键

## 风险估算

如果有$N$种可能输出，随机生成$k$个值，那么完全没有碰撞的概率为

$$
P_{\text{no collision}}
=
\prod_{i=0}^{k-1}\left(1-\frac{i}{N}\right)
$$

因此，至少发生一次碰撞的概率是

$$
P_{\text{collision}}
=
1-
\prod_{i=0}^{k-1}\left(1-\frac{i}{N}\right)
$$

当$k$相对$N$较小时，可以使用近似

$$
\ln(1-x)\approx -x
$$

于是

$$
\begin{aligned}
\ln P_{\text{no collision}}
&= \sum_{i=0}^{k-1}\ln\left(1-\frac{i}{N}\right) \\
&\approx -\sum_{i=0}^{k-1}\frac{i}{N} \\
&= -\frac{k(k-1)}{2N}
\end{aligned}
$$

所以

$$
P_{\text{collision}}
\approx
1-e^{-\frac{k(k-1)}{2N}}
$$

这条公式比直接算阶乘更适合做工程估算。它说明碰撞概率主要由

$$
\frac{k^2}{2N}
$$

控制，而不是由$\frac{k}{N}$控制。这也是为什么碰撞来得比直觉更快

## 数学原理

如果想反过来问：为了让碰撞概率达到某个$p$，大约需要生成多少个随机值？可以从近似公式出发：

$$
p \approx 1-e^{-\frac{k(k-1)}{2N}}
$$

当$k$较大时，$k(k-1)\approx k^2$，于是

$$
\begin{aligned}
1-p
&\approx e^{-\frac{k^2}{2N}} \\
\ln(1-p)
&\approx -\frac{k^2}{2N} \\
k
&\approx \sqrt{2N\ln\frac{1}{1-p}}
\end{aligned}
$$

当$p=0.5$时，

$$
k \approx \sqrt{2N\ln 2}\approx 1.177\sqrt{N}
$$

这就是“平方根量级”的来源。生日问题里$N=365$，所以

$$
1.177\sqrt{365}\approx 22.49
$$

因此23人时，出现同生日的概率刚好超过50%

这个结论也可以迁移到随机 ID 设计中。假设系统使用$b$ bit 的随机 ID，那么$N=2^b$。如果一天生成$k$个 ID，则碰撞概率近似为

$$
P_{\text{collision}}
\approx
1-e^{-\frac{k^2}{2\cdot 2^b}}
$$

当风险很小时，还可以继续近似为

$$
P_{\text{collision}}
\approx
\frac{k^2}{2\cdot 2^b}
$$

例如使用64 bit 随机 ID，一天生成一百万个：

$$
\begin{aligned}
k &= 10^6 \\
N &= 2^{64}\approx 1.84\times 10^{19} \\
P_{\text{collision}}
&\approx \frac{10^{12}}{2\times 1.84\times 10^{19}} \\
&\approx 2.7\times 10^{-8}
\end{aligned}
$$

单日风险很小，但如果系统长期运行、规模继续扩大，风险会随生成数量的平方增长。因此在设计哈希长度、随机 ID、短链接码、文件指纹时，真正要关注的是“生成数量的平方”和“输出空间大小”的比例
