带权圆形图的总路径概率

Question

假设有一个游戏，每一步有可能走几条路径，具体取决于骰子的扔出结果。根据结果，可能向前、向后或停留在原地。最终（即使扔无数次），图形将导向最终状态。每个边缘都用概率加权。

如果没有循环的情况下，我可以简单地对每种结果的概率进行求和、乘法并重新归一化，如果我从同一个顶点（单元格）开始。

然而，如果存在循环，则会变得混乱。例如，假设每个边缘的概率相同：

  start0
   /\   ^
  /  \  |
end1  tr2
      /
     end2

图表从 start0 开始，有50%的概率停止在 end1 或转到 tr2。从 tr2 开始，又有50%的概率停止在 end2 或返回 start0。

我如何计算到达每个终点 end1 和 end2 的总概率？如果我尝试使用像这样的收敛级数： pEnd1=1/2 + 1/2*1/2+1/8+.. ->lim->1。这没有任何意义，因为end2得不到任何概率。很明显我那里有错误。

所以我的问题是，如果我有每个边缘的概率但可以有环路，我该如何计算到达最终节点的概率。

示例1）简单的叉路和一个循环，所有边缘都有50%的可能性。

start0-> p=50% ->end1
start0-> p=50% ->tr1
tr2-> p=50% ->start0
tr2-> p=50% ->end2

示例 2）更多的循环

start0-> p=1/3 ->e1
start0-> p=1/3 ->tr1
start0-> p=1/3 ->start0
tr1-> p=1/3 ->tr2
tr1-> p=2/3 ->start0
tr2-> p=7/9 ->start0
tr2-> p=2/9 ->end2

示例3) - 退化测试用例 - 由于所有路径都以 e1 结束 - 因此它最终应该具有100%的概率。

start0-> p=1/3 ->e1
start0-> p=2/3 ->tr1
tr1-> p=3/4 ->start0
tr2-> p=1/4 ->e1

- Dr Phil

Answer 1

这不是一个编程问题，尽管你可以编写一个模拟程序并运行10万次以查看分布会是什么样子。

你写道：

pEnd1=1/2 + 1/2*1/2+1/8+.. ->lim->1。这没有意义，因为end2没有得到任何概率。显然，我在那里犯了一个错误。

确实存在误差。您没有考虑从tr2到start0的概率（50%）。路径循环一次到start0，然后最终到达end1的概率是1/2（去tr2）*1/2（回start0）*1/2（去end1）。当在end1结束时，50％的决策数始终为奇数，而在end2结束时则为偶数。因此公式应为：

pEnd1 = 2^-1 + 2^-3 + 2^-5 + ... -> lim = 2/3

pEnd2 = 2^-2 + 2^-4 + 2^-6 + ... -> lim = 1/3

模拟

为了将其变成一个编程问题，以下是JavaScript中的模拟程序：

function run(transitions, state) {
    while (transitions[state][state] != 1) { // not in sink
        let probs = transitions[state];
        let rnd = Math.random(); // in range [0, 1)
        for (let i = 0; i < probs.length; i++) {
            rnd -= probs[i];
            if (rnd < 0) {
                state = i; // transition
                break;
            }
        }
    }
    return state;
}

// Define graph
let names = ["start0", "end1", "tr2", "end2"]
let transitions = [
    [0.0, 0.5, 0.5, 0.0],
    [0.0, 1.0, 0.0, 0.0], // sink
    [0.5, 0.0, 0.0, 0.5],
    [0.0, 0.0, 0.0, 1.0]  // sink
];

// Start sampling
let numResults = [0, 0, 0, 0];
let numSamples = 0;
setInterval(function () {
    let endstate = run(transitions, 0);
    numSamples++;
    numResults[endstate]++;
    document.querySelector("#" + names[endstate]).textContent = (100 * numResults[endstate] / numSamples).toFixed(4) + "%";
}, 1);

<div>Arriving in end1: <span id="end1"></span></div>
<div>Arriving in end2: <span id="end2"></span></div>

您可能还想阅读有关吸收马尔可夫链的内容。从中我们学到，"吸收概率"矩阵 B 可以用以下公式计算：

B = NR

其中：

• N 是 "基本矩阵" (I - Q)⁻¹     
• I 是与 Q 相同形状的单位矩阵
• Q 是非最终状态之间转移的概率矩阵
• R 是转移到最终状态的概率矩阵

以下是一个包括相关矩阵函数的脚本，用于计算您所描述示例问题的 B 矩阵：

// Probabilities to go from one non-final state to another
let Q = [
    [0.0, 0.5], // from start0 to [start0, tr2]
    [0.5, 0.0]  // from tr2    to [tr2, start0]
];
// Probabilities to go from one non-final state to a final one
let R = [
    [0.5, 0.0], // from start0 to [end1, end2]
    [0.0, 0.5]  // from tr2    to [end1, end2]
];
// See https://en.wikipedia.org/wiki/Absorbing_Markov_chain#Absorbing_probabilities
let N = inversed(sum(identity(Q.length), scalarProduct(Q, -1)));
let B = product(N, R);
console.log("B = (I-Q)⁻¹R:\n" + str(B));

// Generic matrix utility functions:
// cofactor is copy of given matrix without given column and given row 
function cofactor(a, y, x) {
    return a.slice(0, y).concat(a.slice(y+1)).map(row => row.slice(0, x).concat(row.slice(x+1)));
} 

function determinant(a) {
    return a.length == 1 ? a[0][0] : a.reduceRight((sum, row, y) =>
        a[y][0] * determinant(cofactor(a, y, 0)) - sum
    , 0);
} 

function adjoint(a) {
    return a.length == 1 ? [[1]] : transposed(a.map((row, y) => 
        row.map((_, x) => ((x + y) % 2 ? -1 : 1) * determinant(cofactor(a, y, x)))
    ));
} 

function transposed(a) {
    return a[0].map((_, x) => a.map((_, y) => a[y][x]));
}

function scalarProduct(a, coeff) {
    return a.map((row, y) => row.map((val, x) => val * coeff));
}

function inversed(a) {
    return scalarProduct(adjoint(a), 1 / determinant(a));
}

function product(a, b) {
    return a.map((rowa) =>
        b[0].map((_, x) =>
            b.reduce((sum, rowb, z) =>
                sum + rowa[z] * rowb[x]
            , 0)
        )
    );
}

function sum(a, b) {
    return a.map((row, y) => row.map((val, x) => val + b[y][x]));
}

function identity(length) {
    return Array.from({length}, (_, y) => 
        Array.from({length}, (_, x) => +(y == x))
    );
}

function str(a) {
    return a.map(row => JSON.stringify(row)).join("\n");
}

输出结果为：

[
    [2/3, 1/3] // probabilities when starting in start0 and ending in [end1, end2]
    [1/3, 2/3] // probabilities when starting in tr2 and ending in [end1, end2]
]

- trincot

---

您所给出的答案非常令人印象深刻，即使提供了一些代码片段（我只是询问算法），这需要我花费一些时间来理解。 - Dr Phil

Answer 2

你在描述一种离散时间、离散状态空间的吸收马尔可夫链。

在你的例子中，end1和end2是吸收状态。

参考维基百科文章介绍了如何计算吸收概率（或者称为固定概率）。

还可以参考这里和这里。

- Lior Kogan