Quick puzzle: how long to get to heaven?

For today, just a fun brain teaser that was passed along to me.

A person dies and arrives at the gates to heaven. There are three identical doors: one of them leads to heaven, another leads to a 1-day stay in limbo, and then back to the gate, and the other leads to a 2-day stay in limbo, and then back to the gate.

Every time the person is back at the gate, the three doors are reshuffled. How long, on the average, will it take the person to reach heaven?

There’s a quick way to solve this puzzle. Can you figure it out?

Hint: see method 3 of the dice brain teaser

I am going to narrate how I arrived at the answer. But if you just want the answer, skip ahead to the section labeled The answer.

A first attempt: the direct sum

I initially attempted the problem as a straight expectation: I would weight the number of days by its associated probability.

In other words, if pn is the probability of taking n days, then the average number of days would be:

N = 0 * p0 + p1 + 2p2 + 3p3 + 4p4 + 5p5…

The question is: how to calculate pn?

The first few cases are simple enough. There is only one way to make it in zero days–namely pick the right door on the first try–and so p0 is 1/3 (there are three doors, each equally likely to be picked).

To make it in one day again there is only one way–pick the door holding you for a day, and then pick the door going to heaven–and so that means p1 is 1/3 * 1/3 = 1/9.

Continuing, we can calculate the probability for taking two days. For this case, there are two different routes one could take. One route is to take the door holding for two days and then pick the door going to heaven (1/3 * 1/3), and the other route is to pick the door holding for one day twice and then pick the door to heaven (1/3 * 1/3 * 1/3). This means p2 = (1/3 * 1/3) + (1/3 * 1/3 * 1/3).

Note that the expression is not simplified. The reason is to demonstrate a pattern in the probability, namely that:

p2 = 1/3 * (p0 + p1)

Why should that be? The recursion happens because of the following observation. To take two days to reach heaven, you can either add two days to the case of taking zero days, or you can add one day to the case of taking one day. The coefficient of 1/3 is because adding that extra door in the route happens with probability 1/3.

This logic also applies to cases taking 3 or more days to get to heaven. So, for example, we can say that:

p3 = 1/3 * (p1 + p2)

The reason is that there are two possible ways to take three days to get to heaven. One can either add two days to a route taking a single day, or one could add a single day to a route taking two days.

The recursion formula applies generally, and we get the following formula:

pn + 2 = 1/3 * (pn + 1 + pn)

Recursive formulas like this are extremely useful as they can be programmed into spreadsheets readily. Once the probabilities for 0 and 1 days are inputted, the recursive formula can be used to determined each subsequent one.

With this method, I decided to sum up the partial sum up to 25 terms. From the third term and onwards, the calculation was based on the recursive formula.

Here is the result:

N P(N) N * P(N)
0 0.333 0.000
1 0.111 0.111
2 0.148 0.296
3 0.086 0.259
4 0.078 0.313
5 0.055 0.274
6 0.044 0.266
7 0.033 0.232
8 0.026 0.206
9 0.020 0.177
10 0.015 0.151
11 0.012 0.128
12 0.009 0.107
13 0.007 0.089
14 0.005 0.073
15 0.004 0.060
16 0.003 0.049
17 0.002 0.040
18 0.002 0.033
19 0.001 0.027
20 0.001 0.021
21 0.001 0.017
22 0.001 0.014
23 0.000 0.011
24 0.000 0.009
25 0.000 0.007
sum 2.97

This is an interesting result–the series evidently converges to 3.

Can this sum be proved to converge to 3?

I bet it can, but I have not yet worked it out–bonus points to anyone who comes up with the proof.

It was while working on this that I realized that this approach was  inefficient and not the easiest one.

It turns out there is an elegant and simple way to find the answer.

The answer

Let N denote the average number of days it takes to get to heaven.

The trick to solve for N is to rewrite the average using symmetry of the game.

N is equal to the average number of days regardless of which door you enter first. This splits up into three cases:

Case 1: One-third of the time you go directly to heaven, and that’s 0 days.

Case 2: One-third of the time you pick the door that adds 1 day. In this case, you end up in heaven in N + 1 days.

Case 3: The remaining one-third you pick the door that adds 2 days. In this case, you end up in heaven in N + 2 days.

These observations lead to the following equation and answer:

N = 1/3 * 0 + 1/3 * (N + 1) + 1/3 * (N + 2)

N = 1/3 *N + 1/3 + 1/3 *N + 2/3

N = 2/3 *N + 1

1/3 * N = 1

N = 3

