Return to the Minotaur's Labyrinth

Question

This is an extension of the puzzle The Minotaur's Labyrinth which is inspired by the comments from histocrat.

You are trapped (again) in a chamber at the center of the minotaur's labyrinth. There are $N$ tunnels, $m$ of which lead to safety; the remaining tunnels only lead back to the chamber. Each tunnel is of a different length, taking $h_i$ hours to travel. Each time you return to the chamber, the room shifts so that you can only choose tunnels at random. However, this time you find the distribution of tunnel length inscribed on the wall. You still don't know the length of any particular tunnel, but you know the distribution of lengths.

You have 24 hours until the Minotaur wakes up. If you are already in a safe tunnel when he wakes up, you will escape safely.

---

Case 1 Suppose there are 10 tunnels such that $$h_i = \begin{cases} i, & i = 1, 2, \cdots 9 \\ 100, & i = 10 \end{cases}$$ and $2$ tunnels lead to safety.

1. What is the optimal strategy you should use?
2. Using the optimal strategy, what is the expected time it will take you to escape?
3. Using the optimal strategy, what is the probability that you will escape?

---

Case 2 Suppose there are 10 tunnels such that $$h_i = 2^i$$ and $2$ tunnels lead to safety.

1. What is the optimal strategy you should use?
2. Using the optimal strategy, what is the expected time it will take you to escape?
3. Using the optimal strategy, what is the probability that you will escape?

---

The strategy with the best probability of survival for case 2 will be accepted.

Using a computer (simulation) to answer questions 2 and 3 is allowed.

---

Some Clarifications

• A priori, each tunnel has an equal chance of being "safe"
• You only know that the tunnel you are in is "safe" once you have traveled to the end of it and realize that you have escaped the labyrinth.
• When you return to the chamber, the room shifts so that you have no knowledge even of which tunnel you just traveled.
• I admit, I'm unsure of how one would demonstrate "optimality" here. For now, I'm mostly interested in maximizing probability of survival. The current score to beat is 30.50% by ffao.

Answer 1

The first observation is that our optimal strategy has to consist of, every time we enter a tunnel, determining a cutoff distance d at which we will turn around and come back.

For Case 1, since we have a tunnel that is much bigger than the others (tunnel with length 100), we would expect the optimal strategy to avoid taking this tunnel whenever possible to allow for more exploration, turning at 9 most of the time. Indeed, let's denote by t how much time we have left before the Minotaur arrives, then this is the optimal strategy:

t=20, didn't go through any tunnels: turn at 9
t=21, went through tunnel with size 1: turn at 9
t=21, went through tunnel with size 3: turn at 9
t=22, didn't go through any tunnels: turn at 9
t=22, went through tunnel with size 1: turn at 9
t=22, went through tunnel with size 2: turn at 9
t=23, went through tunnel with size 1: turn at 9
t=24, didn't go through any tunnels: turn at 9

This gives a winning probability of 59.45%. Assuming you do win, you're expected to take 21.10 hours to do it.

For Case 2, there are several large tunnels and several small tunnels. It makes sense to come back frequently to try for one of the small ones; the large ones consume too much time. And this is what we see in the optimal strategy, as it turns back quite early to try to explore smaller tunnels:

t=14, didn't go through any tunnels: turn at 2
t=14, went through tunnel with size 4: turn at 2
t=14, went through tunnel with size 8: turn at 2
t=16, didn't go through any tunnels: turn at 2
t=16, went through tunnel with size 4: turn at 2
t=16, went through tunnel with size 8: turn at 2
t=18, didn't go through any tunnels: turn at 4
t=18, went through tunnel with size 4: turn at 2
t=20, didn't go through any tunnels: turn at 4
t=20, went through tunnel with size 4: turn at 2
t=22, didn't go through any tunnels: turn at 4
t=24, didn't go through any tunnels: turn at 4

The winning probability of this strategy is 30.50%. Assuming you do win, you're expected to take 572.22 hours.

(This answer earlier solved the arguably more interesting case in which $h_i = 2^{i-1}$ instead of $h_i=2^i$. See the edit history for the strategy in that case.)

In case it isn't obvious by this point, no, I did not generate these tables by hand :)

The c++ code I used to determine these strategies can be found here: https://pastebin.com/vFU9tc2D

Answer 2

Partial :
CASE 1 :

It takes on average $\frac{\sum h_i}{10}$ hours to try one tunnel, and the chance to find the a correct tunnel is $\frac 2{10}$ so on average you will need to try $\frac {10}2$ tunnels. $\frac{\sum h_i}{10}$ X $\frac {10}2$ = $\frac{\sum h_i}2$.
If I understand correctly, the last tunnel takes 100 hours, so the most efficient thing to do is turn back after 9 hours. so 18 hours will be consumed.

$\sum h_i=1+2+3+4+5+6+7+8+9+18=63$

So on average it will take $\frac{63}2 = 31.5$ hours to find the exit.

I am not sure how to calculate the probability to get out in time but I suppose it is something like :
You need to take into account that your are safe past 24h if in a good tunnel so : $\frac{63}{10} * \frac 2{10} = 1.26$ -> average time of 1 path divided by the chance of being in a good path gives the average time extension.
And the final probability would be something like :
Probability that $24 + 1.26 \gtrsim 31.5$

Important note. If m = 1 and the 10th tunnel is the correct one.... tough luck.

CASE 2 :

It takes on average $\frac{\sum h_i}{10}$ hours to try one tunnel, and the chance to find the a correct tunnel is $\frac 2{10}$ so on average you will need to try $\frac {10}2$ tunnels. $\frac{\sum h_i}{10}$ X $\frac {10}2$ = $\frac{\sum h_i}2$.

$\sum h_i=1+4+8+16+32+64+128+256+512+1024=2045$

So on average it will take $\frac{2045}2 = 1022.5$ hours to find the exit.

I am not sure how to calculate the probability to get out in time but I suppose it is something like :
You need to take into account that your are safe past 24h if in a good tunnel so : $\frac{2045}{10} * \frac 2{10} = 204.5$ -> average time of 1 path divided by the chance of being in a good path gives the average time extension.
And the final probability would be something like :
Probability that $24 + 204.5 \gtrsim 1022.5$

EDIT
I forgot to optimize. When the path takes too long, it is best to turn back and try another path to raise your chances slightly. Returning after 8 hours is the only one that makes sense because returning at 16 hours would not be fast enough to try a new path.