Python X >= Y 的概率算法，其中 X 和 Y 的分布基于 2 个采样点数组

Question

我想估计从数组 x 中随机抽取的数据点大于或等于从数组 y 中随机抽取的数据点的概率。我想通过比较所有可能的值对来做到这一点。

我认为一个简单的实现应该是这样的：

def probability_x_gte_y(array_x, array_y):
    gte_counter = 0
    n_comparisons = len(array_x) * len(array_y)
    for vx in array_x:
        for vy in array_y:
            if vx >= vy:
                gte_counter += 1
    return gte_counter / n_comparisons

但我相信有一种更有效的方法来计算这个，特别是考虑到 array_x 和 array_y 中两组点的分布很可能分离得很好（换句话说，两个一维数组之间的重叠相对于覆盖的点的总范围可能很小。）

Answer 1

如果您的数组足够小，那么详尽的计算是可行的，这是正确的。如果你的数组太大，那么你可以改为执行一个模拟，它会收敛正确的概率，给你一个估计。

如果您无法穷尽并想要一个精确的答案，那么您需要将问题分解成更小的块。例如，假设 X 和 Y 中的所有点都在区间 (0,1) 中。如果我们将该区间分成十个子区间，(0,0.1),...(0.9,1)；然后我们可以用尽每个子区间并研究条件概率。从理论上讲，这甚至可以减少到只包含单个点的区间，但我假设在耗尽大小和条件概率树大小之间会有一个权衡。

Answer 2

一个更快的实现是对数组之一进行排序，因此可以更快地找到大于给定值的值的数量，这要归功于二分查找。此实现在 O(n log n) 中运行，而原始实现在 O(n * n).

中运行

def probability_x_gte_y_opt2(array_x, array_y):
    n_comparisons = len(array_x) * len(array_y)
    sorted_x = np.sort(array_x)
    gte_counter = n_comparisons - np.searchsorted(sorted_x, array_y).sum()
    return gte_counter / n_comparisons

在大小为 5000 的随机数组上，这比我的机器快 3890 倍（2.69 秒对 0.69 毫秒）！

请注意，这可以在 O(n) 时间内编写算法运行：您可以在两个数组上使用 基数排序，然后是两个排序数组之间的自定义计数合并。但是，Numpy 还没有实现基数排序，并且无法使用 Numpy 轻松实现快速计数合并。

Python X >= Y 的概率算法，其中 X 和 Y 的分布基于 2 个采样点数组

Python algorithm for probability that X >= Y where distributions for X and Y are based on 2 arrays of sampled points

python

numpy

probability

loss-function