Benford 定律
Benford 从对数表中发现, 在自然界中, 数字 1 作为首位数字出现的概率远远大于其他数字. 例如, 在一个包含大量数据的集合中, 大约有 30% 的数以 1 开头, 而以 9 开头的数只有不到 5%. 这个现象被称为 Benford 定律.
定理Benford 定律
若 $\log_{10} x$ 的小数部分 $U(x) = \{ \log_{10} x \}$ 服从 $(0,1)$ 均匀分布, $x$ 的首位数字 $d=D(x)$ 出现的概率 $P(d)$ 可以用以下公式计算:
$$P(d) = \log_{10}\left(1 + \frac{1}{d}\right)$$其中 d 是 1 到 9 之间的整数.
定理尺度不变性
若对任意 $c>0$, $U(x)$ 和 $U(cx)$ 的分布相同, 则 $X$ 服从 Benford 定律.
证明
$$ U(cx) = \left\{\log_{10} (cx) \right\} = \left\{\log_{10} c + \log_{10} x\right\} = \left\{U(x) + a\right\} $$ $U(x)$ 和 $\left\{U(x) + a\right\}$ 同分布, 对任意 $a$ 都成立. 因此 $U(x)$ 服从 $(0,1)$ 均匀分布, $X$ 服从 Benford 定律.常返
$(x_n)$ 是正数数列, 定义 $U_n = U(x_n) = \left\{ \log_{10} x_n \right\} \in (0,1)$. 首位数字 $d$ 对应 $I_d = \left[ \log_{10}d, \log_{10}(d+1) \right) $，则 $D(x_n)=d \Leftrightarrow U_n \in I_d$.
考虑数列 $x_n = a^n$.
$$U(n) = \left\{ n \log_{10} a \right\} = \left\{ n \alpha \right\}$$换言之,
$$u_{n+1} = u_n + \alpha \mod 1$$- 若 $\alpha \in \mathbb{Q}$, 则数列 $(u_n)$ 是周期数列, 不满足 Benford 定律.
- 若 $\alpha \in \mathbb{R} \setminus \mathbb{Q}$, 则数列 $(u_n)$ 在 $(0,1)$ 上均匀分布, 满足 Benford 定律.
这里用到了 Weyl 等分布定理: 设 $\alpha$ 是无理数, 那么序列 $x_n = \{n\alpha\}$ 在 $[0,1)$ 上均匀分布.
考虑 $W \sim \text{Triangler} (0,1,2)$, 即:
$$ f(W) = \begin{cases} W, & 0 < W < 1 \\ 2-W, & 1 \leq W < 2 \\ \end{cases} $$$X = 10^W$, 则 $U(X) = \{W\}$. 不难计算 $\{W\}$ 是均匀分布, 即便 $W$ 不是. 然而, $X$ 服从 Benford 定律.
其中 $\phi = (1+\sqrt{5})/2$, $\psi = (1-\sqrt{5})/2$.
则 $U(F_n) = \{ n \log_{10} \phi - \log_{10} \sqrt{5} + o(1) \}$. 因为 $\log_{10} \phi$ 是无理数, 所以 $U(F_n)$ 在 $(0,1)$ 上均匀分布, 满足 Benford 定律.
这就是乘法过程中的常返, $X_{n+1}=A_nX_n$.