Compute Random Walk Hitting and Return Probabilities
Company: Cfm
Role: Data Scientist
Category: Machine Learning
Difficulty: hard
Interview Round: Technical Screen
Consider simple symmetric random walks on integer lattices.
1. In one dimension, a particle starts at integer position `x` with absorbing boundaries at integers `a` and `b`, where `a < x < b`. At each step it moves to the left or right by 1 with probability `1/2` each. What is the expected number of steps until it first hits either boundary `a` or boundary `b`?
2. In two dimensions, a particle starts at the origin `(0, 0)` on the integer lattice. At each step it moves one unit up, down, left, or right, each with probability `1/4`. What is the probability that it eventually returns to the origin?
3. Extend the previous question to three dimensions: the particle starts at `(0, 0, 0)` and at each step moves to one of its six neighboring lattice points with probability `1/6` each. What is the probability that it eventually returns to the origin?
Quick Answer: This question evaluates understanding of probability theory and stochastic processes, specifically simple symmetric random walks, expected hitting times with absorbing boundaries, and recurrence versus transience (return probabilities) on integer lattices.