在允许更新的同时从分布中随机抽样的高效算法？

Question

这是我前一段时间接受采访的问题,我找不到答案.

给定一些样本S1,S2,... Sn和它们的概率分布(或权重,无论它叫什么)P1,P2,... Pn,设计算法随机选择样本考虑其概率.我带来的解决方案如下:

1. 构建累积的权重数组Ci,例如

   C0 = 0; Ci = C [i-1] + Pi.

同时计算T = P1 + P2 + ... Pn.这需要O(n)时间

2. 生成均匀随机数R = T*random [0..1]
3. 使用二进制搜索算法,返回最小i,例如Ci> = R.结果是Si.它需要O(logN)时间.

现在的实际问题是:假设我想要改变其中一个初始权重Pj.如何在O(n)时间内做到这一点？其他数据结构是可以接受的,但随机抽样算法不应该比O(logN)差.

Answer 1

解决此问题的一种方法是重新考虑如何构建包含累积总计的二叉搜索树.不要构建二叉搜索树,而是考虑将每个节点解释如下:

• 每个节点都存储一系列专用于节点本身的值.
• 左子树中的节点表示从该范围左侧的概率分布中采样.
• 右子树中的节点表示从该范围右侧的概率分布中采样.

例如,假设我们的权重为事件A,B,C,D,E,F和G的3,2,2,2,1,1和1.我们构建这个二进制树,包含A,B,C, D,E,F和G:

               D
             /   \
           B       F
          / \     / \
         A   C   E   G

现在,我们用概率注释树.由于A,C,E和G都是叶子,我们给它们每个概率质量一:

               D
             /   \
           B       F
          / \     / \
         A   C   E   G
         1   1   1   1

现在,看B.树的树有2个被选中,A有3个被选中,而C有2个被选中的概率.如果我们将这些归一化到范围[0,1],则A占概率的3/7,B和C各占2/7.因此,我们让B的节点表示范围[0,3/7]中的任何内容都转到左子树,范围[3/7,5/7]中的任何内容都映射到B,并且范围内的任何内容[5/7,1)映射到右子树:

                   D
                 /   \
           B              F
 [0, 3/7) / \  [5/7, 1)  / \
         A   C          E   G
         1   1          1   1

类似地,让我们处理F.E具有被选择的权重2,而F和G各自具有被选择的概率权重1.因此,E的子树占这里概率质量的1/2,节点F占1/4,G的子树占1/4.这意味着我们可以将概率指定为

                       D
                     /   \
           B                        F
 [0, 3/7) / \  [5/7, 1)   [0, 1/2) / \  [3/4, 1)
         A   C                    E   G
         1   1                    1   1

最后,让我们看一下根.左子树的组合权重是3 + 2 + 2 = 7.右子树的组合权重是2 + 1 + 1 = 4.D本身的权重是2.因此左子树的概率为7/13在被挑选时,D有被挑选的概率为2/13,而右子树有被挑选的概率为4/13.因此,我们可以将概率确定为

                       D
           [0, 7/13) /   \ [9/13, 1)
           B                        F
 [0, 3/7) / \  [5/7, 1)   [0, 1/2) / \  [3/4, 1)
         A   C                    E   G
         1   1                    1   1

要生成随机值,请重复以下操作:

• 从根开始:
  • 选择[0,1]范围内的均匀随机值.
  • 如果它在左子树的范围内,则进入它.
  • 如果它在正确的子树的范围内,则进入它.
  • 否则,返回与当前节点对应的值.

树构建时,可以递归地确定概率本身:

• 对于任何叶节点,左和右概率为0.
• 如果内部节点本身具有权重W,则其左侧树具有总权重W _L,并且其右侧树具有总权重W _R,则左侧概率为(W _L)/(W + W _L + W _R)且右侧树具有权重W 概率是(W _R)/(W + W _L + W _R).

这种重新制定有用的原因在于它为我们提供了一种方法来更新每个概率更新的O(log n)时间的概率.特别是,如果我们更新一些特定节点的权重,让我们考虑一下不变量会发生什么变化.为简单起见,我们假设节点现在是一片叶子.当我们更新叶节点的权重时,叶节点的概率仍然是正确的,但它们对于它上面的节点是不正确的,因为该节点的一个子树的权重已经改变.因此,我们可以(在O(1)时间内)通过使用与上面相同的公式重新计算父节点的概率.但是那个节点的父节点不再具有正确的值,因为它的一个子树权重已经改变,所以我们也可以重新计算它的概率.这个过程一直重复到树的根,我们每层进行O(1)计算以纠正分配给每个边的权重.假设树是平衡的,因此我们必须进行O(log n)总工作以更新一个概率.如果节点不是叶节点,则逻辑相同; 我们只是从树的某个地方开始.

简而言之,这给了

• O(n)构建树的时间(使用自下而上的方法),
• O(log n)时间生成一个随机值,和
• O(log n)时间更新任何一个值.

希望这可以帮助!