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)dy E[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>2
n>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,10
1,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_n
Mn的一个递推式
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-1
n−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_k
nMn=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 1
Mn+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)。
本文转载自: https://blog.csdn.net/qq_38406029/article/details/122648243
版权归原作者 鬼道2022 所有， 如有侵权，请联系我们删除。
版权归原作者 鬼道2022 所有， 如有侵权，请联系我们删除。