title: Probability of death of a man moving n steps in a matrix
body: <p>There is an island which is represented by square matrix nxn. </p>
  
  <p>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. </p>
  
  <p>Let the island be represented as (0,0) to (n-1,n-1) (i.e nxn matrix) &amp; 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? </p>
  
  <blockquote>
    <p>What should be the approach to find the probability using programming techniques?</p>
    
    <p>I have a mathematical method, but I don't know whether it's correct or not. Here it is:</p>
  </blockquote>
  
  <p>The total number of outcomes are n^n. To calculate the number of outcomes which can lead to death of the person:</p>
  
  <p>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)</p>
  
  <blockquote>
    <p>This was a Google interview question.</p>
  </blockquote>