1
$\begingroup$

With the following box, you have to get from point 1 to point 2. You can move up, down, left or right. The borders and the X squares are objects that you are not allowed to get through.

-------------
|  |  |  | 2|
-------------
|  | X|  | X|
-------------
| 1|  |  |  |
-------------

Every time I move I get 80% chance to move where I want and 20% chance to move to an orthogonal direction, distributed uniformly. For example, if I want to move left, I get 80% chance to move to the left and 10% chance to move up and 10% chance to move down. If I want to move up, I get 80% chance to move up, 10% chance to move left and 10% chance to move right. If the square I move is a forbidden one, then I stay on the place from where I moved.

What's the path that gives me the higher probability of getting from point 1 to point 2? and what is the probability of the path up, up, right, right and right?

$\endgroup$
5
  • 1
    $\begingroup$ "distributed normally" — Do you mean "uniformly"? $\endgroup$ Jun 19, 2017 at 2:34
  • $\begingroup$ Yes, uniformly distributed. $\endgroup$
    – capm
    Jun 19, 2017 at 2:47
  • $\begingroup$ You can formalise the problem as two Markov chains and then use the formula $(I - Q)^{-1} J$ for to calculate the expected number of moves before you get to the absorbing state (i.e. the square marked 2). ;) $\endgroup$ Jun 19, 2017 at 7:06
  • $\begingroup$ @Waves It's not that simple: the Markov chain is not determined until the optimal strategy has been developed. This is a simple example of making a sequence of decisions under uncertainty, a situation where a decision tree is an appropriate generalization of the Markov chain for analysis. $\endgroup$
    – whuber
    Jun 19, 2017 at 14:33
  • $\begingroup$ @whuber I see - Actually I realised the question was more complicated than I thought after I attempted to work it out myself as well. Thanks! $\endgroup$ Jun 19, 2017 at 15:53

1 Answer 1

3
$\begingroup$

I presume you mean to ask which direction should you attempt in order to get to 2 in the smallest expected number of moves--you'll reach the finish with probability 1 eventually.

You have to get to the square to the left of 2. So what's the better way to get to that square, going right twice and then up twice or up twice and then right twice? Both paths are identical except that the square right of 1 by two squares is "doubly-exposed," i.e. you have a 20% chance of moving in an unhelpful direction while attempting to move up from there, while only a 10% chance of moving in an unhelpful direction from the top left corner. I'll let you fill in the rigor since this might be a homework problem.

As far as the "probability of a path": the probability of going on exactly that path, given that you are attempting to take that path, is just the product of the probabilities of moving to the desired next square at each step. Finding these probabilities is easy if the path you gave can't include "stay" moves. If "stay" moves are allowed, you might have to use the geometric series formula to prove that some intuitive probability results hold.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.