[mathjax]
Brief description:
…. 给定一个单位圆周，随机在里面点 $latex n$ 个点。。确立 $latex n$ 段圆弧。
。。求第 $latex k$ 短的圆弧的长度的期望。
Background:
。。。用代数语言叙述就是：
。。n 个变量 $$x_1, x_2, \ldots, x_n$$ ，满足 $$0 \leq x_i$$ 且 $$\sum_{i=1}^{n} x_i = 1 $$ 。求 $$x_i$$ 中第 $$k$$ 小的期望。
fotile 提出的一个问题。。。我前一阵子也也考虑过。。当时得出的结论是。。把圆周推广到高维球面后。。和二维情况不在一个难度等级。。。
。。。。现在二维已经得到了比较好的处理。。。这里记录一下。。。
Analysis:
。。。作为 “k-th xxx in circle” 系列第二弹。。。
。。和之前一样。。设 $$d_k$$ 为第 $$k$$ 短的长度。。。先考虑 $$d_1$$ 的分布函数。。。设 $$d_1$$ 至少是 $$x$$ 。那么我们先取出 $$nx$$ 预存起来。。。。之后在剩下的 $$(1 – nx)$$ 里。。随机设置 $$n-1$$ 个点以得到 $$n$$ 段弧。。。
$$!P_n (d_1\geq x) = (1 – nx)^{n-1} $$
微分得到密度函数。。。
$$!P_n (d_1=x) = (n-1)(1 – nx)^{n-2} $$
乘以 $$x$$ 积分搞出期望。。注意要使得 $$(1 – nx)$$ 有意义。。积分上限只能到 $$\frac{1}{n}$$
$$!\begin{align} E_n(d_1) &= \int_0^{\frac{1}{n}} xP_n(d_1 = x) \mathrm{d}x\ &= \int_0^{\frac{1}{n}} x(n-1)(1-nx)^{n-2}\mathrm{d}x \ &= \frac{1-n}{n} \int_0^1 nx(1-nx)^{n-2} \mathrm{d}(1-nx) \ &= \frac{n-1}{n}\int_0^1 (1-x)x^{n-2} \mathrm{d}x \ &= \frac{n-1}{n} (\frac{1}{n-1} – \frac{1}{n}) \ &= \frac{1}{n^2} \end{align} $$
。。。对于。。。$$E_n(d_k) $$ … 枚举 $$d_1$$ 的值。。设为 $$x$$。。为了保证剩下 $$n-1$$ 个数比 $$x$$ 大。。我们同样把这些值预存起来。。得到剩下 $$n-1$$ 个变量的和是 $$1 – nx$$ 。。并且仍然保持均匀分布。。可以用 $$E_{n-1}(d_{k-1})$$ 表达。。。于是此时第 $$k$$ 小的期望是 $$x + (1-nx)E_{n-1}(d_{k-1})$$ 。。再乘以 $$x$$ 对应的概率。。。也就是。。。
$$!\begin{align} E_n(d_k) &= \int_0^{\frac{1}{n}} (x + (1-nx)E_{n-1}(d_{k-1})) P_n(d_1=x) \mathrm{d}x \ &= \int_0^{\frac{1}{n}} x P_n(d_1=x) \mathrm{d}x + E_{n-1}(d_{k-1})\int_0^{\frac{1}{n}} (1-nx)P_n(d_1=x) \mathrm{d}x \ &= \frac{1}{n^2} + \frac{n-1}{n} E_{n-1}(d_{k-1}) \end{align} $$
。。以上得到了递推式。。。
。。。最后将递推式展开得到 close-form 。。。
$$! E_n(d_k) = \frac{1}{n} \sum_{i=n-k}^{n} \frac{1}{i} = \frac{H_n – H_{n-k}}{n} $$
。。。调和级数实在是太优美了！。。）
External link:
https://www.13331.org/495.html
http://roosephu.github.io/2013/09/02/kth-min/
