java - 经过 K 次尝试后，数字 N 减少为非正值的概率

Question

假设我们有一个整数 N 。在每个 K试验中，该数字会从均匀区间 [0, M] 中减去一个随机整数。 (因此，如果我们有 M = 5 ，那么每个试验中的数字 N 可以减少 0 、 1 、 2 、 3 、 4 或 5 ，每个都有一个概率 1/6 )。数字 N 出现的概率是多少？ K 之后将小于或等于 0考验？例如，对于 N=2 , M=1和K=3答案是0.5 .

我可以编写一个强力解决方案，简单地枚举每个排列，总共 (M+1)^K并在 N 时计数案例最终是 <= 0从中减去给定排列中的所有数字。但对于这个问题，M和K可能达到 1000，然后这个复杂度就变成 1000^(1000)这是棘手的。

所以我想知道是否有一些数学公式可以帮助我避免生成所有排列？

Answer 1

这是一个计算所需概率的程序

N = 2
M = 1
K = 3

count = [0] * (N+1)
prev = [0] * (N+1)

count[0] = 1 # empty set

for i in range(K):
    # move count to prev
    for index in range(N+1):
        prev[index] = count[index]
        count[index] = 0
    
    # calculate new counts
    for prevSum in range(N+1):
        for value in range(M+1):
            newSum = min(N, prevSum+value)
            count[newSum] += prev[prevSum]
            
ans = (count[N] / pow(M+1, K))
print(ans)

working code link

• 在这里，我们跟踪 count[] 数组中加起来达到给定总和的集合数量的计数
• 任何相加值大于 N 的集合都会添加到 count[N]

这是如何工作的？

• 最初，count[0] = 1，因为我们只有空集{}
• (K = 1):尝试向所有现有集合中添加一个元素:{} + 0, {} + 1。我们得到 {0}, {1} 因此 count[0] = 1, count[1] = 1
• (K = 2):现在再次向所有现有集合添加一个元素:{0} + 0, {0} + 1, {1} + 0, {1} + 1 。我们得到 {0,0},{0,1},{1,0},{1,1} 所以 count[0] = 1, 计数[1] = 2，计数[2] = 1
• (K = 3):现在再次向所有现有集合添加一个元素。我们会得到 {0,0,0}, {0,0,1}, {0,1,0}, {1,0,0}, {0, 1, 1}, {1, 0 , 1}, {1,1,0}, {1,1,1}。 所以 count[0] = 1、count[1] = 3、count[2] = 4
• 在最后一步中，我们还将 {1,1,1} 添加到 count[2]，因为我们添加了总和为 > 的所有集合= N 到 计数[N]
• 最后，为了计算概率，我们将 count[N](总和为 >=N 的所有集合的计数)除以所有可能集合的计数，即(M+1)^K

复杂度为O(N*M*K)。在最坏的情况下N=M*K，因此时间复杂度可以重写为:O((M*K)^2)

---

优化1:

如果您记下 K 每次迭代的 count[] 数组，您会发现一个有趣的观察结果:

M=1

sum: 0 1 2 3 4
K=0: 1 0 0 0 0 (if empty consider value as 0 from now on)
K=1: 1 1
K=2: 1 2 1
K=3: 1 3 3 1
K=4: 1 4 6 4 1


M=2

sum: 0  1  2  3  4  5  6  7  8
K=0: 1
K=1: 1  1  1
K=2: 1  2  3  2  1
K=3: 1  3  6  7  6  3  1
K=4: 1  4 10 16 19 16 10  4  1

这里的观察是:

通过维护先前 M 值的滚动总和，我们可以编写代码的优化版本:

N = 2
M = 1
K = 3
maxValue = M*K

count = [0] * (maxValue+1)
prev = [0] * (maxValue+1)

count[0] = 1 # empty set

for i in range(K):
    # move count to prev
    for index in range(maxValue+1):
        prev[index] = count[index]
        count[index] = 0
    
    rollingSum = 0
    
    # calculate new counts
    for Sum in range(maxValue+1):
        rollingSum += prev[Sum]
        if (Sum > M):
            rollingSum -= prev[Sum - (M + 1)]
        count[Sum] = rollingSum
            

# add all counts of sets whose sum is >= N
ans = sum(count[N:]) / pow(M+1,K)
print(ans)

working code link

该方法的时间复杂度为O(M*(K^2))