Search code examples
pythonmathprobabilitycombinatorics

Probability of moving on a cartesian plane

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
Solution

  • 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.