I was asked a programming question in an interview as following:
There is an island which is represented by square matrix MxM. A person on the island is standing at any given co-ordinates (A,B). He can move in any direction one step right, left, up, down on the island. If he steps outside the island, he dies.
Consider that step in each direction is equally likely, what is the probability that he is dead after he walks N steps on the island?(He falls of the grid.)
My approach to solve this problem is as following:-
Consider this polynomial
$Q(x,y) = \frac 1x + \frac 1y + x + y$
And initial position of the person as $P(x,y) = x^A + y^B$ (Where (A,B) is co-ordinates of initial position.
To calculate total number of ways of surviving, I used following algorithm:
$T(x,y) = x^A + y^B$
Repeat N times:
{
$T(x,y) = T(x,y)Q(x,y)$
discard all the terms from $T(x,y)$ except $C_ix^ay^b$ such that $1\leq a,b \leq M$
}
Sum of all the coefficient in T(x,y) is total number of surviving. So, required probability will be
$\frac {\sum coefficient of T(x,y)}{4^N} $
This solution is very programmatic in nature, how can I get a pure mathematical approach to solve this?
The following is just a mathematical formulation, which the computational complexity could be even higher than the algorithm you proposed.
The direction selection in each step is a multinomial trial, therefore the total number of steps in each direction $(R, L, U, D)$ jointly follows $$\text{Multinomial}\left(n; \frac {1} {4}, \frac {1} {4}, \frac {1} {4}, \frac {1} {4}\right)$$
The event he die is the union of the four events of stepping out in each direction: $$U - D > m - b, D - U \geq b, R - L > m - a, L - R > a$$ One can use inclusion-exclusion to simplify the stuff, and of course by pairing up the $U-D$ and $L-R$ direction can also help.