LightOJ 1027 - A Dangerous Maze

Problem Statement

Topic : Probability/Expected value

Short Discription :

You are in a maze; seeing n doors in front of you in beginning. You can choose any door you like. The probability for choosing a door is equal for all doors.

If you choose the ith door, it can either take you back to the same position where you begun in xi minutes, or can take you out of the maze after xi minutes. If you come back to the same position, you can't remember anything. So, every time you come to the beginning position, you have no past experience.

Now you want to find the expected time to get out of the maze.

Idea:

Say, total number of door is n and total number of door which bring you back to the beginning is n’ . And the expected time to get out of the maze is E.

As we know the probability of choosing a door is equal, for choosing any of the door the probability is ,     

Now, for the first case the expected time to get out with a door which has positive xi value is ,  
As you can directly go to the end with this type of door.

For the second case the expected time to get out with a door which has a negative xi value is,  
As you have to go to the beginning with xi time and then start again with this type of door.

Now, the final expected time to get out of the maze will be the average of expected time taken to take each door. So,

So, this is our expected  time to get out of the maze.

Solution: