问题来源:《算法(第4版)》习题1.2.18
#include
class Accumulator
{
public:
Accumulator()
{
m = 0.0;
s = 0.0;
n = 0;
}
void addDataValue(double x)
{
n++;
s = s + 1.0 * (n - 1) / n * (x - m) * (x - m);
m = m + (x - m) / n;
}
double mean() //样本期望
{
return m;
}
double var() //样本方差
{
return s / (n - 1); //样本方差为什么除以的是n - 1而不是n请自行百度
}
double stddev() //样本标准差
{
return sqrt(var());
}
private:
double m;
double s;
int n;
};
公式推导: 期望定义:
E
n
=
∑
i
=
1
n
x
i
n
E_n=\frac{\sum\limits_{i=1}^nx_i}{n}
En=ni=1∑nxi 期望的递推公式:
E
n
=
∑
i
=
1
n
x
i
n
=
∑
i
=
1
n
−
1
x
i
+
x
n
n
=
(
n
−
1
)
E
n
−
1
+
x
n
n
=
E
n
−
1
+
x
n
−
E
n
−
1
n
E_n=\frac{\sum\limits_{i=1}^nx_i}{n}=\frac{\sum\limits_{i=1}^{n-1}x_i+x_n}{n}=\frac{(n-1)E_{n-1}+x_n}{n}=E_{n-1}+\frac{x_n-E_{n-1}}{n}
En=ni=1∑nxi=ni=1∑n−1xi+xn=n(n−1)En−1+xn=En−1+nxn−En−1 方差定义:
S
n
2
=
∑
i
=
1
n
(
x
i
−
E
n
)
2
n
−
1
S^2_n=\frac{\sum\limits_{i=1}^n(x_i-E_n)^2}{n-1}
Sn2=n−1i=1∑n(xi−En)2 方差的递推公式推导: 为了方便,设
F
n
=
∑
i
=
1
n
(
x
i
−
E
n
)
2
F_n=\sum\limits_{i=1}^n(x_i-E_n)^2
Fn=i=1∑n(xi−En)2
F
n
−
F
n
−
1
=
∑
i
=
1
n
(
x
i
−
E
n
)
2
−
∑
i
=
1
n
−
1
(
x
i
−
E
n
−
1
)
2
=
∑
i
=
1
n
(
x
i
−
E
n
−
1
+
E
n
−
1
−
E
n
)
2
−
∑
i
=
1
n
−
1
(
x
i
−
E
n
−
1
)
2
=
(
x
n
−
E
n
−
1
)
2
+
∑
i
=
1
n
−
1
(
x
i
−
E
n
−
1
)
2
+
2
(
E
n
−
1
−
E
n
)
∑
i
=
1
n
(
x
i
−
E
n
−
1
)
+
∑
i
=
1
n
(
E
n
−
1
−
E
n
)
2
−
∑
i
=
1
n
−
1
(
x
i
−
E
n
−
1
)
2
=
(
x
n
−
E
n
−
1
)
2
+
2
(
E
n
−
1
−
E
n
)
(
n
E
n
−
n
E
n
−
1
)
+
n
(
E
n
−
1
−
E
n
)
2
\begin{aligned} F_n-F_{n-1} & =\sum\limits_{i=1}^n(x_i-E_n)^2-\sum\limits_{i=1}^{n-1}(x_i-E_{n-1})^2 \\ & =\sum\limits_{i=1}^n(x_i-E_{n-1}+E_{n-1}-E_n)^2-\sum\limits_{i=1}^{n-1}(x_i-E_{n-1})^2 \\ & =(x_n-E_{n-1})^2+\sum\limits_{i=1}^{n-1}(x_i-E_{n-1})^2+2(E_{n-1}-E_n)\sum\limits_{i=1}^n(x_i-E_{n-1})+\sum\limits_{i=1}^n(E_{n-1}-E_n)^2-\sum\limits_{i=1}^{n-1}(x_i-E_{n-1})^2 \\ & =(x_n-E_{n-1})^2+2(E_{n-1}-E_n)(nE_n-nE_{n-1})+n(E_{n-1}-E_n)^2\\ \end{aligned}
Fn−Fn−1=i=1∑n(xi−En)2−i=1∑n−1(xi−En−1)2=i=1∑n(xi−En−1+En−1−En)2−i=1∑n−1(xi−En−1)2=(xn−En−1)2+i=1∑n−1(xi−En−1)2+2(En−1−En)i=1∑n(xi−En−1)+i=1∑n(En−1−En)2−i=1∑n−1(xi−En−1)2=(xn−En−1)2+2(En−1−En)(nEn−nEn−1)+n(En−1−En)2 由期望的递推公式:
n
E
n
−
n
E
n
−
1
=
x
n
−
E
n
−
1
nE_n-nE_{n-1}=x_n-E_{n-1}
nEn−nEn−1=xn−En−1 代入上面的式子里,得
F
n
−
F
n
−
1
=
(
x
n
−
E
n
−
1
)
2
+
2
(
E
n
−
1
−
E
n
)
(
x
n
−
E
n
−
1
)
+
n
(
E
n
−
1
−
E
n
)
2
=
(
x
n
−
E
n
−
1
)
2
+
(
E
n
−
1
−
E
n
)
(
2
x
n
−
2
E
n
−
1
+
n
E
n
−
1
−
E
n
)
=
(
x
n
−
E
n
−
1
)
2
+
(
E
n
−
1
−
E
n
)
(
2
x
n
−
2
E
n
−
1
−
x
n
+
E
n
−
1
)
=
(
x
n
−
E
n
−
1
)
2
+
(
E
n
−
1
−
E
n
)
(
x
n
−
E
n
−
1
)
=
(
x
n
−
E
n
−
1
)
(
x
n
−
E
n
−
1
+
E
n
−
1
−
E
n
)
=
(
x
n
−
E
n
−
1
)
(
x
n
−
E
n
)
\begin{aligned} F_n-F_{n-1} & =(x_n-E_{n-1})^2+2(E_{n-1}-E_n)(x_n-E_{n-1})+n(E_{n-1}-E_n)^2\\ & =(x_n-E_{n-1})^2+(E_{n-1}-E_n)(2x_n-2E_{n-1}+nE_{n-1}-E_n)\\ & =(x_n-E_{n-1})^2+(E_{n-1}-E_n)(2x_n-2E_{n-1}-x_n+E_{n-1})\\ & =(x_n-E_{n-1})^2+(E_{n-1}-E_n)(x_n-E_{n-1})\\ & =(x_n-E_{n-1})(x_n-E_{n-1}+E_{n-1}-E_n)\\ & =(x_n-E_{n-1})(x_n-E_n) \end{aligned}
Fn−Fn−1=(xn−En−1)2+2(En−1−En)(xn−En−1)+n(En−1−En)2=(xn−En−1)2+(En−1−En)(2xn−2En−1+nEn−1−En)=(xn−En−1)2+(En−1−En)(2xn−2En−1−xn+En−1)=(xn−En−1)2+(En−1−En)(xn−En−1)=(xn−En−1)(xn−En−1+En−1−En)=(xn−En−1)(xn−En) 所以,
F
n
=
F
n
−
1
+
(
x
n
−
E
n
−
1
)
(
x
n
−
E
n
)
F_n=F_{n-1}+(x_n-E_{n-1})(x_n-E_n)
Fn=Fn−1+(xn−En−1)(xn−En) 而
x
n
−
E
n
=
x
n
−
(
E
n
−
1
+
x
n
−
E
n
−
1
n
)
=
n
−
1
n
(
x
n
−
E
n
−
1
)
\begin{aligned} x_n-E_n & =x_n-(E_{n-1}+\frac{x_n-E_{n-1}}{n})\\ & =\frac{n-1}{n}(x_{n}-E_{n-1}) \end{aligned}
xn−En=xn−(En−1+nxn−En−1)=nn−1(xn−En−1) 最后,
F
n
=
F
n
−
1
+
n
−
1
n
(
x
n
−
E
n
−
1
)
2
F_n=F_{n-1}+\frac{n-1}{n}(x_n-E_{n-1})^2
Fn=Fn−1+nn−1(xn−En−1)2
|