5.1 雇用問題

5.2 指示器隨機(jī)變量

個(gè)人感覺與獨(dú)立重復(fù)試驗(yàn)類似

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

應(yīng)聘者問題的指示器隨機(jī)變量解法 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)$$

關(guān)于例題

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

逆序?qū)栴} 對于每一組數(shù)的組合，都有一半的概率為逆序，故其數(shù)學(xué)期望為C2n?12=n(n?1)/4$C_n^2 /cdot /frac 1 2 =n(n-1)/4$

5.3 隨機(jī)算法

含義 讓分布固定，而通過特定算法實(shí)現(xiàn)隨機(jī)化。

隨機(jī)排列數(shù)組

PERMUTE-BY-SROTING

RANDOMIZE-IN-PLACE

證明

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

保持：假設(shè)i次迭代前每種(i-1)排列出現(xiàn)概率為(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!}$

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

5.4 特征序列

問題：拋一枚標(biāo)準(zhǔn)硬幣n次，求最長連續(xù)正面的數(shù)學(xué)期望

思路： 類似夾逼準(zhǔn)則

證明過程：

O(lgn)

設(shè)連續(xù)擲硬幣k次，k=2lgn。

起始于某一位置，長度**大于等于**k的序列至多有n-k+1個(gè)，故開始于任一位置的概率總和小于等于 ∑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為長度的具體值。

顯然，當(dāng)j較大時(shí)P{Lj}$P/{L_j/}$較小，當(dāng)P{Lj}$P/{L_j/}$較大時(shí)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$$ 又因?yàn)?nobr>∑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。

顯然任一一組，結(jié)果為同一面（假設(shè)為正面）概率為 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ì)，因此 ∑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)$$

結(jié)論：特征序列長為lgn。

指示器隨機(jī)變量的近似結(jié)果：n?k+12k$/frac{n-k+1}{2^k}$，且?guī)雓=lgn時(shí)值近似符合要求。

5.5 在線雇傭問題

問題：只雇傭一次應(yīng)聘者，并且每次應(yīng)聘必須決定是否雇傭這個(gè)人。

實(shí)現(xiàn)思路：選擇一個(gè)正整數(shù)k，面試并拒絕前k個(gè)應(yīng)聘者，并雇傭后面第一個(gè)分?jǐn)?shù)比前k個(gè)應(yīng)聘者中分最高者還高的人，若沒有則雇傭最后一個(gè)人。問題轉(zhuǎn)化為尋找k的最優(yōu)值。

過程：

令P{Si}$P/{S_i/}$表示應(yīng)聘者為第i時(shí)面試成功的概率，Bi$B_i$表示最佳面試者為第i人的概率，M(j)$M(j)$表示前1~j人中的最高分，Oi$O_i$表示從k+1到i-1的應(yīng)聘者都小于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)$

求導(dǎo)，得k=n/e$k=n/e$