$d$ 维球体 $k$ 远点期望

从 xiaodao 空间上看到的……

感觉蛮好玩的于是就试了试。xiaodao 最后的那个连乘真的没有想到，我只会暴力积分……

Problem

\(d\) 维单位球体中随机选 \(n\) 个点，到球心 \(k\) 远点距离球心的期望是多少？

Solution

\(n\) 个点，随机选一个为 \(k\) 远点，再选 \(k - 1\) 个点为前 \(k - 1\) 远点，方案数为 \(\binom{n}{1, k - 1}\) 。

（维基百科） \(d\) 维单位球体的体积是 \[V_d(R) = \frac{\pi^{\frac{d}{2}}R^d}{\Gamma(\frac{d}{2}+1)} = C_d R^d\] 其中 \(C_d\) 为与 \(d\) 相关的常数。

根据“维”的定义，我们有距离为 \(r\) 的点的密度为 \[\rho(r) = \frac{V'_d(r)}{V_d(1)} = d r^{d - 1}\]

于是 \(k\) 远点的期望是： \[\begin{array}{rl} & \binom{n}{1, k - 1} \int_0^1 r \rho(r) (r^d)^{k-1} (1 - r^d)^{n-k} \mathrm{d} r \\ = & d \binom{n}{1, k - 1} \int_0^1 r^{kd} (1 - r^d)^{n-k} \mathrm{d} r \\ = & nd \binom{n - 1}{k - 1} \int_0^1 r^{kd} \sum_{i=0}^{n-k} \binom{n-k}{i} (-r^d)^i \mathrm{d} r \\ = & nd \binom{n - 1}{k - 1} \sum_{i=0}^{n-k} \binom{n-k}{i} (-1)^i \int_0^1 r^{kd+id} \mathrm{d} r \\ = & nd \binom{n - 1}{k - 1} \sum_{i=0}^{n-k} \frac{\binom{n-k}{i} (-1)^i}{kd+id+1} \\ \end{array} \]

这样做的值应该是没错的，但是精度误差特别大 >__<

于是我们还需要继续化简……

我对如何操作二项式已经忘得差不多了，于是无意间拿起 CM 居然看到了这货：

对于函数 \(f(x)\) ，定义 \(\Delta^{(0)} f(x) = f(x)\) 。然后可以定义 \(\Delta^{(n)} f(x) = \Delta^{(n - 1)} f(x + 1) - \Delta^{(n - 1)} f(x)\) ，然后可以得到： \[\Delta^{(n)} f(x) = \sum_{k} \binom{n}{k} (-1)^{n-k} f(x+k)\]

注意到 \(\Delta^{(n)}f(x)\) 的表达式与要化简的那个式子中的比较像，考虑令 \(f(x) = \frac{1}{x}\) ， 用 \((-1)^{n-k} \Delta^{(n - k)} f(x)\) 来代替 \(\sum\) 。

\[\begin{array}{rl} & nd \binom{n - 1}{k - 1} \sum_{i=0}^{n-k} \frac{\binom{n-k}{i} (-1)^i}{kd+id+1} \\ = & n \binom{n - 1}{k - 1} (-1)^{n-k} \sum_{i=0}^{n-k} \frac{\binom{n-k}{i} (-1)^{n-k-i}}{k+i+\frac{1}{d}} \\ = & n \binom{n - 1}{k - 1} \Delta^{(n - k)} f(k+\frac{1}{d}) (-1)^{n-k} \\ \end{array}\]

由于 \(f(x) = \frac{1}{x}\) ，我们又有： \[\begin{array}{rcl} \Delta^{(1)} f(x) & = & \frac{-1}{x^{\bar{2}}} \\ \Delta^{(2)} f(x) & = & \frac{2}{x^{\bar{3}}} \\ \Delta^{(3)} f(x) & = & \frac{-6}{x^{\bar{4}}} \\ \end{array}\]

其中 \(x^{\bar{k}} = \prod_{i = 0}^{k - 1} (x+i)\)

可以找出规律（然后归纳法）\[\Delta^{(n)} f(x) = \frac{(-1)^n n!}{x^{\bar{n+1}}}\]

继续代入： \[\begin{array}{rl} & n \binom{n - 1}{k - 1} \Delta^{(n - k)} f(k+\frac{1}{d}) (-1)^{n-k} \\ = & n \binom{n - 1}{k - 1} \frac{(-1)^{n-k} (n-k)!}{(k+\frac{1}{d})^{\bar{n-k+1}}} (-1)^{n-k} \\ = & \frac{n!}{(k-1)! (k+\frac{1}{d})^{\bar{n-k+1}}} \\ = & \frac{n!}{(k-1)! \prod_{i=0}^{n-k} (k+i+\frac{1}{d})} \\ = & \frac{\prod_{i=0}^{n-k}(n-i)}{\prod_{i=0}^{n-k} (k+i+\frac{1}{d})} \\ = & \prod_{i=0}^{n-k} \frac{(n-i)}{k+i+\frac{1}{d}} \\ = & \prod_{i=k}^{n} \frac{i}{i+\frac{1}{d}} \\ = & \prod_{i=k}^{n} \frac{di}{di+1} \\ \end{array}\]

这样化简的结果和 xiaodao 的方法是一样的……真是太开心了 @_@ ……

Epilogue

这推导真是恶心死我了……

学的东西都忘光了怎么破……

写的公式太多了感觉会跪？ @dyh 求查错……

Markdown 里的替换

大概是为了防止 TeX 里面的 _ 和 ^ 被转义而写的。由于要改多次……还是先记下来吧。

\([^\]\)^ -> \1\^
\([^\]\)_ -> \1\_