解决分区问题的修改版本

Question

所以我正在寻找一个原则上类似于计算大 N 的分区的问题。我的问题类似于以下假设问题。

假设我有一个随机变量 X，它的可能结果为 1,2,...,10，每个结果的发生概率为 P1,P2,...,P10。我的假设问题：如果我生成 20 个随机且独立的 X 样本并将它们加在一起，则 10,11,12,... 200.

的总和的可能性是多少？

我想到的一些理论上可行但计算上不太可能的方法如下。

想法1）列出200的分区。删除任何使用数字大于10的分区类别。计算每个类别的概率并对每个总和求和（总和= 10,11，...，200 ).这是小 N 的 ezpz，完全和完全疯狂的 'huge in this context' N 像 200。

思路2）列出所有可能的20项样本结果（即1-1-1-1-1-1-1-1-1-2,1-1-1-1-1-1 -1-1-1-2 等），记下每个概率，并对每个总和求和（总和 = 10、11、...、200）。同样，对于小 N 的 ezpz，在这种情况下完全不可行。

我也有下面的想法，但是没能实现。思路 3) 修改你最喜欢的 'generate the partitions' 算法，使得分区中不能使用任何大于 10 的数字。原则上与想法 1 类似，但是我们生成一个小列表，而不必 trim 向下一个巨大的列表。我对这个想法有两个问题，a) 我不确定如何为任何分区生成算法执行此操作，以及 b) 即使我可以，我也不相信它在计算上是可行的。

关于如何解决这个问题的任何要点？归根结底，它类似于 [列举所有可能的结果，计算每个结果的概率，汇总每个总和的概率，然后你就有了答案] 中的任何其他问题。然而样本space实在是太大了

这很容易通过 monte carlo 来近似，但这种方法给我留下了不好的印象，因为很多理论上可能的结果都不会出现，即使是 100 亿次以上的迭代也不会出现。

关于如何解决这个问题有什么想法吗？

[我对语言的选择很灵活，但我倾向于尽可能使用 Python]

Answer 1

随机生成100000，统计每个值apparend.If你要具体值，用二项分布。这是一个 python 模拟：

def random_int_by_probas_sum(probas_cum, r):
    """
    @param probas_cum cumulation probablities of the 10 random numbers.
    @param r random number
    return the value of r-percentage. for example r=0.3, it will return 3, r=0.8, it will return 8
    """
    for index in range(len(probas_cum)):
        if r <= probas_cum[index]:
            return index

import numpy as np
import pandas as pd
import random

nums = np.arange(0, 10, 1)
#
probas = [0.05, 0.15, 0.07, 0.13, 0.09, 0.11, 0.08, 0.12, 0.04, 0.16]
probas_cum = [0.05, 0.2, 0.27, 0.4, 0.49, 0.6, 0.68, 0.8, 0.84, 1]
random_count = 1000000
sums = []

for _ in range(random_count):
    sum_step = 0
    for i in range(10):
        r = random.random()
        sum_step += random_int_by_probas_sum(probas_cum, r)
    sums.append(sum_step)

sums = pd.Series(sums)
sums.value_counts()

Answer 2

根据亚伦评论中的想法写了一个递归解决方案。这使用以前的 N 值的解决方案来找到更大的 N 值。

与其他答案不同，此方法不是近似值。

import itertools
from collections import defaultdict, namedtuple

numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
probs = [0.1] * 10
Distribution = namedtuple('Distribution', 'numbers probs')


def find_prob(dist, n=1):
    if n == 0:
        # If you draw 0 numbers, you have a 100% change of getting zero.
        return Distribution([0], [1])
    else:
        # Find probability of each number, drawing one fewer sample
        dist_b = find_prob(dist, n - 1)
        # Combine two distributions. Add up all probabilities for getting
        # the same number.
        prob_for_num = defaultdict(float)
        for a, p_a in zip(dist.numbers, dist.probs):
            for b, p_b in zip(dist_b.numbers, dist_b.probs):
                num = a + b
                # Probability of p(A&B) = p(A) * p(B)
                prob = p_a * p_b
                prob_for_num[num] += prob

        # Split numbers and probabilities into two lists
        numbers, probs = zip(*prob_for_num.items())
        return Distribution(numbers=numbers, probs=probs)
sol = find_prob(Distribution(numbers=numbers, probs=probs), 20)

我以一种简单的方式设置了它，从 1 到 10 的每个数字都有相等的概率。不过，数字不必是连续的，概率也不必相等。我这样做只是为了简单起见。

N=20 很容易总结出来。它在 N=1000 左右开始减速。如果您想总结比这更多的样本，您可能需要研究更有效的递归方法。

当我对均匀分布的 20 个样本求和时，我得到了这个概率图：

...正如预期的那样，这是正态分布。

解决分区问题的修改版本

Solving modified version of the Partition problem

python

combinations

combinatorics