加权圆图的总路径概率

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 次以查看分布情况。

您写道：

pEnd1=1/2 + 1/2*1/2+1/8+.. ->lim->1. which makes no sense since end2 is getting no probability. Obviously I have a mistake there.

确实有误。您没有考虑从 tr2 到 start0 的概率 (50%)。路径将循环一次到 start0 然后在 end1 结束的概率是 1/2（去 tr2）* 1/2（回到 start0）* 1/2（去 end1）。在 end1 结束时，决定的数量（50%）总是 odd。而在end2结束时是even。所以公式是：

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>

您可能还想阅读有关 Absorbing Markov chains 的内容。从中我们了解到“吸收概率”矩阵 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]
]

Answer 2

您描述的是离散时间离散状态-space Absorbing Markov Chain。

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

引用的维基百科文章描述了如何计算吸收概率（或吸收概率）。

另见 here and here。

加权圆图的总路径概率

total path probability of weighted circular graph

algorithm

graph

probability

fractions

fractals

模拟