Numpy：数组中元素之和大于或等于10的概率是多少？

Question

我正在尝试编写一个程序来计算 N array elements 的总和大于或等于 M number 的概率。在 N 数组中，数组的第一个元素是 N，而其他元素是 N-1（可以重复）。

例如：我的数组大小是 N=5 和 M=10，第一个元素总是 5，而其他元素从 1 到 4。所以它看起来像下面的迭代。因为除了第一个，其他元素是随机生成的，我需要找到 Sum>=10 or not?

的概率

    Random_Iteration1: Arr=[5, 3, 2, 1, 3] Sum = 13
    Random_Iteration2: Arr=[5, 1, 1, 1, 1] Sum = 9
    Random_Iteration3: Arr=[5, 1, 2, 2, 1] Sum = 11

我在Python中写了下面的代码：

    import numpy as np
    N=5 #array size
    M=10 
    arr = []
    arr.append([N])
    arr.append(np.random.choice(np.arange(1, N), size=N-1).tolist()) 
    arr = sum(arr,[]) #generates array such that 1st element is N, rest are randomly generated elements from 1 to N-1
    arr_sum = np.sum(arr) #gives array sum

    possibilities = N*N
    #numerator = I am not sure what to take here

如果有任何帮助，我将不胜感激。如果需要解释中的任何细节，请告诉我。谢谢。

Answer 1

您可以在 O(n(m+n)) 时间内精确计算。该问题等同于找出 n-1 个骰子的概率，每个骰子有 n-1 个面，总和至少为 m-n。 n 个 k 面骰子的概率分布由多项式的系数给出 (1+x+x^2+...+x^k)^n / k^n.

此代码迭代计算该多项式，丢弃与 x 的 m 或更大的幂对应的项。

迭代结束后，数组中的概率对应骰子和为0,1,2,..,m-1的概率，其和为1减去骰子和的概率至少是 m.

函数 prob_weird_sum 是计算给定问题结果的代码。

from fractions import Fraction as F

# Returns the probability that the sum of
# n IID uniform random variables that take
# values 1..k is greater than or equal to m.
def prob_sum_ge(n, k, m):
    if m <= 0: return 1
    p = [F(1)] + [0] * (m - 1)
    for _ in xrange(n):
        S = 0
        for i in xrange(m-1, -k-1, -1):
            if i >= 0:
                S += p[i]
            if i + k < m:
                S -= p[i+k]
                p[i+k] = S / k
    return 1 - sum(p)

# The probability that if you add n, and n-1
# uniform IID random numbers 1..n-1, you get
# at least m.
def prob_weird_sum(n, m):
    return prob_sum_ge(n-1, n-1, m-n)

print prob_weird_sum(3, 2)

程序的输出是：

255/256

Numpy：数组中元素之和大于或等于10的概率是多少？

Numpy: What is the probability that sum of elements in array is greater than or equal to 10?

python

algorithm

math

numpy

probability