Position likelihood in a 2D graph I am looking for general principles or specific answers to this generic example. 
Assume a 2d grid with no boundaries and a roving dot (ant/drunk guy/particle) that is initially located at some starting position S. There's an equal probability of going up (u), down (d), left (l) or right (r) from any position on the grid. A block is defined by analogy to a city block, and 2 adjacent points as well as 2 points that are linked by a u+r path (for example) are both said to be distant by 1 block. 
How would I approach computing the likelihood that my roving dot is at least n blocks away from startig point x after i moves? For example, what is the mathematical approach to determining the likelihood that the roving dot is 4 or more blocks away from S after 10 moves?
 A: You can use a Markov chain on the positions. In ten moves you can't get too far, so you can use a finite grid. In your specific example, the probability of ending up at least 4 blocks away is about 0.21846 if this code is correct.

import numpy as np
k = 10
d = 4
P = np.zeros((k, k, k, k))
for i in range(k):
    # boundaries
    P[i, 0, i, 1] += 0.5
    P[0, i, 1, i] += 0.5
    P[i, -1, i, -2] += 0.5
    P[-1, i, -2, i] += 0.5
    # interior
    for j in range(1, k-1):
        P[i, j, i, j-1] += 0.25
        P[i, j, i, j+1] += 0.25
        P[j, i, j-1, i] += 0.25
        P[j, i, j+1, i] += 0.25
# initial state
v = np.zeros((k, k))
v[0, 0] = 1
# final state
R = np.linalg.matrix_power(P.reshape(k*k, k*k), k)
r = v.reshape(k*k).dot(R).reshape((k, k))
# probability
print 1 - r[:d, :d].sum()

A: The block distance is the maximum of the horizontal and vertical distances from the starting point. If you condition on the numbers of horizontal and vertical steps, then the two distances are conditionally independent and the relevant distance probabilities  are binomial tail probabilities. Thus you end up a binomial mixture of products of binomial tail probabilities. 
