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

huangapple go评论65阅读模式
英文:

Probability of moving on a cartesian plane

问题

我正在处理以下编程问题,看起来更像是一个概率问题而不是一个编程问题。

平台由5个顶点组成。这些顶点的坐标分别是:(-1,0), (0,-1), (0,0), (0,1), (1,0)。
你从顶点(xs,ys)开始,并随机向左(即x坐标减1)、向右(即x坐标加1)、向上或向下移动。后续移动的方向是独立的。
在掉出平台之前,你到达顶点(xe,ye)的概率是多少?
约束条件:
(xs, ys)在[(-1,0), (0,-1), (0,0), (0,1), (1,0)]范围内
(xe, ye)在[(-1,0), (0,-1), (0,0), (0,1), (1,0)]范围内
xs != xe 或 ys != ye

以下是我实现的代码,对于我分享的案例有效,但对于所有其他情况都失败了

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
英文:

I am working on the below coding problem which looks more like a probability question rather than a coding problem

platform consisting of 5 vertices. The coordinates of the vertices are: (-1,0), (0.-1). (0,0), (0.1). (1.0).
You start at vertex (xs,ys)
and keep moving randomly either left (i.e., x coordinate decreases by 1), right (i.e., x coordinate increases by 1), up, or
down. The direction of subsequent moves is independent.
What is the probability that you reach vertex (xe, ye)
before falling off the platform?
Constraints:
(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 or ys != yend

below is what I implemented which works for the case I shared but fails for all other cases

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

答案1

得分: 7

If we handle the edge cases where you start at your destination, or you start at an edge and the destination is the center, we're left with a simple scenario: find your way to the center, and then to the destination. Getting to the origin is a flat 0.25 probability, and then it's just a matter of getting to the right edge. If you randomly walk in the wrong direction, you can always backtrack with 0.25 probability of success. This can repeat any number of times before walking in the correct direction (to the destination).

This means from the origin, we have a 1/4 chance of picking the right direction, and a 3/4 chance of picking the wrong direction. If we pick the right direction, we're done, if we pick the wrong direction, we have to pick the opposite direction to get back to the origin and avoid falling off, which is a 1/4 chance. Combining these into one, we have a 1/4 of being right the first time, and 3/16 chance at a second chance. Continuing this repeatedly, we end up with a formula like:

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

So from the origin, we have a 4/13 chance of walking to the correct edge tile without falling off.

In code:

def solve(xs, ys, xe, ye):
    # already at destination
    if xs == xe and ys == ye:
        return 1

    # if destination is the origin, the probability is a flat 0.25
    if xe == 0 and ye == 0:
        return 0.25

    # first move must take you to the origin if not already there
    prob = 0.25 if xs != 0 or ys != 0 else 1

    # multiply by probability of walking from origin to destination
    return prob * 4 / 13

Update: I have an alternative and possibly simpler way of approaching the math in the section above.

Take P to represent the probability of successfully walking from the origin to the destination without falling off. Ignore the edge case where the origin is the destination- that's already handled above. We now have two cases to handle:

  • The first move takes is to the destination. This has a 1/4 chance of happening.
  • The first move takes us in one of the other 3 directions (3/4 chance). We then have to return to the origin, with a 1/4 chance of not falling off. We then repeat the process recursively, with a P chance of success (by definition of P). This gives 3/16 * P chance for this scenario.

This means we have algebraically:

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

We arrive at the same probability of 4/13 as before.

英文:

If we handle the edge cases where you start at your destination, or you start at an edge and the destination is the center, we're left with a simple scenario: find you way to the center, and then to the destination. Getting to the origin is a flat 0.25 probability, and then its just a matter of getting to the right edge. If you randomly walk in the wrong direction, you can always backtrack with 0.25 probability of success. This can repeat any number of times before walking in the correct direction (to the destination).

This means from the origin, we have a 1/4 chance of picking the right direction, and a 3/4 chance of picking the wrong direction. If we pick the right direction, we're done, if we pick the wrong direction, we have to pick the opposite direction to get back to the origin and avoid falling off, which is a 1/4 chance. Combining these into one, we have a 1/4 of being right the first time, and 3/16 chance at a second chance. Continuing this repeatedly, we end up with a formula like:

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

So from the origin, we have a 4/13 chance of walking to the correct edge tile without falling off.

In code:

def solve(xs, ys, xe, ye):
    # already at destination
    if xs == xe and ys == ye:
        return 1

    # if destination is the origin, the probability is a flat 0.25
    if xe == 0 and ye == 0:
        return 0.25

    # first move must take you to the origin if not already there
    prob = 0.25 if xs != 0 or ys != 0 else 1

    # multiply by probability of walking from origin to destination
    return prob * 4 / 13

Update: I have an alternative and possibly simpler way of approaching the math in the section above.

Take P to represent the probability of successfully walking from the origin to the destination without falling off. Ignore the edge case where the origin is the destination- that's already handled above. We know have two cases to handle:

  • The first move takes is to the destination. This has a 1/4 chance of happening.
  • The first move takes us in one of the other 3 directions (3/4 chance). We then have to return to the origin, with a 1/4 chance of not falling off. We then repeat the process recursively, with a P chance of success (by definition of P). This gives 3/16 * P chance for this scenario.

This means we have algebraically:

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

We arrive at the same probability of 4/13 as before.

huangapple
  • 本文由 发表于 2023年5月15日 02:53:02
  • 转载请务必保留本文链接:https://go.coder-hub.com/76249186.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定