c++ - 使用什么概率函数

Question

我想从向量中的“e”edges_in_sorted_order 中概率性地选择“n”条边。但我想在选择时使用概率。而且我也不想在开始时选择大边缘。

所以它就像在开始时对较小的边缘给予更多的权重，当我采取边缘时，我也会对更大的剩余边缘给予越来越多的权重。

我应该选择 n 和 e 的什么概率函数？

while( edgesTaken < n ) {
     for each edge i and edgesTaken < n
         probability = pdf( edgesTaken, i)
         if ( prob > THRESHOLD )
              take the edge
 }

Answer 1

您需要用于所需分布的分位数函数。使用标准生成器绘制一个随机数，得到均匀分布在 [0, 1) 中的 q。然后以q为参数调用分位数函数。生成的随机集将具有所需的分布。

Answer 2

第一条边为1的概率是choose(n-1,e-1)/choose(n,e)。

更一般地，第一条边为 k 的概率为 [choose(nk,e-1)/choose(n,e)] * 1/k

您可能还需要 1-k 中恰好有一条边的概率：[choose(nk,e-1)/choose(n,e)]

从这里我想你可以把事情结束了！

PS 只是为了解释一下，这三个函数给出了选择满足其条件的边的方式数与选择（n，e）的比率，即从 n 中选择 e 边的方式数。