Brief description:
…. 给定一个 $$p$$ 维的单位圆，随机在里面点 $$n$$ 个点。。。
。。求第 $$k$$ 远点的距离的期望。
Background:
。。。整理了一下聊天记录。。发现这个问题真是 Nice !。。。真是有助于提高智商。。。。）。
最早是 Diy 群里的 __Sisyphus 神牛提出的问题。。。我感觉有点意思。。
就追问了一下来源。。。是 The Elements of Statistical Learning 书第 23 页的一个栗子里轻描淡写提出的一个结论。。。。。
。原问题是。。
“The median distance from the origin to the closest data point … ” （问最近点的中位数。。。（这个带到分布函数里 =1/2 反解出来就行。。）
。。不过进一步考虑这个东西的期望的话确实有意思多了。。。
Analysis:
.我们对点按照到原点的距离从大到小排序。。。设 $$d_k$$ 表示 $$k$$ 远点的距离。。( 从 1 标号。。
。。首先最远点的期望非常好求。。。
。。.设 $$V^n(r)$$ 为半径为 $$r$$ 的 $$n$$ 维超球的体积。。.考虑 $$d_1$$ 的分布函数。。。。显然就是。
$$!P(d_1 \leq x) = \frac{V^n(x)}{V^n(1)} = x^{np} $$
（这一步需要用两个 $$n$$ 维球的体积做比。。虽然我们不知道 $$n$$ 维球体积公式具体是啥。。但是比值显然就是这个 blabla 。。
微分得到密度函数。
$$!P(d_1 = x) = npx^{np-1} $$
乘以 $$x$$ 再积分得到期望。。。
$$!E(d_1) = \int_{0}^{1} xP(d_1 = x) \mathrm{d}x = \int_{0}^{1} npx^{np} \mathrm{d}x = \frac{np}{np+1} $$
然后第 $$k$$ 远的期望就是。。
$$!E(d_k) = \prod_{i=n-k}^n \frac{ip}{ip+1}$$
So why ?。。。
。。。我们考虑第 $$k$$ 远点距离的期望已经得到了。。现在来求 $$k+1$$ 远的。。
那么就相当于在一个半径为第 $$k$$ 远期望的超球内部随机取 $$n-k$$ 个点。时的最远点距离的期望。。。。
。。所以最后结果就是一堆最远点的期望乘以来。。。。。是不是很好丽洁？。。。。
External link:
http://roosephu.github.io/2013/06/21/kth-point/
http://acm.hdu.edu.cn/showproblem.php?pid=4653
