The probability of death of a person moving n steps in a matrix

Question

There is an island that is represented by the square matrix nxn.

A man on the island stands at any coordinates (x, y). He can move in any direction one step to the right, left, up, down the island. If he goes outside the island, he dies.

Let the island be represented as (0,0) - (n-1, n-1) (i.e. the nxn-matrix), and the person stands at the given coordinates (x, y). He is allowed to move n steps to the island (along the matrix). What is the likelihood that he is dead after he takes n steps on the island?

What should be the approach to finding probability using programming methods?

I have a mathematical method, but I do not know if it is correct or not. Here he is:

The total number of outcomes is n ^ n. To calculate the number of results that can lead to a person’s death:

For each of the four directions, check how many steps can lead to its exit from the matrix. Then apply the high school probability formula. E.g. suppose the total number of steps he can take is 5; (x, y) = (2,1) [indexing based on 0]. So, he needs to take 3 steps in the northern dir. drop out of the island. Keeping them in the group: (NNN) and taking the other 2 steps as any of the 4 options, we have the formula: 4 * 4 * 3. Similarly, for the other three directions. Finally, probability = (sum of calculated death results) / (final results)

It was an interview question with Google.

Answer 1

TL; DR : recursion. (Or "mathematical induction" if you are a snobber.)

(Hereinafter “he is dead after he takes steps on the island” it is understood that “he dies after he is less than or equal to steps n .” If you understand “he dies after exactly n steps”, the answer will be somewhat otherwise, I will briefly talk about this at the end.

We have an NxN matrix, where the value in each cell represents the probability of death in steps n , if we started with this cell.

Consider the probability of death in steps 0 . It is understood that this is 0.0 for each location inside the island and 1.0 everywhere outside it.

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

Similarly, the probability of death in steps k , starting from a given cell, is the average value of the probability of dying in steps k-1 , starting from its neighboring 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 a bit: ( mpr is just a matrix printing function)

 >>> 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 cannot die in 0 steps if you start on 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 expect. If you start with a corner cell, you have a 0.5 chance of dying in 1 step: 2 of your 4 neighbors are outside the island. If you start from the edge, only one neighbor is outside, so your probability of death is 0.25 . Everywhere, all neighbors are inside the island, so the probability of death by 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 

Chance of death in 5 steps. I can’t check the exact values, but it looks right: the probability of death is highest in the corners, slightly lower at the edges and steadily decreasing inward.

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

Now, to find the probability of dying exactly in steps of n : let the probability of death in steps of less than t20> starting from (x,y) be denoted by P(x,y,n) . Then the probability of death at points n is the probability of survival for steps n-1 times the probability of death at step n , given that we survived for steps n-1 : (1-P(x,y,n-1))*(P(x,y,n) - P(x,y,n-1)) . (I'm not so sure about this formula; correct me if I'm wrong.)

Answer 2

First, start with the matrix with the probability of being squared (x, y) at step 0. Let it simulate it using a 4x4 matrix. Assuming the guy starts with (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 computes 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() 

Answer 3

This is a very complex and subtle problem. I suspect that the purpose of the interviewers was not to hear that you came up with an answer, but rather to understand how you approach the problem.

The problem becomes a chessboard of n squares on the side, with a clearly random placement of the part that should move n spaces, moving in an apparently random cardinal direction at each turn. Thus, the likelihood that a piece will remain on the board is associated not only with the size of the board, but also with the placement of the piece. Since any movement of the board is also considered an exit from the board, the path that the piece occupies is therefore also important.

For a 2 × 2 grid, a piece has a 2/7 chance of being on the board (four paths remain on the board, fourteen common tracks, regardless of which of the four possible starting points).

For a 3 × 3 grid, a piece has a 2/11 probability on board (16 paths remain, 88 common tracks) if it starts at a corner. If it starts from the side, it has a probability of 3/11 (24 paths remain on). If it starts in the center, it has a probability of 9/22 (36 paths remain on). Since a piece has a probability of 4/9, each of which starts in a corner or side, and a probability of 1/9 to start in the center, its overall probability of remaining on the board is (2/11 + 3/11) × 4/9 + 9/22 × 1/9 = 0.247.

A 4 × 4 grid becomes (obviously) even more complex, but it may be worth noting that the grids correspond to the pattern:

2 × 2 :

 - - 1 - - - 2 - 2 - 1 - 2 - 1 - 2 - 2 - - - 1 - - 

3 × 3 :

 - - - 1 - - - - - 3 - 3 - - - 3 - 9 - 3 - 1 - 9 - 9 - 1 - 3 - 9 - 3 - - - 3 - 3 - - - - - 1 - - - 

I started working with a 4x4 grid, but not thanks. The starting square seems to have 36 paths leading to it, and actually identifying them, well, is tedious. In each case, the piece begins in the center of the drawing, and we can draw the board as we see.

However, it is obvious that there is a pattern, and it screams rather that there is mathematical symmetry, but I have neither the time nor the patience to solve it. Each pole has one path, the next group of endpoints has n paths, and the next group has n ² paths. I suspect that I made a mistake when calculating the innermost set of endpoints for a 4 × 4 grid, but if I don’t, then 36 = n (n - 1) ² which strongly suggests a pattern for rings.

In any case, as I said, the problem is very complex, and almost certainly your approach is suing, and not your ability to respond to it. However, it was a fun exercise.

Answer 4

The approach should be based on a probability formula - no favorable cases / total number of cases

Specified coordinate (x, y) and steps - n The total number of ways the user can take action -
1st step - 4 ways; 2nd step - 4 * 3 (if he cannot retreat) 3rd step - 4 * 3 ^ 2 ... .... ... n-th step - 4 * 3 ^ (n-1) Advances in arthritis will give common steps.

Favorite cases, i.e. border crossing is a recursive fuction with recursion in all 4 directions and the incr variable count whenever a matrix border is crossed.

Separate both to get an answer.

Answer 5

Thanks to Anubhav C for a great solution that was very helpful in highlighting the issue. I think that using 0.25 in probability (mentioned above) can be misleading and wrong! If we look at the probability of # dead_cases / # total_possible_moves, the results will be different.

Consider the following code to search for dying / surviving cases:

 def winLoss_stat(N, steps): newStats = [[[0, 0, 0] for i in range(N)] for j in range(N)] if steps==0: newStats = [[[1, 0, 0] for i in range(N)] for j in range(N)] return newStats oldStats = winLoss_stat(N, steps-1) for i in range(N): for j in range(N): for d in [(0, 1), (0, -1), (1, 0), (-1, 0)]: indX = i + d[0] indY = j + d[1] if indX >=0 and indX < N and indY >= 0 and indY<N: newStats[i][j][0] += oldStats[indX][indY][0] newStats[i][j][1] += oldStats[indX][indY][1] newStats[i][j][2] += oldStats[indX][indY][2] else: newStats[i][j][1] += 1 if steps==1: newStats[i][j][2] = 1 return newStats (or equivalently, for one step (using dfs - recursive): class winLoss: def __init__(self, N): self.win = 0 self.loss = 0 self.N = N def winLoss(self, x, y, n): if x < 0 or y < 0 or x >= self.N or y >= self.N: self.loss += 1 return if n == 0: self.win += 1 return self.winLoss(x - 1, y, n-1) self.winLoss(x, y - 1, n-1) self.winLoss(x+1, y, n-1) self.winLoss(x, y+1, n-1) wl = winLoss(n) wl.winLoss(i, j, n) for any i,j start point and n (size of square) ) The winLoss_stat returns three values for starting point at each square i, j: [numbers of survive cases, numbers of die cases before or at k steps, numbers of death exactly at step k] The results are as the following for n=4 (4X4), steps=4: 0 1 2 3 0 [58, 24, 12] [93, 34, 18] [93, 34, 18] [58, 24, 12] 1 [93, 34, 18] [150, 46, 28] [150, 46, 28] [93, 34, 18] 2 [93, 34, 18] [150, 46, 28] [150, 46, 28] [93, 34, 18] 3 [58, 24, 12] [93, 34, 18] [93, 34, 18] [58, 24, 12] This translates to the following probabilities for 1. death before or at k steps: 0 1 2 3 0 0.292683 0.267717 0.267717 0.292683 1 0.267717 0.234694 0.234694 0.267717 2 0.267717 0.234694 0.234694 0.267717 3 0.292683 0.267717 0.267717 0.292683 2. death exactly at k steps: 0 1 2 3 0 0.146341 0.141732 0.141732 0.146341 1 0.141732 0.142857 0.142857 0.141732 2 0.141732 0.142857 0.142857 0.141732 3 0.146341 0.141732 0.141732 0.146341 The results can be verified by looking at the numbers of win-loss from step 1 to 3 for n=3: winLoss_stat(3, 1) 0 1 2 0 [2, 2, 1] [3, 1, 1] [2, 2, 1] 1 [3, 1, 1] [4, 0, 0] [3, 1, 1] 2 [2, 2, 1] [3, 1, 1] [2, 2, 1] winLoss_stat(3, 2) 0 1 2 0 [6, 4, 2] [8, 5, 2] [6, 4, 2] 1 [8, 5, 2] [12, 4, 4] [8, 5, 2] 2 [6, 4, 2] [8, 5, 2] [6, 4, 2] winLoss_stat(3, 3) 0 1 2 0 [16, 12, 4] [24, 13, 8] [16, 12, 4] 1 [24, 13, 8] [32, 20, 8] [24, 13, 8] 2 [16, 12, 4] [24, 13, 8] [16, 12, 4]