Grid random walk

Grid random walk#

Question#

Two people start at opposite corners of a 4x4 grid. Person A starts on the bottom-left node. Person B starts on the top-right node.

Every second, Person A will randomly move either one edge to the right or one edge up. At the same time, Person B will randomly move either one edge to the left or one edge down. Each person must always move each second, and for example, if Person A cannot move right anymore, they must move up.

What is the probability that A and B will never share the same position at some point?

Ans#

First consider 2 by 2 grid, and consider three possible meeting points: (1,1), (0,2) and (2,0)

A going from (0,0) to (2,2) have 6 possible routes, 4 of which go through (1,1), so intuitively one thinks A goes through (1,1) 2/3 of the time.

In fact, A goes through (1,1) only half of the times, and reaches (0,2) or (2,0) each with 1/4 of times.

So P(A & B meet at 1,1) = 1/2^2 = 1/4
P(A & B meet at 2,0) = 1/4^2 = 1/16
P(A & B meet) = 1/4 + 1/16 + 1/16 = 3/8

import random

GRID_SIZE = 2

# Possible moves for Person A and Person B
MOVES_A = [[1, 0], [0, 1]]  # Right or Up
MOVES_B = [[-1, 0], [0, -1]]  # Left or Down

def simulate_meeting(GRID_SIZE):
    pos_a = [0, 0]
    pos_b = [GRID_SIZE, GRID_SIZE]

    while pos_a != [GRID_SIZE, GRID_SIZE] or pos_b != [0, 0]:
        if pos_a[0] == GRID_SIZE: # can only move up now
            pos_a[1] += 1
        elif pos_a[1] == GRID_SIZE: # can only move right now
            pos_a[0] += 1
        else:
            move_a = random.choice(MOVES_A)
            pos_a = [pos_a[0] + move_a[0], pos_a[1] + move_a[1]]

        if pos_b[0] == 0: # can only move down now
            pos_b[1] -= 1
        elif pos_b[1] == 0: # can only move left now
            pos_b[0] -= 1
        else:
            move_b = random.choice(MOVES_B)
            pos_b = [pos_b[0] + move_b[0], pos_b[1] + move_b[1]]

        if pos_a == pos_b:
            return False  # They met at some point
        
    return True  # They never met

def estimate_probability(simulations=100000, grid_size=GRID_SIZE):
    no_meeting_count = 0
    for _ in range(simulations):
        if simulate_meeting(grid_size):
            no_meeting_count += 1
    return no_meeting_count / simulations

estimate_probability()

0.625

0.62539

4 by 4 case#

A reaches (2,2) with 3/8 chance, reaches (1,3) or (3,1) with 1/4 chance, reaches (0,4) or (4,0) with 1/16 chance

P(A & B meet) = 3/8^2 + 1/4^2 * 2 + 1/16^2 * 2 = 35/128

print(1 - 35/128)
estimate_probability(grid_size=4)

0.7265625
4

0.72833

10 by 10 grid (11 by 11 lattice), start at center, equally likely to go up down left right, expected time to reach boundary?#

29

Idea: approximate the square grid with a circle. For a simple random walk starting at the center of a circle of radius \(R\), the expected exit time is \(R^2\).

Lower bound: circle with radius 5
\(E_{lower} = 5^2 = 25\) It is lower bound because the square has corners that stick out further than this circle.

Upper bound: \(\pi R_{eq}^2 = 100 \implies R_{eq} = \sqrt{\frac{100}{\pi}} \approx 5.64\)
\(E_{upper} \approx (5.64)^2 \approx 31.83\)

The true value for the square lies between these bounds: \(25 < E_{square} < 31.83\).

import random
import numpy as np

def run_once():
    x, y = 0, 0
    t = 0
    while abs(x) < 5 and abs(y) < 5:
        r = random.randint(0, 3)
        if r == 0:
            x += 1
        elif r == 1:
            x -= 1
        elif r == 2:
            y += 1
        else:
            y -= 1
        t += 1
    return t

N = 200_000
times = [run_once() for _ in range(N)]

print("Mean:", np.mean(times))
print("Std:", np.std(times))

Mean: 29.288425
Std: 20.392722133628332
Contents