某島

… : "…アッカリ~ン . .. . " .. .
September 3, 2013

圓周 k 短弧

[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/