加权圆图的总路径概率

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。这是没有道理的，因为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>

您可能还想读一下Markov chains