鼠标在状态 B 之前到达状态 A 的概率是多少

What is the probability that mouse with reach state A before state B

Maze

我有一个如上所示的迷宫(使用 link),状态 3 包含奖品,而状态 7 包含震惊。鼠标可以随机放置在1到9的任何状态,并且随机均匀地穿过迷宫

Pi 表示鼠标在状态 7 之前到达状态 3 的概率,假设 AIM 从隔间 i 开始。

如何计算 ∈ {1,2,3,4,5,6,7,8,9} 的 Pi。

从直觉上看,只要起点是随机的,落在任何一个方格上的概率似乎都是偶数。

+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+
| 7 | 8 | 9 |
+---+---+---+

如果鼠标从位置 3 或 7 开始,则游戏结束。

如果鼠标从位置 1 开始,它有 1/3 的机会在位置 2、5 或 4 结束,依此类推。

如果我们从包含 1/9 概率的每个单元格开始,我们可以通过将当前值乘以鼠标从另一个位置移入的概率来计算下一代的频率分布。例如,在第二代。单元格 1 将有 1/5 来自单元格 2 的小鼠 + 1/5 来自单元格 4 的小鼠和 1/8 来自单元格 5 的小鼠。因此,下一代单元格 1 是 (1/9)(1/ 5)+(1/9)(1/5)+(1/9)(1/8),或 21/360,或 0.0583。然后我们可以计算所有剩余单元格的概率。

这是格式非常糟糕的前五代 table

    1       2       3       4       5
1   0.111   0.058   0.059   0.046   0.039
2   0.111   0.095   0.078   0.065   0.054
3   0.111   0.169   0.228   0.274   0.312
4   0.111   0.095   0.078   0.065   0.054
5   0.111   0.163   0.115   0.101   0.082
6   0.111   0.095   0.078   0.065   0.054
7   0.111   0.169   0.228   0.274   0.312
8   0.111   0.095   0.078   0.065   0.054
9   0.111   0.058   0.059   0.046   0.039

Px 为游戏在位置 3 结束的概率,如果它在位置 x.

我们知道 P3=1P7=0

如果您从任何其他单元格开始,那么在您移动之后,您实际上是在新单元格中重新开始游戏。因此,其他 7 个单元格的概率可以根据它们可以移动到的邻居的概率来计算:

P5 = P2/4 + P4/4 + P6/4 + P8/4

P2 = P1/3 + P5/3 + P3/3

P1 = P2/2 + P4/2

...等等

对于每个单元格,您都有一个线性方程式 -- 9 个单元格有 9 个方程式。使用高斯消去法或类似技术求解方程组的 9 个概率。