This approach is much easier! And the answer is therefore that it will take 3 days to reach heaven.



Share this post:

| More

Previous post:

Next post:



  • Alex Greene

    Actually, it takes the rest of your life + 3 days, and technically you have to die first.

  • Jon

    Could you explain in greater detail, why for case 2, “In this case, you end up in heaven in N + 1 days” holds true? Sorry if it’s extremely obvious, but I don’t seem to get it.

  • mark

    No need for fancy math ;-)

    #!/usr/bin/env ruby

    def run
    positions = [1, 2, 3]
    days = 0
    while true
    choice = 1 + rand(2)
    positions.shuffle!
    position = positions[choice]
    case position
    when 1: break
    when 2: days += 1
    when 3: days += 2
    end
    end
    days
    end

    runs = 1000000
    days = 0.0
    runs.times { days += run }
    puts “avarage days to heaven: #{days/runs}”

    But yes, its 3 days on average…

  • Tristan

    Hi,
    As you suspected the direct sum can be proven to equal 3.
    Here is my proof: (I hope you can find one shorter)
    I started by finding a closed form function for the recurrence relationship for pn.
    Namely pn = C*k1^n+D*k2^n where
    C = (13+sqrt(13))/78
    k1 = (1+sqrt(13))/6
    D = (13-sqrt(13))/78
    k2 = (1-sqrt(13))/6
    Next you have the summation as
    N = ∑ (C*k1^n+D*k2^n)*n
    Or
    N = C ∑ n*k1^n + D ∑ n*k2^n
    Then you need to find what the sum of the infinite series of n*k^n is.
    Lucky for us, if you divide the sum by k it is the derivative of the geometric series, so
    ∑ n*k^n = k/((1-k)^2) where |k| < 1
    From there you now know that
    N = (C*k1)/((1-k1)^2) + (D*k2)/((1-k2)^2)
    Substitute and N = 3
    I have no idea how this will show up when posted. I apologize if anything is missing.

  • http://www.mindyourdecisions.com/blog/ Presh Talwalkar

    Thanks Tristan! Your solution led me to read about recurrence relations, which is the method I believed you used. I somehow never learned about this but it is extremely fascinating and I bet this idea comes up in many puzzles. I will read more about it and find out!

  • http://www.mindyourdecisions.com/blog/ Presh Talwalkar

    Jon: Think about this question: conditional on picking the door of 1 day, how long would you take on average to reach heaven?

    Because each trial is independent, you would still expect to take N days to get into heaven. But you’ve already spent 1 day in limbo, and hence your expected value, conditional on picking door of 1 day, is N+1.

    Same thing goes for picking the door with a 2 limbo stay, the conditional expectation will be N+2.

    Then we can equate the average to the sum of the conditional expectations:

    N = E(days door 0 | picking door 0)*Pr(picking door 0) + E(days door 1 | picking door 1)*Pr(picking door 1) + E(days door 2 | picking door 2)*Pr(picking door 2) = 1/3 * (0 + (N+1) + (N+2))

    And that is the same equation as before.

  • Eyal

    I did it the long way. I worked out how you get from your definitions of p_n to the recurrence relation (same as Tristan’s). Then I proved the formula for the sum from 0 to infinity of n*k^n. Near the end it gets messy but a lot of eignvalues (lambdas) cancel out and the result is 3.

    http://min.us/iddmcy.png

    Understanding how to derive the recurrence equations from the eignvalues is often useful for statistics.

  • http://www.mindyourdecisions.com/blog/ Presh Talwalkar

    Thanks Eyal for the detailed derivation–I truly appreciate it and learned a lot!

  • Nikhil Kejriwal

    Another way of looking at the problem is to think of choosing a gate as an episode. An episode consists of the event of choosing and it then includes the waiting time as well. So, each time you choose a gate, it is a new episode. Now, there will be a series of such episodes, this series will terminate if you choose the gate with 0 wait in any episode.

    Now, expected value of the wait in any episode is 0*(1/3) + 1*(1/3) + 2*(1/3) = 1

    Prob that you will experience next episode is 2/3 which is constant for all episodes.

    Expected value of wait accumulated over a series infinite episodes is

    1*(2/3) + 1*(2/3)^2 + 1*(2/3)^3 ….

    This is an infinite G.P. whose sum is 3.

  • Abhilash

    Nikhil: The infinite summation of this GP is 2. Please verify





Previous post:

Next post:

Other posts you may enjoy reading:

Random Posts

This site is for recreational and educational purposes only (privacy policy)

Powered by WordPress