5.1 雇用問題

5.2 指示器隨機變量

個人感覺與獨立重復試驗類似

核心：將問題分解為子問題

應聘者問題的指示器隨機變量解法 E[X]=∑x=1nxP{X=x}=∑i=1nE[xi]=∑i=1n1/i=lnn+O(1) $$E[X]=/sum_{x=1}^n xP /{ X=x /}= /sum_{i=1}^n E[x_i]=/sum_{i=1}^n 1/i=lnn+O(1)$$

關于例題

帽子核對問題 對于每個顧客，拿到自己的帽子的概率為1/n$1/n$，故其數學期望為∑ni=11/n=1$/sum_{i=1}^n 1/n =1$

逆序對問題 對于每一組數的組合，都有一半的概率為逆序，故其數學期望為C2n?12=n(n?1)/4$C_n^2 /cdot /frac 1 2 =n(n-1)/4$

5.3 隨機算法

含義 讓分布固定，而通過特定算法實現隨機化。

隨機排列數組

PERMUTE-BY-SROTING

RANDOMIZE-IN-PLACE

證明

初始化：初始化賦值i=2（涉及討論i=1的空數組，故先顯式交換一次），即對于每個1排列，長度為1的子數組包含這種排列的概率為 (n?1)!/n!=1/n$(n-1)!/n!=1/n$，第一次循環迭代前循環不變式成立。

保持：假設i次迭代前每種(i-1)排列出現概率為(n?i+1)!/n!$(n-i+1)!/n!$，則第i次迭代后，概率為1n?i+1?(n?i+1)!n!$/frac{1}{n-i+1} /cdot /frac{(n-i+1)!}{n!}$

終止：終止時，i=n+1，子數組任一排列概率為1/n!$1/n!$

5.4 特征序列

問題：拋一枚標準硬幣n次，求最長連續正面的數學期望

思路： 類似夾逼準則

證明過程：

O(lgn)

設連續擲硬幣k次，k=2lgn。

起始于某一位置，長度**大于等于**k的序列至多有n-k+1個，故開始于任一位置的概率總和小于等于 ∑i=1n?k+11/2k≤∑i=1n?k+11/n2<∑i=1n1/n2=1/n $$/sum_{i=1}^{n-k+1} {1/2}^k /leq /sum_{i=1}^{n-k+1} 1/n^2 < /sum_{i=1}^n 1/n^2 = 1/n$$

由定義知 E[L]=∑j=0njP{Lj}=∑j=0k?1jP{Lj}+∑j=knjP{Lj} $$E[L]=/sum_{j=0}^n jP/{L_j/}=/sum_{j=0}^{k-1} jP/{L_j/} + /sum_{j=k}^n jP/{L_j/}$$ 其中j為長度的具體值。

顯然，當j較大時P{Lj}$P/{L_j/}$較小，當P{Lj}$P/{L_j/}$較大時j較小，故 E[L]<∑j=0k?1kP{Lj}+∑j=knnP{Lj}<k∑j=0k?1P{Lj}+1 $$E[L]</sum_{j=0}^{k-1} kP/{L_j/} + /sum_{j=k}^n nP/{L_j/}<k/sum_{j=0}^{k-1}P/{L_j/}+1$$ 又因為∑k?1j=0P{Lj}<1$/sum_{j=0}^{k-1}P/{L_j/}<1$，原式小于O(k)=O(lgn)$O(k)=O(lgn)$

Ω(lgn)

把n次投擲劃分為n/s組，每組擲s次，s取lgn/2。

顯然任一一組，結果為同一面（假設為正面）概率為 1/2s=1/n√ $$1/2^s=1//sqrt n$$

故每組都不是同一面概率為 (1?1/n√)n/s?1≤e(n/s?1)/n√=O(e?lgn=O(1/n)) $$(1-1/ /sqrt n)^{n/s-1} /leq e^{(n/s-1)/ /sqrt n} = O(e^{-/lg n} = O(1/n))$$

對j值較小的部分，其值忽略不計，因此 ∑j=0njP{Lj}≥∑j=snjP{Lj}≥s∑j=snP{Lj}≥s(1?O(n))=Ω(lgn) $$/sum_{j=0}^n jP/{L_j/} /geq /sum_{j=s}^n jP/{L_j/} /geq s/sum_{j=s}^nP/{L_j/} /geq s(1-O(n))=/Omega (/lg n)$$

結論：特征序列長為lgn。

指示器隨機變量的近似結果：n?k+12k$/frac{n-k+1}{2^k}$，且帶入k=lgn時值近似符合要求。

5.5 在線雇傭問題

問題：只雇傭一次應聘者，并且每次應聘必須決定是否雇傭這個人。

實現思路：選擇一個正整數k，面試并拒絕前k個應聘者，并雇傭后面第一個分數比前k個應聘者中分最高者還高的人，若沒有則雇傭最后一個人。問題轉化為尋找k的最優值。

過程：

令P{Si}$P/{S_i/}$表示應聘者為第i時面試成功的概率，Bi$B_i$表示最佳面試者為第i人的概率，M(j)$M(j)$表示前1~j人中的最高分，Oi$O_i$表示從k+1到i-1的應聘者都小于M(k)$M(k)$的概率。

顯然 P{S}=∑i=k+1nP{Si} $$P/{S/}=/sum_{i=k+1}^{n}P/{S_i/}$$ P{Bi}=1/n $$P/{B_i/}=1/n$$ P{Oi}=k/(i?1) $$P/{O_i/}=k/(i-1)$$ P{Si}=P{Bi}?P{Oi} $$P/{S_i/}=P/{B_i/} /cdot P/{O_i/}$$

解得 P{S}=kn(lnn?lnk)$P/{S/}= /frac{k}n (/ln n - /ln k)$

求導，得k=n/e$k=n/e$