SPRT可控制两种错误的证明

2021-11-27 本文已影响0人老姚记事本

之前知道SPRT是什么和怎么用，但是不知道怎么证明它是对的，最近搞懂了记录一下。

1. SPRT简介

SPRT是在二战中由Wald发明的，最初用于检验炮弹质量。

如果X1, X2,...是iid的分布为P的随机变量，H0 : P = P0， H1：P= P1
SPRT抽样数量为：
$N = inf\{n \ge 1: R_n \geq A\ or\ R_n \leq B \}$
其中A > 1 > B > 0，被称为停止边界，根据α、β选取。
其中Rn为似然比：
$R_n = \prod_{i=1}^{n}\frac{f_1(X_i)}{f_0(X_i)}$
RN >= A时接受H1，RN <= B时接受H0。

2. 鞅的定义

设X和Y是两个随机过程，满足以下条件则过程X是关于Y的鞅。
若对每个n >=0 :
(1) E(|Xn|) < 无穷
(2) Xn是Y0, Y1, ... Yn的函数
(3) E(Xn+1 | Y0,...Yn) = Xn

3. Doob's martingale inequality

设{Xn; n >=0} 为鞅或非负下鞅，那么：
$P(\sup_{0<k<n}|X_k| \ge C) \leq \frac{ E( |X_n|)}{C}$

4. 一类错误被控制的证明

此时H0为真时，则：

(1) 似然比过程是一个鞅

$E(R_{1} | X_1) = \int^{+\infty}_{{-\infty}}\frac{f_1(x_{1})}{f_0(x_{1})}{f_0(x_{1})}dx = 1$
$E(R_{n+1} | X_1,..X_n) = E(R_n\frac{f_1(X_{n + 1})}{f_0(X_{n+1})}) = R_nE(\frac{f_1(X_{n + 1})}{f_0(X_{n+1})}) = R_n\int^{+\infty}_{{-\infty}}\frac{f_1(x_{n + 1})}{f_0(x_{n+1})}{f_0(x_{n+1})}dx \\= R_n$

(2) 带入Doob's martingale inequality

$P(\sup_{0<i<n}|R_n| \ge \frac{1}{\alpha}) \leq \frac{E(|R_n|)}{\frac{1}{\alpha}} = \alpha$

其他

同理也可以证明H1为真时，对二类错误的控制是正确的。
mSPRT使用分部积分法展开，也可以用类似的过程证明。

PS：欢迎对ab testing希望知其然知其所以然的朋友私信我，交个朋友以后共同探讨。