從1到N中隨機抽取一個數（N為上限，不被抽取）作為新的上限繼續抽取，直到上限為1。求總抽取次數的期望？

01-21

從1到N（N為上限，不被抽取）個整數中隨機抽取一個數作為新的上限，繼續抽取，求抽到1總共所需次數的期望

設上限為 $n$ 時，還需抽取的期望次數為 $f(n)$ 。

顯然 $f(1) = 0$ ， $f(n) = 1 + frac{1}{n-1} sum_{i=1}^{n-1} f(i)$ 。

解此遞推式得 $f(n) = sum_{i=1}^{n-1} frac{1}{i}$ （可手算幾項觀察得到規律，再用數學歸納法證明）。

另解：當上限為 $n$ 時，有 $frac{1}{n-1}$ 的概率把上限縮小到 $n-1$ ，這種情況下，連帶著第一次，一共需要抽取 $1 + f(n-1)$ 次。

另有 $frac{n-2}{n-1}$ 的概率把上限直接縮小到 $n-1$ 以下（不含），這種情況跟一開始上限就是 $n-1$ 是等價的，一共需要抽取 $f(n-1)$ 次。

於是有 $f(n) = frac{1}{n-1} left[ 1 + f(n-1) ight] + frac{n-2}{n-1} f(n-1) = f(n-1) + frac{1}{n-1}$ ，立即得到結論。

N=1 E=0基礎條件

N=2 E=1x1=1

N=3 E=0.5x1+0.5x2=1.5

N=4 E=0.33x1+0.33x2+0.33x2.5=1.83

觀察

N=1 E=0

N=2 E=1

N=3 E=1+0.5

N=4 E=1+0.5+0.33

...

N=n E=1+0.5+...+1/(n-1)

驗證

N=n時 E=En

N=n+1時 E=((E1+1)+...+(En+1))/n

得到遞推關係En+1=(E1+...En+n)/n

帶入觀察得到的En通項

左側En+1=1+...+1/n

右側(E1+E2+...+En+n)/(n-1)

整理得((n-1)/1+(n-2)/2+...+2/(n-2)+1/(n-1)+n)/n

再整理((n/1+n/2+...+n/n)/n

也就是右側=1+1/2+...+1/n=左側

觀察得到的En滿足遞推關係式子

綜上。

可以直接解通項，先佔一坑。爪機打公式不方便望見諒。

題主已經得出了

E(n)=[ E(1)+E(2)+E(3)+...+E(n-1) ]/n + 1 這樣的遞推關係，分母是 n 還是 n - 1 不再深究。

令 S 為 E 的前綴和，即 S(n) = E(1) + ... + E(n)。

即可得

S(n) - S(n-1) = S(n-1) / n + 1

S(n) = S(n-1) (n+1)/n + 1

S(n) / (n+1) = S(n - 1) / n + 1 / (n+1)

再次換: 令 T(n) = S(n) / (n + 1)，代入上式

T(n) = T(n - 1) + 1 / (n+1)

至此可以直接用一個求和寫出 T 。

最後把 T 代回 E

E(n) = T(n-1) + 1

即可得出一個還算漂亮的表達式。

分母不是 n 的話沒算，但是應該類似。

馬爾可夫過程，全期望公式。占坑