带权圆图的总路径概率

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

Answer 1

这实际上并不是一个编程问题，尽管您可以编写一个模拟并执行 100000 次来查看分布情况。

\n

你写了：

\n

\n

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

\n

\n

确实，有一个错误。您没有考虑从 tr2 到 start0 的概率 (50%)。路径循环一次到 start0 然后在 end1 结束的概率为 1/2（前往 tr2）* 1/2（返回 start0）* 1/2（前往 end1）。当以 end1 结束时，决策数量（50%）总是奇数。即使在end2结束时也是如此。所以公式是：

\n

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

\n

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

\n

模拟

\n

为了使这个问题成为一个编程问题，下面是用 JavaScript 进行的模拟：

\n

\r\n

\r\n

function run(transitions, state) {\n    while (transitions[state][state] != 1) { // not in sink\n        let probs = transitions[state];\n        let rnd = Math.random(); // in range [0, 1)\n        for (let i = 0; i < probs.length; i++) {\n            rnd -= probs[i];\n            if (rnd < 0) {\n                state = i; // transition\n                break;\n            }\n        }\n    }\n    return state;\n}\n\n// Define graph\nlet names = ["start0", "end1", "tr2", "end2"]\nlet transitions = [\n    [0.0, 0.5, 0.5, 0.0],\n    [0.0, 1.0, 0.0, 0.0], // sink\n    [0.5, 0.0, 0.0, 0.5],\n    [0.0, 0.0, 0.0, 1.0]  // sink\n];\n\n// Start sampling\nlet numResults = [0, 0, 0, 0];\nlet numSamples = 0;\nsetInterval(function () {\n    let endstate = run(transitions, 0);\n    numSamples++;\n    numResults[endstate]++;\n    document.querySelector("#" + names[endstate]).textContent = (100 * numResults[endstate] / numSamples).toFixed(4) + "%";\n}, 1);

\r\n

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

\r\n

\r\n

\r\n

\n

您可能还想阅读有关吸收马尔可夫链的内容。由此我们得知“吸收概率”矩阵 B 可以用以下公式计算：

\n

B = NR

\n

在哪里：

\n

\n
• N 是“基本矩阵”(I - Q)\xe2\x81\xbb\xc2\xb9 \xc2\xa0\xc2\xa0\xc2\xa0\xc2\xa0
\n
• I 是与 Q 形状相同的单位矩阵
\n
• Q 是非最终状态之间转换的概率矩阵
\n
• R 是过渡到最终状态的概率矩阵
\n

\n

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

\n

\r\n

\r\n

// Probabilities to go from one non-final state to another\nlet Q = [\n    [0.0, 0.5], // from start0 to [start0, tr2]\n    [0.5, 0.0]  // from tr2    to [tr2, start0]\n];\n// Probabilities to go from one non-final state to a final one\nlet R = [\n    [0.5, 0.0], // from start0 to [end1, end2]\n    [0.0, 0.5]  // from tr2    to [end1, end2]\n];\n// See https://en.wikipedia.org/wiki/Absorbing_Markov_chain#Absorbing_probabilities\nlet N = inversed(sum(identity(Q.length), scalarProduct(Q, -1)));\nlet B = product(N, R);\nconsole.log("B = (I-Q)\xe2\x81\xbb\xc2\xb9R:\\n" + str(B));\n\n// Generic matrix utility functions:\n// cofactor is copy of given matrix without given column and given row \nfunction cofactor(a, y, x) {\n    return a.slice(0, y).concat(a.slice(y+1)).map(row => row.slice(0, x).concat(row.slice(x+1)));\n} \n\nfunction determinant(a) {\n    return a.length == 1 ? a[0][0] : a.reduceRight((sum, row, y) =>\n        a[y][0] * determinant(cofactor(a, y, 0)) - sum\n    , 0);\n} \n\nfunction adjoint(a) {\n    return a.length == 1 ? [[1]] : transposed(a.map((row, y) => \n        row.map((_, x) => ((x + y) % 2 ? -1 : 1) * determinant(cofactor(a, y, x)))\n    ));\n} \n\nfunction transposed(a) {\n    return a[0].map((_, x) => a.map((_, y) => a[y][x]));\n}\n\nfunction scalarProduct(a, coeff) {\n    return a.map((row, y) => row.map((val, x) => val * coeff));\n}\n\nfunction inversed(a) {\n    return scalarProduct(adjoint(a), 1 / determinant(a));\n}\n\nfunction product(a, b) {\n    return a.map((rowa) =>\n        b[0].map((_, x) =>\n            b.reduce((sum, rowb, z) =>\n                sum + rowa[z] * rowb[x]\n            , 0)\n        )\n    );\n}\n\nfunction sum(a, b) {\n    return a.map((row, y) => row.map((val, x) => val + b[y][x]));\n}\n\nfunction identity(length) {\n    return Array.from({length}, (_, y) => \n        Array.from({length}, (_, x) => +(y == x))\n    );\n}\n\nfunction str(a) {\n    return a.map(row => JSON.stringify(row)).join("\\n");\n}

\r\n

\r\n

\r\n

\n

输出是：

\n

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

\n