Probability of survival

Question

There is an island represented by a matrix. You are somewhere on an island at (x,y) . If you jump n times, what is the likelihood that you will survive? Survival means that after jump n you must be on the island.

My solution: I applied the flood fill algorithm , in which I was allowed to move in all directions (i.e. N, W, E, S) and is checked if I was at the island before the n jumps, then increase the failure counter, otherwise increase the success counter.

After repeating all possible paths, the answer will be ((success) / (success + failure)). It takes exponential time.

My question is from you - can we solve this problem in polynomial time using dynamic programming or any other programming technique? If so, can you give me a concept for this technique?

EDIT: MY CODE

 #include<iostream> using namespace std; double probability_of_survival(int n, int m, int x, int y, int jumps) { int success = 0; int failure = 0; probability_of_survival_utility_func(n, m, x, y, 0, jumps, &sucess, &failure); return (double)((success)/(failure+success)); } void probability_of_survival_utility_func(int n, int m, int x, int y, int jump_made, int jumps, int *success, int *failure) { if(x > m || x < 0 || y > n || y < 0) { (*failure)++; return;} if(jump_made == jumps) { (*success)++; return;} probability_of_survival_utility_func(n, m, x+1, y, jump_made++, jumps, success, failure); probability_of_survival_utility_func(n, m, x, y+1, jump_made++, jumps, success, failure); probability_of_survival_utility_func(n, m, x-1, y, jump_made++, jumps, success, failure); probability_of_survival_utility_func(n, m, x, y-1, jump_made++, jumps, success, failure); } 

Answer 1

 f(x,y,0) = 0 if (x,y) is not in the island 1 otherwise f(x,y,i) = 0 if (x,y) is not in the island otherwise: 1/4 * f(x+1,y,i-1) + 1/4 * f(x-1,y,i-1) + 1/4 * f(x,y+1,i-1) + 1/4 * f(x,y-1,i-1) 

Using dynamic programming, you can create a 3-dimensional array 2n+1 x 2n+1 x n+1 and fill it in accordance with this formula, starting from i=0 and moving up to i=n .

Your solution at the end is f(0,0,n) in the array. (Remmeber for setting the original (x, y) in the form of (0,0) in your coordinates and making the necessary settings).

Complexity O(n^3) is the size of the matrix.

Please note: this is a pseudo-polynomial solution, therefore, if any future answers show that this problem is NP-Hard (I don’t know if this is the case) - this does not contradict it.

PS For real implementations - if you need an exact answer - be very careful when using double-precision numbers - especially for a large number of steps, since a numerical error can become significant.

Answer 2

The problem is described in detail by the Markov matrix. Transfer the problem to the schedule as follows. Match the rows of the matrix with the coordinates, i.e. For all possible (x,y) -> i . Construct a symmetric adjacency matrix A such that (i,j)=1 if and only if the sites (x1,y1)->i, (x2,y2)->j are connected. All death sites will be displayed on one site and have a property such that A[i,i]=1 , A[i,j!=i]=0 ie these are adsorbing states. The row normalizes the matrix. With the starting vector p=[0,0,0,...,1,...,0,0] , where one corresponds to the starting position, take the product:

  (A**k) . p 

And summarize on live sites, this will give you a chance of survival. For analysis, the number of notes here is n , the number of live sites on the island. The complexity is neatly connected, the most expensive operation is the exponential exposure of the matrix A**k . You can naively do this in O(n**3 * k) , but I suspect that you can first diagonalize the matrix at the cost of O(n**3) and increase its eigenvalues.

Visual example:

An island with a red starting point and adjacency matrix:

calculated probability of survival as a function of steps:

Python implementation:

 from numpy import * # Define an example island L = zeros((6,6),dtype=int) L[1,1:2] = 1 L[2,1:4] = 1 L[3,1:5] = 1 L[4,2:4] = 1 # Identify alive sites alive = zip(*where(L)) N = len(alive) # Map the entries onto an index for easy access ID = dict(zip(alive, range(N))) # Create adj. matrix, the final index is the dead site def connect(x, horz, vert): s = (x[0]+horz, x[1]+vert) if s not in ID: A[ID[x], N] += 1 else : A[ID[x], ID[s]] += 1 A = zeros((N+1,N+1)) for x in alive: connect(x, 1, 0) connect(x, -1, 0) connect(x, 0, 1) connect(x, 0,-1) # Define the dead site as adsorbing, and row normalize A[N,N] = 1 A /= A.sum(axis=1)[:,newaxis] # Define the initial state inital = (3,2) p0 = zeros(N+1) p0[ID[inital]] = 1 # Compute survival prob. as a function of steps steps = 20 A2 = A.copy() S = zeros(steps) for t in xrange(steps): S[t] = 1-dot(A2.T,p0)[-1] A2 = dot(A2, A) # Plot results import pylab as plt plt.subplot(121) LSHOW = L.copy() LSHOW[inital] = 2 plt.imshow(LSHOW,interpolation='nearest') plt.subplot(122) plt.imshow(A,interpolation='nearest') plt.figure() plt.plot(range(steps), S,'ro--') plt.show()