美文网首页
破产问题与简单序贯检测

破产问题与简单序贯检测

作者: 老姚记事本 | 来源:发表于2020-10-20 01:17 被阅读0次

    本文是对Simple Sequential A/B Testing的解读。
    该方法归属序贯检测类,可以用于伯努利分布场景,随着抽样持续进行,判断接受零假设或备择假设(关于序贯检测)。

    理论依据——赌徒破产问题

    一个赌徒携带d元进入赌场,每次下注一元,胜利额外赢得一元,失败则输掉一元。假如赌博是公平的,赌徒在第n轮剩余0元的概率(记作R_{n,d})是多少?

    概率计算

    使用R_{n,d}来表示赌徒起始d元在第n轮输光的概率。
    总局:n,输:(n + d) / 2,胜:(n - d) / 2。

    1. 赌场可以借钱给赌徒的情况,此时为简单的排列组合关系。

    R_{n,d} = \binom{n}{(n + d)/ 2} * 2^{-n}

    1. 赌场不肯借钱给赌徒情况。

    R_{n,d} = \frac{d}{n}\binom{n}{(n + d)/ 2} * 2^{-n}

    这是简单序贯检测的基础,将在下面推导。

    随机游走和选举定理

    在此对第二种情况进行计算。

    1. 取纵坐标为钱,横坐标为赌博轮次,则过程为一维随机游走。举例:


      赌徒场景2
    2. 此时从A出发到K,满足条件路径数(中途不与0轴接触),等于从K出发到A的路径数。场景转换为从0开始,到d结束。


      转换
    3. 在满足中途不触碰0轴条件,第一步必须为正。则从J到A路径数等于从A到K路径数。


      镜像

      如图所示,每一条从J到第一个接触横轴的点的路径,总有一条从K出发到相同点的映射路径,后续都走相同路径。因此J到A经过横轴路径数等于K到A的路径数。

    4. 设从0出发,有p步向上,q步向下。根据3,满足不触碰横轴概率为:
      (\binom{p + q - 1}{p - 1} - \binom{p + q - 1}{p}) / \binom{p + q}{p} = \frac{p - q}{p + q}

    此公式被称为选举定理

    p + q = n, p - q = d带入,原问题最终结果为\frac{d}{n}\binom{n}{(n + d)/ 2} * 2^ {-n}

    简单序贯检测

    简单序贯检测是基于上面的结论产生的。

    与赌徒破产问题的关系

    均等流量的转化率型ab测试场景中,实验组、对照组随着时间推移,都会产生转化。在零假设下,下一次转化发生在实验组或对照组的概率是相等的。因此可以转换为赌徒破产问题。

    每轮次:下一次转化发生;
    每轮获胜者:下一次转化所在的组;
    破产的轮次n:实验组、对照组转换数之和;
    赌徒初始筹码d:因为转换数积累是从零开始的,不能直接套用。可以认为赌徒初始资本为0,输到-d时破产。

    假设检验设计

    以下仅介绍单尾情况,双尾的扩展请参考原文。

    原假设

    零假设(H0):实验组转化率等于对照组转化率(对应未破产情况);
    备择假设(H1):实验组转化率小于对照组转换率(对应破产情况)。

    假阳性控制(alpha)

    参考上文,在零假设假设下,第n轮赌徒破产概率为: R_{n,d} = \frac{d}{n}\binom{n}{(n + d)/ 2} * 2^{-n}
    在N轮及N轮之前,赌徒破产概率为:\sum_{n = 1} ^{N}R_{n,d}
    取上面的概率为alpha,通过控N和d的选取,可以控制假阳性水平。

    假阴性控制(beta)

    控制假阴性,需要预设期望的最小观测效果(mde,此处选相对效果)。当实际提升效果等于MDE时,假阴性概率等于预设值。
    在备择假设下,当实验组提升了mde时,下一次转化发生在实验概率为P_t = \frac {1 + mde}{2 + mde},对照组概率为P_c = \frac{1}{2 + mde}
    第n轮破产概率:R_{n,d} = \frac{d}{n}\binom{n}{(n + d)/ 2} * P_t^{(n - d) / 2}* P_t^{(n + d) / 2}
    在N轮及N轮之前,赌徒破产概率为:\sum_{n = 1} ^{N}R_{n,d}
    取上面的概率为功效(power),通过次N和d的选取,可以控制假阴性水平。

    选择结束条件

    联立上述不等式,使N和d满足:

    \sum_{n = 1} \frac{d}{n}\binom{n}{(n + d)/ 2} * 2^{-n} < \alpha
    \sum_{n = 1}\frac{d}{n}\binom{n}{(n + d)/ 2} * P_t^{(n - d) / 2}* P_t^{(n + d) / 2} > 1 - \beta

    不等式很难直接求解,可通过计算机遍历可能的N和d,找到合适的值。

    具体流程
    1. 实验开始,实验组、对照组从0开始计数;
    2. 每有一个转化,对应的组计数+1,并进行判断;
    3. 对照转化数 - 实验组转化数 >= d,接受备择假设;
    4. 对照转化数 + 实验组转化数 = N,接受原假设。

    优缺点

    优点

    1. 基于弱假设,易于理解和证明;
    2. 过程易于操作;
    3. 在低转换率时,需要样本量小于固定水平检验需要的样本量;
    4. 不存在“偷看”问题。

    缺点

    1. 只适用于近似伯努利分布场景;
    2. 结束条件难以直接计算,需要通过计算机遍历查找;
    3. 在高转化率时,需求样本量大于固定水平检验需要的样本量;
    4. 无法直接给出置信区间和P值。

    相关文章

      网友评论

          本文标题:破产问题与简单序贯检测

          本文链接:https://www.haomeiwen.com/subject/sjuapktx.html