Irwin-Hall Distribution

$n$ 个在 $[0,1)$ 上均匀分布的随机变量 $\{x_i\}$，考虑它们的和 $s=\sum x_i$，则 $s$ 服从 Irwin-Hall Distribution，其累计分布函数
$$
F_s(x)=\frac 1 {n!}\sum_{k=0}^{\lfloor x\rfloor}(-1)^k\binom nk(x-k)^n.
$$
考虑单个变量的概率密度函数 $f(x)=[0\le x< 1]$，则 $F$ 是 $n$ 个 $f$ 的卷积。

容斥，将 $f(x)$ 重写为 $f(x)=[x\ge 0]-[x\ge 1]$。

考虑计算 $g(x)=[x\ge 0]$ 的卷积。
$$
\begin{aligned}
g^{*n}(x)&=\int g^{*(n-1)}(t)g(x-t)\mathrm d t\\
&=\int_0^x g^{*(n-1)}(t)\mathrm d t
\end{aligned}
\quad(x\ge 0)
$$
容易归纳得到 $g^{*n}(x)=x^n/n!$。

选择一个 $[x\ge 1]$ 相当于使目标总和 $-1$，于是容易得到文章开头的累积分布函数。

组合意义：

$g^{*n}(x)$ 描述了合法点 $(x_1,x_2,\dots,x_n)$ 构成集合在 $n$ 维空间中的测度。考虑对 $\{x_i\}$ 做前缀和，前缀和序列中的每个数属于 $[0,x]$，于是我们在 $[0,x]$ 中任意撒 $n$ 个点即可得到合法的前缀和数组，从而唯一确定 $\{x_i\}$，同一个前缀和数组会被统计 $n!$ 次，于是测度为 $x^n/n!$。

当 $x$ 是自然数时，$F_s(x)$ 乘上 $n!$ 就恰好是欧拉数的前缀和，我们可以证明这一点。

记 $s_i$ 为 $\lfloor x_1+\dots+x_i\rfloor$ 的小数部分，容易发现 $\lfloor x_1+\dots+x_i\rfloor+1=\lfloor x_1+\dots+x_{i+1}\rfloor$ 当且仅当 $s_i>s_{i+1}$，于是，$\sum x_i<k$ 当且仅当序列 $s$ 中满足 $s_i>s_{i+1}$ 的位置不超过 $k-1$，$s$ 中元素大小关系服从任意排列的概率均相等，所以 $\sum x_i<k$ 的概率和随机排列满足 $p_i>p_{i+1}$ 的位置不超过 $k-1$ 的概率相等。这样就从组合上建立了两问题间的联系。

---

Reference：

• 题解 P5825 【排列计数】 - EI
• Irwin–Hall Distribution - OneInDark
• 浅谈欧拉数 - Karry5307

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。