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

从 xiaodao 空间上看到的……

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

Problem

dd 维单位球体中随机选 nn 个点，到球心 kk 远点距离球心的期望是多少？

Solution

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

（维基百科） dd 维单位球体的体积是

Vd(R)=πd2RdΓ(d2+1)=CdRdV_d(R) = \frac{\pi^{\frac{d}{2}}R^d}{\Gamma(\frac{d}{2}+1)} = C_d R^d

其中 CdC_d 为与 dd 相关的常数。

根据“维”的定义，我们有距离为 rr 的点的密度为

ρ(r)=V′_d(r)Vd(1)=drd−1\rho(r) = \frac{V'\_d(r)}{V_d(1)} = d r^{d - 1}

于是 kk 远点的期望是：

(n1,k−1)∫∗01rρ(r)(rd)k−1(1−rd)n−kdr=d(n1,k−1)∫01rkd(1−rd)n−kdr=nd(n−1k−1)∫01rkd∑∗i=0n−k(n−ki)(−rd)idr=nd(n−1k−1)∑∗i=0n−k(n−ki)(−1)i∫01rkd+iddr=nd(n−1k−1)∑∗i=0n−k(n−ki)(−1)ikd+id+1\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)f(x) ，定义 Δ(0)f(x)=f(x)\Delta^{(0)} f(x) = f(x) 。然后可以定义 Δ(n)f(x)=Δ(n−1)f(x+1)−Δ(n−1)f(x)\Delta^{(n)} f(x) = \Delta^{(n - 1)} f(x + 1) - \Delta^{(n - 1)} f(x) ，然后可以得到：

Δ(n)f(x)=∑_k(nk)(−1)n−kf(x+k)\Delta^{(n)} f(x) = \sum\_{k} \binom{n}{k} (-1)^{n-k} f(x+k)

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

nd(n−1k−1)∑∗i=0n−k(n−ki)(−1)ikd+id+1=n(n−1k−1)(−1)n−k∑∗i=0n−k(n−ki)(−1)n−k−ik+i+1d=n(n−1k−1)Δ(n−k)f(k+1d)(−1)n−k\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)=1xf(x) = \frac{1}{x} ，我们又有：

Δ(1)f(x)=−1x2ˉΔ(2)f(x)=2x3ˉΔ(3)f(x)=−6x4ˉ\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}

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

可以找出规律（然后归纳法）

Δ(n)f(x)=(−1)nn!xn+1ˉ\Delta^{(n)} f(x) = \frac{(-1)^n n!}{x^{\bar{n+1}}}

继续代入：

n(n−1k−1)Δ(n−k)f(k+1d)(−1)n−k=n(n−1k−1)(−1)n−k(n−k)!(k+1d)n−k+1ˉ(−1)n−k=n!(k−1)!(k+1d)n−k+1ˉ=n!(k−1)!∏∗i=0n−k(k+i+1d)=∏∗i=0n−k(n−i)∏∗i=0n−k(k+i+1d)=∏∗i=0n−k(n−i)k+i+1d=∏∗i=knii+1d=∏∗i=kndidi+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\_