My last post, on the 17 x 17 challenge, ended with a solution to a problem which I thought sounded incredibly naïve* but which turned out to be correct. It got me thinking about a problem that I was posed when I was interviewing to work at investment banks. In fact I was asked the same question in interviews for two different banks (potential applicants take note).

It goes like this: You find yourself in a dark cave, which has three tunnels leading from it (see the crude sketch on the right). One of the tunnels leads outside, and it takes 3 hours to traverse it. The other two tunnels connect to each other, returning you to the cave, and they take 1 hour to walk down. If you choose tunnels at random each time you’re faced with a choice, how long will it take you on average to get outside?

I’m about to tell you the answer, so maybe you want to stop and think about it for a bit. The point I’m making is that even though the calculation you have to do is a bit involved (although simple to anyone who’s ever studied Markov chains) there’s a cheeky shortcut: you can get the answer just by assuming that you take each of the tunnels once, and add up the times to traverse them, getting an answer of 1+1+3=5 hours.

Is this just a coincidence? To find out, let’s generalise the problem. Now we find ourselves in a cave with *n* tunnels, of which *m* of them lead to an exit and *n-m* dump you back in the cave. Each of the tunnels takes time to traverse, for *i*=1,…,*n*, and is chosen with probability . We’ll adopt the convention that the first *m* tunnels are the ones that lead to an exit, and the last *n-m* are the return tunnels (notice that our generalisation allows the possibility that a return tunnel might take a different amount of time to traverse if we go in the opposite direction).

To work out what the average escape time is, we notice that if we pick an escape tunnel then we’re free in the time it takes to traverse the tunnel. If we pick a return tunnel, then we’ve increased our expected time to leave by the time that it took to traverse the tunnel. If the time to leave is *T*, then we write the expected leaving time as E[*T*], and

.

After a couple of lines of algebra we see that the expected time to leave is given by

or, written in everyday language:

Avg time to leave = (Avg tunnel length) ÷ (Chance of picking an exit tunnel)

That’s it! The average time to escape only depends on the average time it takes to traverse a randomly picked tunnel, and the probability of picking a tunnel which leads to an exit. It’s completely insensitive to the specifics of the problem, namely how long the individual tunnels are, and what the precise probabilities of picking each tunnel are. In the special case where each of the tunnels is equally likely, all you have to do is add up the time it takes to traverse each of the tunnels, and divide by the number of tunnels that lead to an exit.

This appeals to me because a problem which has a lot of fine detail turns out to be insensitive to the fine detail. I’d be interested to hear about other examples of this phenomenon.

* Is it pretentious to write ‘naïve’ instead of ‘naive’? Answers, opinions and furious rants on a postcard, please.

## 13 comments

Comments feed for this article

December 11, 2009 at 10:56 pm

JasperSpeaking purely pragmatically, is this problem assuming that the traverser is dumb? If one of the routes leads you back into the cave via another route, surely that counts as both of those tunnels traversed and discounted? If there’s a mathematical response to that question, speak slowly.

December 13, 2009 at 3:02 pm

Chris TaylorI didn’t make it clear enough when I wrote it down, but essentially, yes: you assume the traverser is dumb. Or more precisely, I think I was told that ‘dark’ means ‘pitch black’ so you really are choosing randomly each time.

It’s something that annoys me a bit about mathematical puzzles like this one (and maths in general, actually…) However much fun they are to think about, someone can always come along and point how how devastatingly unrealistic they are.

December 12, 2009 at 12:52 pm

qoqoszActually you don’t need to know anything about Markov chains to solve this simple example.

Probability of success (leaving the cave) is p=1/3. Expected value of geometric distribution is 1/p=3. So it means that on average you’ll choose bad tunnel twice and the third choice will be good. Avg. travel time is just 1+1+3=5 – good result using only basic methods :)

December 13, 2009 at 3:22 pm

Chris TaylorI hadn’t thought of it as a geometric dist’n. Thanks!

December 13, 2009 at 10:57 am

David ColquhounJaspar has a point

Unless the victim was blindfolded and spun round between attempts, it wouldn’t be Markovian. If you noted which tunnel you entered, and which you emerged from if it was the blind one, then you wouldn’t use either of them again.

That seems to leave two ways of getting out

(1) You choose the right tunnel first time, probability 1/3, time= 3 hours

(2) You choose one of the wrong tunnels first time, prob=2/3, time=1 hour but then inevitably choose the right tunnel next time, time = 3 hours, total time 4 hours.

I think that gives a mean escape time of 3 hours*(1/3) + 4 hours*2/3 = 3.6667 hours (rather than 5 hours if it were possible to keep repeating the mistake)

December 14, 2009 at 12:26 am

