©2020-2024 ioDraw All rights reserved
<>1 条件期望
定义1（条件期望）：给定随机变量 X X X和 Y Y Y，则有如下条件期望 E [ X ] = E [ E [ X ∣ Y ] ]
\mathrm{E}[X]=\mathrm{E}\left[\mathrm{E}[X|Y]\right]E[X]=E[E[X∣Y]]如果 Y Y Y
是离散随机变量，则有 E [ X ] = ∑ y E [ X ∣ Y = y ] P { Y = y }
\mathrm{E}[X]=\sum\limits_{y}\mathrm{E}[X|Y=y]\mathrm{P}\{Y=y\}E[X]=y∑E[X∣Y=y]P
{Y=y}如果 Y Y Y是密度为 f Y ( y ) f_Y(y) fY(y)的连续随机变量，则有 E [ X ] = ∫ − ∞ ∞ E [ X ∣ Y
= y ] f Y ( y ) d y
\mathrm{E}[X]=\int_{-\infty}^{\infty}\mathrm{E}[X|Y=y]f_Y(y)dyE[X]=∫−∞∞E[X∣Y=y]
fY(y)dy
证明： 离散随机变量的证明方式与连续随机变量证明方式一致，具体的证明过程如下所示 ∑ y E [ X ∣ Y = y ] P ( Y = y ) = ∑ y
∑ x x P { X = x ∣ Y = y } P { Y = y } = ∑ y ∑ x x P { X = x , Y = y } P { Y = y
} P ( Y = y ) = ∑ y ∑ x x P { X = x , Y = y } = ∑ x x ∑ y P { X = x , Y = y } =
∑ x x P { X = x } = E [ X ] \begin{aligned}\sum\limits_y
\mathrm{E}[X|Y=y]\mathrm{P}(Y=y)&=\sum\limits_y\sum\limits_{x}x
\mathrm{P}\{X=x|Y=y\}\mathrm{P}\{Y=y\}\\&=\sum\limits_y
\sum\limits_{x}x\frac{\mathrm{P}\{X=x,Y=y\}}{\mathrm{P}\{Y=y\}}\mathrm{P}(Y=y)\\&=\sum\limits_{y}\sum\limits_xx\mathrm{P}\{X=x,Y=y\}\\&=\sum\limits_{x}x\sum\limits_{y}\mathrm{P}\{X=x,Y=y\}\\&=\sum\limits_{x}x\mathrm{P}\{X=x\}=\mathrm{E}[X]\end{aligned}
y∑E[X∣Y=y]P(Y=y)=y∑x∑xP{X=x∣Y=y}P{Y=y}=y∑x∑xP{Y=y}P{X=x,Y=y}P(Y=y)=y∑x∑
xP{X=x,Y=y}=x∑xy∑P{X=x,Y=y}=x∑xP{X=x}=E[X]证毕。
<>2 快速排序算法分析
假设有 n n n个不同的值 x 1 , ⋯ , x n x_1,\cdots,x_n x1,⋯,xn
的一个集合，将它们按照递增次序排序，完成它的一个有效的算法是快速排序算法。当 n = 2 n=2 n=2时，该算法比较此二值，将它们置于合适的次序。当 n >
2 n>2n>2时，它开始在 n n n值中随机地选取一个，譬如 x i x_i xi，然后将其它的 n − 1 n-1 n−1个值与 x i x_i xi
比较，以 S i S_i Si记小于 x i x_i xi的元素的集合， S i ˉ \bar{S_i} Siˉ记大于 x i x_i xi
的元素即集合，然后分别对集合 S i S_i Si和 S i ˉ \bar{S_i} Siˉ分别排序，所以，最后的次序由集合 S i S_i Si
元素的次序、 x i x_i xi、集合 S i ˉ \bar{S_i} Siˉ元素的次序排列组成。
假定元素集合是 10 10 10， 5 5 5， 8 8 8， 2 2 2， 1 1 1， 4 4 4， 7 7 7，随机选取一个（即这 7 7 7
个值中的每一个选取的概率都是 1 7 \frac{1}7{} 71）。假如值 4 4 4被选取，然后将其它 6 6 6个值得每一个与 4 4 4做比较得到
{ 2 , 1 } , 4 , { 10 , 5 , 8 , 7 } \{2,1\},4,\{10,5,8,7\}{2,1},4,{10,5,8,7}将集合
{ 2 , 1 } \{2,1\}{2,1}排序得到 1 , 2 , 4 , { 10 , 5 , 8 , 7 } 1,2,4,\{10,5,8,7\} 1,2
,4,{10,5,8,7}其次，在 { 10 , 5 , 8 , 7 } \{10,5,8,7\} {10,5,8,7}中随机选取一个，譬如取到的是 7 7 7
，而且将其它三个值与 7 7 7作比较得到 1 , 2 , 4 , 5 , 7 , { 10 , 8 } 1,2,4,5,7,\{10,8\} 1,2,4,5,
7,{10,8}最后将 { 10 , 8 } \{10,8\} {10,8}得到 1 , 2 , 4 , 5 , 7 , 8 , 10
1,2,4,5,7,8,101,2,4,5,7,8,10该算法有效性的一个度量是做次数的期望。假定以 M n M_n Mn记 n n n
个不同值的一个集合的快速排序算法的比较次数的期望。令比较次数的随机变量为 X X X，取到的第 j j j小的值的随机变量为 Y Y Y，则此时可以得到 M
n M_nMn的一个递推式 M n = E [ X ] = E [ E [ X ∣ Y ] ] = ∑ j = 1 n 1 n E [ X ∣ Y ]
M_n=\mathrm{E}[X]=\mathrm{E}[\mathrm{E}[X|Y]]=\sum\limits_{j=1}^n
\frac{1}{n}\mathrm{E}[X|Y]Mn=E[X]=E[E[X∣Y]]=j=1∑nn1E[X∣Y]若初始的取值是第 j j j
小的值，则较小的集合的容量是 j − 1 j-1 j−1，较大的集合的容量是 n − j n-j n−j。因此，由于对于选定的初始的取值需要作 n − 1
n-1n−1次比较，可以得到 M n = ∑ j = 1 n 1 n ( n − 1 + M j − 1 + M n − j ) = n − 1 + 2 n
∑ k = 1 n − 1 M k
M_n=\sum\limits_{j=1}^n\frac{1}{n}(n-1+M_{j-1}+M_{n-j})=n-1+\frac{2}{n}\sum\limits^{n-1}_{k=1}M_k
Mn=j=1∑nn1(n−1+Mj−1+Mn−j)=n−1+n2k=1∑n−1Mk其中 M 0 = 0 M_0=0 M0=0，等价于 n M
n = n ( n − 1 ) + 2 ∑ k = 1 n − 1 M k nM_n = n(n-1)+2\sum\limits_{k=1}^{n-1}M_kn
Mn=n(n−1)+2k=1∑n−1Mk为了求解上式，用 n + 1 n+1 n+1代替 n n n得到 ( n + 1 ) M n + 1 = ( n
+ 1 ) n + 2 ∑ k = 1 n M k (n+1)M_{n+1}=(n+1)n+2\sum\limits_{k=1}^nM_k(n+1)Mn+1=
(n+1)n+2k=1∑nMk因此，经过相减得到 ( n + 1 ) M n + 1 − n M n = 2 n + 2 M n
(n+1)M_{n+1}-nM_n=2n+2M_n(n+1)Mn+1−nMn=2n+2Mn进一步则有 ( n + 1 ) M n + 1 = ( n +
2 ) M n + 2 n (n+1)M_{n+1}=(n+2)M_n+2n(n+1)Mn+1=(n+2)Mn+2n所以 M n + 1 n + 2 =
2 n ( n + 1 ) ( n + 2 ) + M n n + 1
\frac{M_{n+1}}{n+2}=\frac{2n}{(n+1)(n+2)}+\frac{M_n}{n+1}n+2Mn+1=(n+1)(n+2)2n
+n+1Mn将此式迭代给出 M n + 1 n + 2 = 2 n ( n + 1 ) ( n + 2 ) + 2 ( n − 1 ) n ( n + 1
) + M n − 1 n = ⋯ = 2 ∑ k = 0 n − 1 n − k ( n + 1 − k ) ( n + 2 − k )
\begin{aligned}\frac{M_{n+1}}{n+2}&=\frac{2n}{(n+1)(n+2)}+\frac{2(n-1)}{n(n+1)}+\frac{M_{n-1}}{n}\\&=\cdots\\&=2\sum\limits_{k=0}^{n-1}\frac{n-k}{(n+1-k)(n+2-k)}\end{aligned}
n+2Mn+1=(n+1)(n+2)2n+n(n+1)2(n−1)+nMn−1=⋯=2k=0∑n−1(n+1−k)(n+2−k)n−k从而
M n + 1 = 2 ( n + 2 ) ∑ k = 0 n − 1 n − k ( n + 1 − k ) ( n + 2 − k ) = 2 ( n +
2 ) ∑ i = 1 n i ( i + 1 ) ( i + 2 ) , n ≥ 1
M_{n+1}=2(n+2)\sum\limits_{k=0}^{n-1}\frac{n-k}{(n+1-k)(n+2-k)}=2(n+2)\sum\limits_{i=1}^n\frac{i}{(i+1)(i+2)},\quad
n\ge 1Mn+1=2(n+2)k=0∑n−1(n+1−k)(n+2−k)n−k=2(n+2)i=1∑n(i+1)(i+2)i,n≥1利用恒等式
i [ ( i + 1 ) ( i + 2 ) ] = 2 ( i + 2 ) − 1 ( i + 1 )
\frac{i}{[(i+1)(i+2)]}=\frac{2}{(i+2)}-\frac{1}{(i+1)}[(i+1)(i+2)]i=(i+2)2−(i+
1)1，则可以得到如下近似 M n + 1 = 2 ( n + 2 ) [ ∑ i = 1 n 2 i + 2 − ∑ i = 1 n 1 i + 1 ]
∼ 2 ( n + 2 ) [ ∫ 3 n + 2 2 x d x − ∫ 2 n + 1 1 x d x ] = 2 ( n + 2 ) [ 2 ln
( n + 2 ) − ln ( n + 1 ) + ln 2 − 2 ln 3 ] = 2 ( n + 2 ) [ ln ( n + 2 )
+ ln n + 2 n + 1 + ln 2 − 2 ln 3 ] ∼ 2 ( n + 2 ) ln ( n + 2 )
\begin{aligned}M_{n+1}&=2(n+2)\left[\sum\limits_{i=1}^n\frac{2}{i+2}-\sum\limits_{i=1}^n\frac{1}{i+1}\right]\\&\sim2(n+2)\left[\int_3^{n+2}\frac{2}{x}dx-\int_2^{n+1}\frac{1}{x}dx\right]\\&=2(n+2)[2\ln(n+2)-\ln(n+1)+\ln
2 - 2\ln 3]\\&=2(n+2)\left[\ln(n+2)+\ln\frac{n+2}{n+1}+\ln2 - 2\ln
3\right]\\&\sim 2(n+2)\ln(n+2)\end{aligned}Mn+1=2(n+2)[i=1∑ni+22−i=1∑ni+11
]∼2(n+2)[∫3n+2x2dx−∫2n+1x1dx]=2(n+2)[2ln(n+2)−ln(n+1)+ln2−2ln3]=2(n+2)[ln(n+
2)+lnn+1n+2+ln2−2ln3]∼2(n+2)ln(n+2)进而可以知道快速排序算法的复杂度的期望是 O ( n log n )
O(n\log n)O(nlogn)。