一种简单的序贯AB测试方法

Sequential AB testing

在做AB测试时，为了避免出现重复显著性检验的情况，我们会预先设定一个样本值，只有到流量达到样本阈值时，才会进行统计检验。

这又引申出了一个问题：有没有一种AB测试方法，可以不用提前设置流量阈值，并可以在当实验组效果明显好于对照组的时候，能够提前停止实验？

一般而言，Sequential AB testing 需要用到序贯分析sequential probability ratio test，但是，在
even miller博客上记录了以下一种简单方法，这种方法也是可行的。

以下是该方法的流程：

• 1.实验开始前，选定一个数字N
• 2.对两个实验均分流量进行测试
• 3.记录A实验的成功数，记为T，记录B实验的成功次数，记为C
• 4.$T-C>1.96*\sqrt{N}​$ 时停止实验，说明A实验效果优于B实验
• 5.$T+C>N$ 时停止实验，说明无明显差异

原理：随机游走，反射定理、ballot theorem及近似分布

以下内容主要来自Feller’s Introduction to Probability book

从$（0,0）$到达$（n,x）$的随机游走

投掷一枚均匀的硬币，正面为+1，负面为-1，记n为投掷次数，x为累积分数。

对于某一时刻$（n，x）$，定有$p$次为$+1$，$q$次为$-1$，则

$$n=p+q，x=p-q$$

则容易得到

$$N_{n,x}=\binom{p+q}{p}=\binom{n}{\frac{n+x}{2}}$$

若不存在$n、x$满足上述条件，则$N_{n,x}=0$

反射定理

令$A=(a,b)$,$B=(c,d)$,则$A'=（a,-b)$接触$x$轴到达$B$的路径数和$A$接触x轴到达$B$路径数一样多

则此时，明显地，从$（0，0）$出发且不与$x$轴相交到达$（n,x)$的的路径数和从$（1，1）$出发不与x轴相交到达$（n,x）$的路径数一样多，并记为$r_{n,x}$。

ballot theorem

我们把$（1，1）$开始到达$（n，x）$的所有路径数记为$N_{n-1，x-1}$，把$（1，-1）$开始到达$（n，x）$的所有路径数记为$N_{n-1，x+1}$。显然$N_{n-1，x+1}$就是从$（1，1）$开始接触或穿过x轴到达$（n，x）​$的路径数

则有

$$N_{n-1，x+1} +r_{n,x} =N_{n-1，x-1}$$

则有

$$r_{n,x} =N_{n-1，x-1}-N_{n-1，x+1} =\binom{p+q-1}{p-q-1}-\binom{p+q-1}{p-q+1}=\frac{x}{n}N_{n,x}=\frac{x}{n}\binom{n}{\frac{n+x}{2}}$$

也就是说，不接触x轴的路径占所有路径的$\frac{x}{n}$.

类似地，当把$x$轴换成是直线$y=x$时，从$（0，0）$出发，不接触$y=x$到达$（n,x）$的路径数也为$\frac{x}{n}\binom{n}{\frac{n+x}{2}}$

limit theorem for first passages

