August 1, 2011 in Thinking Analytically
Escape from Markov’s Prison
SHARE: PRINT ARTICLE:
https://doi.org/10.1287/LYTX.2011.04.15
After years of being captive in Markov’s prison you have decided it is time to escape. A sketch of the prison is shown in Figure 1. The path to freedom begins when you enter room No. 1 and exit the prison through room No. 16. Unfortunately, there are two very vigilant guards who are on duty and have been walking through the rooms for years. If you and a guard are in the same room at the same time, you will be caught and sentenced to life in prison. Fortunately, over time, you have observed that the guards’ movements are dictated by the following probabilities:
Every second that passes, you and the guards each move to a new room. If the probability instructs a guard to move into a wall, the guard will simply stand still for that iteration. The guards, like you, cannot move diagonally.
Probabilities |
| Guard No. 1: • 20 percent of the time he moves north • 40 percent of the time he moves south • 20 percent of the time he moves west • 20 percent of the time he moves east Guard No. 2: |
Questions:
1) Entering at room No. 1 and exiting the prison at room No. 16, what route will give you the best chance of escape?
2) What is the probability that you will be caught?
Send your answer to [email protected] by Sept 15. The winner, chosen randomly from the correct answers, will receive an “Analytics: Driving Better Business Decisions” T-shirt.
John Toczek is the AVP Predictive Modeling at Chubb in the Decision Analytics and Predictive Modeling department. He earned his BSc. in Chemical Engineering at Drexel University (1996) and his MSc. in Operations Research from Virginia Commonwealth University (2005).