在笛卡尔平面上移动的概率

Question

我正在研究下面的编码问题，它看起来更像是概率问题而不是编码问题

由 5 个顶点组成的平台。顶点的坐标为：(-1,0)、(0.-1)。(0,0), (0.1)。(1.0)。从顶点 (xs,ys) 开始，并继续向左（即 x 坐标减少 1）、向右（即 x 坐标增加 1）、向上或向下随机移动。随后的移动方向是独立的。在从平台上掉下来之前到达顶点 (xe, ye) 的概率是多少？约束：(xs, ys) in [(-1.0), (0.-1), (0.0), (0.1), (1,0)] (xe, ye) in [(-1,0), ( 0.-1), (0,0), (0,1), (1.0)] xs != xend 或 ys != Yend

下面是我实现的方法，它适用于我分享的案例，但不适用于所有其他情况

def calculate_probability(xs, ys, xe, ye):
    edges = [[-1, 0], [0, -1], [0, 1], [1, 0]]
    if [xs, ys] in edges:
        if xe == 0 and ye == 0:
            return 0.25
        elif xs == xe and ys == ye:
            return 1.0
        elif [xe, ye] in edges:
            return 0.075
    
    if xs == 0 and ys == 0:
        if [xe, ye] in edges:
            return 0.3
        elif xe == 0 and ye == 0:
            return 1
    return 0

Answer 1

如果我们处理从目的地开始的边缘情况，或者从边缘开始而目的地是中心的情况，那么我们会遇到一个简单的场景：找到通往中心的路，然后到达目的地。到达原点的0.25概率是平坦的，然后只需到达正确的边缘即可。如果你随机走错了方向，你总能以0.25成功的概率原路返回。在朝正确方向（到达目的地）行走之前，可以重复任意次数。

这意味着从原点开始，我们有 1/4 的机会选择正确的方向，有 3/4 的机会选择错误的方向。如果我们选择了正确的方向，我们就完成了，如果我们选择了错误的方向，我们就必须选择相反的方向才能回到原点并避免掉落，这是1/4的机会。将这些结合起来，我们第一次有 1/4 的机会是正确的，而第二次机会有 3/16 的机会。不断重复这个过程，我们最终得到如下公式：

1/4 + 1/4 * (3/16) + 1/4 * (3/16)^2 + 1/4 * (3/16)^3 + ...
= 1/4 * (1 + (3/16) + (3/16)^2 + (3/16)^3 + ...)
= 1/4 * (16/13)
= 4/13

所以从原点开始，我们就有4/13机会走到正确的边缘瓷砖而不掉落。

在代码中：

1/4 + 1/4 * (3/16) + 1/4 * (3/16)^2 + 1/4 * (3/16)^3 + ...
= 1/4 * (1 + (3/16) + (3/16)^2 + (3/16)^3 + ...)
= 1/4 * (16/13)
= 4/13

更新：我有一种替代且可能更简单的方法来处理上面部分中的数学。

取P代表从起点成功走到目的地而不摔倒的概率。忽略起点是目的地的边缘情况——上面已经处理过。我们知道有两种情况需要处理：

• 第一步是到达目的地。这种情况发生的概率是 1/4。
• 第一步将我们带到其他 3 个方向之一（3/4 机会）。然后我们必须回到原点，有 1/4 的机会不掉落。然后，我们递归地重复该过程，并有P成功的机会（根据 的定义P）。这3/16 * P为这种情况提供了机会。

这意味着我们有代数：

P = 1/4 + 3/16 * P
13/16 * P = 1/4
P = 4/13

我们得到4/13与之前相同的概率。