$$令a_k =b(v+k;2v,\frac{1}{2})，则a_0=b(v;2v,\frac{1}{2})=\binom{2v}{v},且有\\ a_k =a_0\frac{v(v-1)..(v-k+1)}{(v+k)(v+k-1)(v+1)}=a_0\prod_{i=1}^k\frac{v-k+i}{v+i}=a_0\prod_{i=1}^k(1-\frac{k}{v+i}) \\当v很大时， 有1+\frac{j}{v} \approx e^{j/v},a_k \approx a_0\prod_{i=1}^k(1-\frac{k}{v})\approx a_0e^{-k^2/v} \\由stering公式 :n!\approx\sqrt{2\pi n}\frac{n}{e}n,可得: \\a_0 = 2^{-2v}\frac{(2v)!}{(v!)^2} \approx 2^{-2v}\frac{\sqrt{2\pi}(2v)^{2v+\frac{1}{2}}e^{-2v}}{2\pi v^{2v+1}e^{-2v}}\approx\frac{1}{\sqrt{\pi v}} \\ 综上所述，有 P_{n,x} = \frac{x}{n}\binom{n}{\frac{n+x}{2}}2^{-n}=\frac {x}{n}{a(x/2)}\approx \sqrt{\frac{2}{\pi}}\frac{x}{\sqrt {n^3} }e^{\frac{-x^2}{2n}} \\则 \sum_1^n {P_{n,x}} \approx \int{P_{n,x}}d_x \\ \int{P_{n,x}}d_x =\int_1^\infty\sqrt{\frac{2}{\pi}}\frac{x}{\sqrt{n^3} }e^{\frac{-x^2}{2n}}\\ 令t=\frac{x}{\sqrt{n}},则 \\ 原式=2\int_{-x}^x\sqrt{\frac{1}{2\pi}} e^\frac{-t^2}{2}dt=2(1-U(x)) \\观察可得此为正态分布积分形式 \\则对于 \sum_1^n {P_{n,x}}<\alpha \\有 x<Z_{1-\frac{\alpha}{2}}N；当\alpha=0.05时，Z_{1-\frac{\alpha}{2}}=1.96$$

场景：赌徒输光问题与AB测试实验

ballot theorm 可以用来解决一下问题:

赌徒输光问题

假设有一个有x枚金币的赌徒，初始有$x​$ 枚金币，每次胜率为$0.5​$，可以看到，赌徒正好在第$n​$轮输光所有金币的概率为

$$P_{n,x}= \frac{x}{n}\binom{n}{\frac{n+x}{2}}2^{-n}$$

而赌徒在第n轮前输掉所有金币的概率

$$\sum{P_{n,x}}= \sum_{n=1}^N \frac{x}{n} {n \choose (n+x)/2}2^{-n}$$

引申：AB测试

同样的，我们可以用ballot theorem来解释一个初始分数为0的玩家，不断投掷硬币$（正面+1分，反面-1分）$，在第n轮时首次达到$x$分的概率为

$$P_{n,x}= \frac{x}{n}\binom{n}{\frac{n+x}{2}}2^{-n}$$

同样的，玩家前$n$轮能达到$x$分的概率为

$$\sum{P_{n,x}}= \sum_{n=1}^N \frac{x}{n} {n \choose (n+x)/2}2^{-n}$$

此时，我们假设通过AB测试来玩这个游戏，则若两个实验的效果没有差别，则AB测试会近似这一过程。

统计检验

对于$AB​$测试这一过程，我们期待一个实验组比对照组的效果要提升$\delta​$，则

$$p = \frac{p_t}{p_c+p_t} = \frac{p_t/p_c}{1+p_t/p_c} = \frac{1}{1+(1+\delta)} = \frac{1+\delta}{2+\delta}$$

对于AB测试的过程

$$H_0：p_c = p_t ;H_1:p_t>p_c \\等价于 \\H_0：p = \frac{1+\delta}{2+\delta}=\frac{1}{2} ;H_1:p>\frac{1}{2}$$

参数计算

为了保证犯第一类错误和第二类错误的概率，可以构建以下不等式组：

$$\sum_{n=1}^N \frac{d^*}{n}{n \choose (n+d^*)/2}\left(\frac{1}{2+\delta}\right)^{(n-d^*)/2} \left(\frac{1+\delta}{2+\delta}\right)^{(n+d^*)/2} > 1 - \beta \\ \sum_{n=1}^N \frac{d^*}{n} {n \choose (n+d^*)/2}2^{-n} < \alpha$$

通过迭代运算，我们可以计算出停止实验所需要的$d^*​$ 和$N​$；通过近似分布，我们可以的得到$d^*=Z_{1-\frac{\alpha}{2}}N​$；并最终得到N。

最后, 对于两个实验成功的次数T和C，如果在T+C达到N之前达到T-C达到$d^*$时，则拒绝$H_0$