<>1 Conditional expectation
definition 1（ Conditional expectation ）： Given random variable X X X and Y Y Y, The following conditions are expected E [ X ] = E [ E [ X ∣ Y ] ]
\mathrm{E}[X]=\mathrm{E}\left[\mathrm{E}[X|Y]\right]E[X]=E[E[X∣Y]] If Y Y Y
Is a discrete random variable , Then there 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} If Y Y Y Yes, the density is f Y ( y ) f_Y(y) fY(y) Continuous random variable , Then there 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
prove ： The proof of discrete random variables is consistent with that of continuous random variables , The specific proof process is as follows ∑ 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] Zheng Bi .
<>2 Analysis of quick sorting algorithm
Suppose there is n n n Different values x 1 , ⋯ , x n x_1,\cdots,x_n x1,⋯,xn
A collection of , Sort them in ascending order , An effective algorithm to complete it is fast sorting algorithm . When n = 2 n=2 n=2 Time , The algorithm compares the two values , Put them in the right order . When n >
2 n>2n>2 Time , It started in n n n Randomly select one of the values , for example x i x_i xi, Then put the others n − 1 n-1 n−1 Values and x i x_i xi
compare , with S i S_i Si Record less than x i x_i xi Collection of elements , S i ˉ \bar{S_i} Siˉ Remember greater than x i x_i xi
The elements of the are collections , Then set the S i S_i Si and S i ˉ \bar{S_i} Siˉ Sort separately , therefore , The final order is determined by the set S i S_i Si
Order of elements , x i x_i xi, aggregate S i ˉ \bar{S_i} Siˉ The elements are arranged in order .
Assume that the element set is 10 10 10, 5 5 5, 8 8 8, 2 2 2, 1 1 1, 4 4 4, 7 7 7, Pick one at random （ That is 7 7 7
The probability of selecting each of the values is 1 7 \frac{1}7{} 71）. If value 4 4 4 Selected , Then put the others 6 6 6 Worth every one with 4 4 4 Make a comparison
{ 2 , 1 } , 4 , { 10 , 5 , 8 , 7 } \{2,1\},4,\{10,5,8,7\}{2,1},4,{10,5,8,7} Set
{ 2 , 1 } \{2,1\}{2,1} Sort to get 1 , 2 , 4 , { 10 , 5 , 8 , 7 } 1,2,4,\{10,5,8,7\} 1,2
,4,{10,5,8,7} secondly , stay { 10 , 5 , 8 , 7 } \{10,5,8,7\} {10,5,8,7} Select one at random , For example, what you get is 7 7 7
, And compare the other three values with 7 7 7 By comparison 1 , 2 , 4 , 5 , 7 , { 10 , 8 } 1,2,4,5,7,\{10,8\} 1,2,4,5,
7,{10,8} Finally { 10 , 8 } \{10,8\} {10,8} obtain 1 , 2 , 4 , 5 , 7 , 8 , 10
1,2,4,5,7,8,101,2,4,5,7,8,10 One measure of the effectiveness of the algorithm is the expectation of the number of times . Assume to M n M_n Mn remember n n n
The expectation of the comparison times of a set of fast sorting algorithms with different values . Let the random variable of the number of comparisons be X X X, Get the second j j j The small value of the random variable is Y Y Y, Then you can get M
n M_nMn A recursive formula of 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] If the initial value is No j j j
Small value , The capacity of the smaller set is j − 1 j-1 j−1, What is the capacity of a larger set n − j n-j n−j. therefore , Since the selected initial value needs to be changed n − 1
n-1n−1 Secondary comparison , Can get 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 among M 0 = 0 M_0=0 M0=0, Equivalent to 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 To solve the above equation , use n + 1 n+1 n+1 replace n n n obtain ( 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 therefore , Obtained by subtraction ( 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 Further, there are ( 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 therefore 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 This formula is given iteratively 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 thus
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 Using identity
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, The following approximation can be obtained 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) Then we can know that the expectation of the complexity of the quick sorting algorithm is O ( n log n )
O(n\log n)O(nlogn).
Technology