Chris TaylorThanks for the comment David. I completely agree with you – if you note which tunnels you have already used, it’s not Markovian. As I mentioned in my reply to Jasper, this is one of those mathematical puzzles which has very little relation to the real world!

December 13, 2009 at 10:49 pm

She-LigerThe right answer is 4,2.

David’s answer is right too, if we accept his admission that the victim is capable to note which tunnel it came out from.

Markov’s chains can’t be used here at all.

December 14, 2009 at 12:27 am

Chris TaylorHow do you calculate 4.2?

I disagree that Markov chains can’t be used here. If you don’t recall which tunnels you’ve already been down, the probabilities of moving to a new state are independent of your history – the Markov property is easily seen to be satisfied!

December 14, 2009 at 5:46 pm

She-LigerI calculate like David does it. But I don’t accept that victim can understand that two tunnels are connected, because this admission is absent in the specification of task. Solving without this admission we shall get the answer 4,2.

And how do YOU calculate 5? Even without any calculations we can see that average value CAN’T be equal to 5. Calculate the full time in maximally possible solution! It is equal 1+1+3=5. And then calculate minimally possible solution. It is equal 3. It is clear that average will lie BETWEEN 5 and 3, but will never be equal 5 or 3.

To receive right solution it is necessary to calculate the “ways” as David does, but not tunnels as you do.

It is NOT Markovian process. And David’s task is not Markovian.

How does victim choose the tunnels in your task?

1) The probabilities of choice for all three tunnel is equal in the first step. For example, the victim chooses the second tunnel, comes in it and comes out from third tunnel to the cave.

2) What tunnel can victim choose in the second step? Either the first or the third, but not the second, because the victim chose this tunnel in the first step.

Let the victim choose the third tunnel. The victim comes in the third tunnel and comes out from the second tunnel.

3) What tunnel can victim choose in the third step? Only the first, because the victim can’t choose the second and the third tunnels on the basis of the task’s specification.

Now, let we consider, what we would receive in Markovian task.

1) The probabilities of choice for all three tunnel is equal in the first step. The victim chooses the second tunnel and comes out from third tunnel.

2) What tunnel will the victim choose in the second step? Either the first or the third, but not the second, because it chose this tunnel in the first step.

For example, the victim chooses the third tunnel. The victim comes in the third tunnel and comes out from the second tunnel.

3) What tunnel can victim choose in the third step? Either the first or the second! But not the third because the victim chose the third tunnel in previous step. Nevertheless the victim can choose the second tunnel again, because the victim “remembers” only previous step, but doesn’t “remember” the first step, when the second tunnel was chosen.

Do you see the difference?

And David’s task is not Markovian, because victim in his task is capable to choose the first tunnel already in the second step, because the victim “remembers” about the second tunnel on the basis of task’s specification and the victim understands that the third tunnel is connected with the second. So David’s task has more strict conditions. The number of ways in his task is 2, maximum is 4, minimum is 3, the probabilities are 1/3 and 2/3, the full times in the ways are 3 and 4, and average is 3,66(6).

His task can be solved by other method. Then, the number of ways is 3, maximum is 4, minimum is 3, the probabilities are 1/3, 1/3 and 1/3, the full times in the ways are 3; 4 and 4, and average is 3,66(6).

This is two equivalent methods! They give the same answer.

In my solution – the number of ways is 5, maximum is 5, minimum is 3, the probabilities are 1/5, 1/5, 1/5,1/5 and 1/5, the full times in the ways are 5; 5; 4; 4 and 3, and average is 4,2.

December 14, 2009 at 6:58 pm

Chris TaylorYou get an average of 5 by assuming that the victim doesn’t remember *at all* what tunnels they have been down. So they can take a tunnel and then, in their blind stumbling, go down it again the next time. In which case the problem is Markovian, and the average isn’t restricted to be between 3 and 5 because they can take the same tunnel multiple times :)

December 14, 2009 at 8:29 pm

She-LigerIt is not so. If you accept the condition: “you take each of the tunnels once”, then you will always receive 4,2.

But if you abolish this condition, you turn your task into “infinite”. The average will be infinite in general case, i.e. it will be very indeterminate value.

And if you bound such task (for example, mentioned here Markovian task is always bounded by the number of steps), then the average will always depend on the boundary condition, which you choose.

In brief, the average 5 is impossible in general case.

Uh-huh! ;)

December 15, 2009 at 1:16 am

Chris TaylorOkay. You’re either a lot smarter than I am, or a lot stupider. I can’t decide which.

December 15, 2009 at 2:14 am

She-LigerReally? ;) In such cases David Hilbert recommended to change the mathematics to poetry. But don’t be upset! ;) Poets earns more money than mathematicians… :P