這個(gè)答案是log(n),以e為底數(shù).
我們設(shè)置n個(gè)隨機(jī)變量：X1、X2、……、Xn
其中,Xi 表示：
若 Xi=1,則：第i個(gè)抽出的卡片是前i個(gè)中最大的,也就是第i個(gè)卡片將放在右手邊.
否則 Xi=0.
令隨機(jī)變量Y為最終右手邊卡片的數(shù)量,則：
Y = X1+X2+...+Xn
E(Y) = E(X1) + E(X2) + ...+ E(Xn)
下面我們證：E(Xi) = 1/i
n個(gè)卡片隨機(jī)排列,一共有n!種,我們求第i個(gè)是前i個(gè)中最大的.
把這n!種分類,按照前i個(gè)卡片所組成的集合.
也就是假設(shè)我們已知前i個(gè)是什么卡片,但不知次序,考慮第i個(gè)最大的比例.
當(dāng)已知前i個(gè)是什么卡片,但不知次序時(shí),總共有：i!(n-i)!種.
第i個(gè)是前i個(gè)里最大的,那么第i個(gè)也就確定了,剩下n-1 個(gè)不確定,一共有：(i-1)!(n-i)!種.
所以,比例是：[(i-1)!(n-i)!] / [i!(n-i)!] = 1/i
這個(gè)比例與我們的分類,也就是前i個(gè)具體是什么無關(guān),所以每個(gè)分類都是 1/i.
所以,最后這個(gè) Xi=1 的概率就是 1/i,你可以按我們的分類用一下全概率公式.
所以,E(Xi) = 1×(1/i) + 0×(1-1/i) = 1/i
所以,E(Y) = 1/1 + 1/2 + 1/3 + ...+ 1/n
這是調(diào)和序列,當(dāng)n趨于無窮大時(shí),逼近 log(n),以e為底數(shù).