有没有办法用概率树而不是模拟来计算概率

Question

我想在 python 中实现一个函数，它给出了我以下问题的确切概率（如果可能的话，以分数形式）：

你有一个包含 8 个元素的列表，比方说 l=[1,2,3,4,5,6,7,8]，然后你在该列表中连续取 k 个数字，如果该数字是 1、2、3 或 4，则将其从该列表中删除，否则你让那个清单保持原样。每个数字出现的概率都相等

我想计算在这 n 次尝试中，至少有数字 1 的概率以及有 1 和 2 的概率。

对于 n=1，得到 1 的概率是 1/8

对于 n=2，得到 1 的概率是 1/8 + 4/8 * 1/8 +3/8 * 1/7= 27/112

有 1 和 2 是 2 * 1/8 * 1/7 = 1/28

等..

但是，我无法将该概率形式化为公式。我试图用算法计算它，但它并不简单。

我能够模拟它以获得近似值，但我对此并不十分满意。

def amalsimu2(adapt,n=int(1e6)):
    prob_to_find_both=0
    prob_to_find_one=0
    for _ in range(n):
        l=[i for i in range(1,9)]
        rec=[]
        for _ in range(adapt):
            draw=l[rd.randint(0,len(l)-1)]
            rec.append(draw)
            if draw<5:
                l.remove(draw)
        if 1 in rec:
            prob_to_find_one+=1
            if 2 in rec:
                prob_to_find_both+=1
    return [round(prob_to_find_one/n*100,3), round(n/prob_to_find_one,3)],[round(prob_to_find_both/n*100,3), round(n/prob_to_find_both,3)]

我稍微研究了 python 中的树，但我不知道这是否是一个好的处理方法。

如果您对如何公式化我想要计算的概率有任何想法，或者如果您对如何使用 python 算法进行处理有很好的想法，我将非常感激

Answer 1

它更像是概率图而不是树，但这取决于您如何定义状态（图中的节点）。下面的代码将“状态”定义为仍然可以选择的整数元组。最大的优势是只有 16 种可能的状态（取决于已经选择了 {1, 2, 3, 4} 的哪个子集），状态越少，速度越快。

缺点是可能的状态太少限制了可以回答的问题。例如，没有任何状态记录是否曾经选择过 5。但是我不知道你所说的“等”是什么意思，你的描述和代码都只询问了prob_to_find_one和prob_to_find_both，这里使用的状态足以回答这些问题。

def crunch():
    from fractions import Fraction
    from collections import defaultdict

    step = 0
    state2prob = {tuple(range(1, 9)) : Fraction(1)}
    while True:
        step += 1
        new_state2prob = defaultdict(Fraction)
        for state, prob in state2prob.items():
            nchoices = len(state)
            for choice in state:
                newstate = state
                if 1 <= choice <= 4:
                    newstate = list(state)
                    newstate.remove(choice)
                    newstate = tuple(newstate)
                new_state2prob[newstate] += prob / nchoices
        state2prob = new_state2prob
        assert sum(state2prob.values()) == 1
        prob1 = prob12 = Fraction(0)
        for state, prob in state2prob.items():
            if 1 not in state:
                prob1 += prob
                if 2 not in state:
                    prob12 += prob
        print(f"{step=}")
        print(f"    {prob1=} {float(prob1):7.2%}")
        print(f"    {prob12=} {float(prob12):7.2%}")

输出开始是这样的：

step=1
    prob1=Fraction(1, 8)  12.50%
    prob12=Fraction(0, 1)   0.00%
step=2
    prob1=Fraction(27, 112)  24.11%
    prob12=Fraction(1, 28)   3.57%
step=3
    prob1=Fraction(545, 1568)  34.76%
    prob12=Fraction(115, 1176)   9.78%
step=4
    prob1=Fraction(146201, 329280)  44.40%
    prob12=Fraction(43739, 246960)  17.71%
step=5
    prob1=Fraction(36652993, 69148800)  53.01%
    prob12=Fraction(13765027, 51861600)  26.54%
step=6
    prob1=Fraction(8796724649, 14521248000)  60.58%
    prob12=Fraction(3876980411, 10890936000)  35.60%
step=7
    prob1=Fraction(2047820152657, 3049462080000)  67.15%
    prob12=Fraction(1015122839923, 2287096560000)  44.38%
step=8
    prob1=Fraction(466169430547001, 640387036800000)  72.79%
    prob12=Fraction(252512187968939, 480290277600000)  52.57%
step=9
    prob1=Fraction(104336675177661793, 134481277728000000)  77.58%
    prob12=Fraction(60499089868078627, 100860958296000000)  59.98%

请注意，虽然 Fraction 类型会自动转换为最低项，但分子和分母会迅速变大。这是精确的有理算术。

有没有办法用概率树而不是模拟来计算概率

Is there a way to calculate probability with probability tree instead of simulation

python

tree

list

probability

python-3.x