加权圆形图的总路径概率

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

您正在描述离散时间离散状态空间Absorbing Markov Chain。

在您的示例中，end 1和end2是吸收状态。

[参考的Wikipedia文章描述了如何计算吸收概率（或吸收概率）。

另请参见here和here。

Answer 2

这不是真正的编程问题，尽管您可以编写一个模拟并执行100000次以查看分布是什么。

您写道：

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％）始终为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）⁻¹R
• 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]
]