Particle in square lattice
Problem statement:
A square is drawn in a Cartesian coordinate plane with vertices at (2,2) , (-2,2) , (-2,-2) and (2,-2). A particle starts at (0,0). Every second it moves with equal probability to one of the lattice points (points with integer coordinate) closest to its current location, independently to its previous moves. The particle will eventually hit the square for the first time either on the one of the four corners of the square or at one lattice point on the interior of the sides of square. The probability that it will hit the corner rather than the interior part of the side is m/n, where m and n are relatively prime integers. What is m+n?
Solution:
This problem is very interesting because it involves nesting probability, I will make this simple for you, the above problem boils down to that what is the probability that a particle moving around randomly between those points will hit the corners, hitting the corners means winning while hitting the outer edge point is losing.
Note: The particle can only move around one out eight nearest points at a time.
Let us consider the probability of winning at center point p0 be P0 and at the point p1 immediately above p0 be P1 and by symmetry we will get four such points including this one having the probability of winning as P1 namely left, right, up and down.
Also we have another set of points let's call them as p2 and the probability of winning from these points be P2, these points are located on the immediate diagonals of the centre point.
The probability of winning from the points marked as blue is zero. Also the probability of winning at the corners is obviously one.
Now we are ready to formulate some equations:
Point p0:
From point p0 we have 8 options so the probability of winning from p0 will be the sum of probabilities of winning from those eight points and there is 1/2 chance of selecting a yellow(p1) point and 1/2 chance of selecting an orange(p2) point, hence the equation becomes:
P0 = (1/2) * P1 + (1/2) * P2 --------- eq(1)
Points p1:
Here also we got 8 choices out of which three blue points contribute 0 probability to winning, we have 2/8 chance of selecting an orange point and 2/8 chance of selecting a yellow point and a 1/8 chance of selecting the midpoint (red), hence the equation becomes:
P1 = (1/4) * P2 + (1/4) * P1 + (1/8) * P0 ------ eq(2)
Points p2:
In this case we have 1/8 chance of winning (green point) and 2/8 chance of hitting the yellow point and a 1/8 chance of hitting the middle point (red).
P2 = 1/8 + (1/4) * P1 + (1/8) * P0 ------ eq(3)
We have three equations 1,2 and 3 and three variables P0, P1 and P2 which can be solved easily.
The value of P0 turns out to be 4/35 hence the value of m + n (numerator + denominator) is 39.
Thanks for reading guys, hope you liked the post, this problem was asked in ACM 2017.