Probability of death of a man moving n steps in a matrix

Question

There is an island which is represented by square matrix nxn.

A person on the island is standing at any given co-ordinates (x,y). He can move in any direction one step right, left, up, down on the island. If he steps outside the island, he dies.

Let the island be represented as (0,0) to (n-1,n-1) (i.e nxn matrix) & person is standing at given co-ordinates (x,y). He is allowed to move n steps on the island (along the matrix). What is the probability that he is dead after he walks n steps on the island?

What should be the approach to find the probability using programming techniques?

I have a mathematical method, but I don't know whether it's correct or not. Here it is:

The total number of outcomes are n^n. To calculate the number of outcomes which can lead to death of the person:

For each of the four directions, check how many steps can lead to him going out of the matrix. Then, apply the high school probability formula. For e.g. suppose the total number of steps he can take are 5; (x, y) = (2,1) [indexing is 0-based]. So, he needs to take 3 steps in north dir. to fall out of island. Keeping them in a group: (NNN) and making other 2 steps as any of the 4 choices, we have the formula: 4*4*3. Similarly, for other 3 directions. Finally, the probality = (sum of the calculated death outcomes) / (total outcomes)

This was a Google interview question.

Answer 1

TL;DR: Recursion. (Or "mathematical induction", if you're snobbish.)

(In what follows, "he is dead after he walks n steps on the island" is assumed to mean "he dies after less than or equal to n steps". If you take it to mean "he dies after exactly n steps", the answer will be slightly different. I'll discuss it briefly at the end.)

We have an NxN matrix where the value in each cell represents the probability of dying in n steps if we started from that cell.

Consider the probability of dying in 0 steps. Clearly, this is 0.0 for every location inside the island, and 1.0 everywhere outside it.

What's the probability of dying in 1 steps? You have four directions you can move in, with equal probability. So for each cell, you take its four neighbors, find their probability of dying in 0 steps, and average them together. (If a neighbor is outside the matrix, you consider its probability to be 1.0.)

Similarly, the probability of dying in k steps starting from a given cell is the average of the probability of dying in k-1 steps starting from its neighbour cells.

Python code:

from itertools import product as prod 

def prob_death(island_size, steps):
    if island_size < 1 or steps < 0: raise ValueError
    new_prob = [[0. for i in range(island_size)] for j in range(island_size)]
    if steps == 0:
        return new_prob
    old_prob = prob_death(island_size, steps - 1)
    directions = [(0, -1), (1, 0), (0, 1), (-1, 0)]
    for (i, j, direction) in prod(range(island_size), range(island_size), directions):
        neighbor_i = i + direction[0]
        neighbor_j = j + direction[1]
        if neighbor_i >= 0 and neighbor_i < island_size and \
                neighbor_j >= 0 and neighbor_j < island_size:
            prob_death_this_way = old_prob[neighbor_i][neighbor_j]
        else: # neighbor is outside the island 
            prob_death_this_way = 1.
        new_prob[i][j] += 0.25* prob_death_this_way
    return new_prob

Now, let's test it out a bit: (mpr is just a function for printing matrices nicely)

>>> mpr(prob_death(5, 0))
0.000000 0.000000 0.000000 0.000000 0.000000
0.000000 0.000000 0.000000 0.000000 0.000000
0.000000 0.000000 0.000000 0.000000 0.000000
0.000000 0.000000 0.000000 0.000000 0.000000
0.000000 0.000000 0.000000 0.000000 0.000000

As expected: You can't die in 0 steps if you start inside the island.

>>> mpr(prob_death(5,1))
0.500000 0.250000 0.250000 0.250000 0.500000
0.250000 0.000000 0.000000 0.000000 0.250000
0.250000 0.000000 0.000000 0.000000 0.250000
0.250000 0.000000 0.000000 0.000000 0.250000
0.500000 0.250000 0.250000 0.250000 0.500000

This is what we'd expect. If you start at a corner cell, you have 0.5 probability of dying in 1 step: 2 out of your 4 neighbors are outside the island. If you start on an edge, only 1 neighbor is outside, so your probability of dying is 0.25. Everywhere else, all neighbors are inside the island, so probability of dying in 1 step is 0.0.

>>> mpr(prob_death(5, 5))
0.806641 0.666016 0.622070 0.666016 0.806641
0.666016 0.437500 0.349609 0.437500 0.666016
0.622070 0.349609 0.261719 0.349609 0.622070
0.666016 0.437500 0.349609 0.437500 0.666016
0.806641 0.666016 0.622070 0.666016 0.806641

The probability of dying in 5 steps. I can't verify the exact values, but it looks about right: The probability of dying is highest in the corners, a little lower at the edges, and decreases steadily inwards.

That solves the problem of dying in less than or equal to n steps.

Now, to find the probability of dying in exactly n steps: Let the probability of dying in less than or equal to n steps starting from (x,y) be denoted by P(x,y,n). Then the probability of dying in exactly n steps is the probability of surviving for n-1 steps, times the probability of dying in the nth step given that we survived for n-1 steps: (1-P(x,y,n-1))*(P(x,y,n) - P(x,y,n-1)). (I'm not all that sure about this formula; correct me if I'm wrong.)

Answer 2

First, start with a matrix with the probability of being in the square (x, y) in the 0th step. Let's simulate it with a 4x4 matrix. Assuming the guy starts at (1, 2):

After 0 steps:
  0.00%   0.00%   0.00%   0.00%
  0.00%   0.00% 100.00%   0.00%
  0.00%   0.00%   0.00%   0.00%
  0.00%   0.00%   0.00%   0.00%
outside:   0.00%
----
After 1 steps:
  0.00%   0.00%  25.00%   0.00%
  0.00%  25.00%   0.00%  25.00%
  0.00%   0.00%  25.00%   0.00%
  0.00%   0.00%   0.00%   0.00%
outside:   0.00%
----
After 2 steps:
  0.00%  12.50%   0.00%  12.50%
  6.25%   0.00%  25.00%   0.00%
  0.00%  12.50%   0.00%  12.50%
  0.00%   0.00%   6.25%   0.00%
outside:  12.50%
----
After 3 steps:
  4.69%   0.00%  12.50%   0.00%
  0.00%  14.06%   0.00%  12.50%
  4.69%   0.00%  14.06%   0.00%
  0.00%   4.69%   0.00%   4.69%
outside:  28.12%
----
After 4 steps:
  0.00%   7.81%   0.00%   6.25%
  5.86%   0.00%  13.28%   0.00%
  0.00%   9.38%   0.00%   7.81%
  2.34%   0.00%   5.86%   0.00%
outside:  41.41%
----

Here's a python program that calculates this:

class Table:
    def __init__(self, n, outside=0):
        self.T = [[0]*n for i in xrange(n)]
        self.outside = outside

    def add(self, i, j, value):
        n = len(self.T)
        if 0<=i<n and 0<=j<n:
            self.T[i][j] += value
        else:
            self.outside += value

    def make_next(self):
        n = len(self.T)
        Q = Table(n, self.outside)

        for i in xrange(n):
            for j in xrange(n):
                value = self.T[i][j] / 4.0
                Q.add(i-1, j, value)
                Q.add(i+1, j, value)
                Q.add(i, j-1, value)
                Q.add(i, j+1, value)
        return Q

    def __repr__(self):
        return '\n'.join(' '.join(
                    '{:6.2f}%'.format(item*100) 
                    for item in line)
                    for line in self.T) + \
               '\noutside: {}'.format('{:6.2f}%'.format(self.outside*100))


N = 4
T = Table(N)
T.add(1, 2, 1)

for k in xrange(N+1):
    print 'After {} steps:'.format(k)
    print T
    print '----'

    T = T.make_next()