2010年2月7日星期日

The impact of resampling to RSE in sampling algorithms

采样算法中,是否可重复采样对相对标准差的影响

在古典概型中有放回和无放回差别很大。在随机采样算法中,对已经采过的样本,是否还可以再采?
问题:
假设有N个零件,次品率为p(即有pN个次品)。现在已知N,要求通过采样率为q(检查qN次)算法来估计p。

有放回算法:
依次生成qN个独立同分布U[0,N)的随机数xi,检查第xi个零件是否为次品,记随机变量X为检查出的次品的个数。来求X的分布。
令Xi=1表示第xi个零件为次品,则X=X1+...+X_qN
P(Xi=1)=p,EXi=p,根据期望线性性,EX=EX1+EX_qN=pqN,DX=pqN(1-p)
相对标准差的平方RSE2为DX/(EX)^2=(1-p)/(pqN)

无放回算法:
一次从N个零件中随机抽取qN个零件,记其中次品个数为X,则X服从超几何分布
EX=pqN,DX=p(1-p)q(1-q)N,RSE2=(1-p)(1-q)/(pqN)

对比发现,两个算法的RSE2就差个(1-q),即相同采样率q下,无放回更精确。当然,对于千分之一的采样率,二者差别可以忽略,但是如果要采50%的样,最好用无放回算法了。这也符合物理直观。
但是不管有没有放回,RSE都关于p,q,N单调递减,因此,固定p(p来自问题域),可以通过调节qN来寻求性能与精度的平衡――
当N较小时,用比较大的q来维持精度,反正样本数qN也不大。
当N较大时,不需要很大的q,因为反正RSE2的分母上已经有个N了:)

没有评论: