5 ms·

Quick puzzle: how long to get to heaven?

13 points by strategy 16y ago

oscardelben 16y ago
This is how I solved it before looking at the answers: I calculated that from a scale of 0 and 1, we have a 0.33 chance of going in in 0 days. The probability of going in within 1 day is equal to the probability of choosing the second door (0.33) multiplied to the probability of choosing the first door the second time (0.33). 0.33 * 0.33 is equal to 0.1089, so we have a 10% chance of getting in with 1 days. To get in in 2 days, we would have to choose the second door, and then the first door. Again, this is another 10% At this point I thought that we have a 53% chance of getting in within two days (33% + 10% + 10%), and 47% of getting in with more than 2 days. The probability of getting in within 3 days is 0.33 * 0.33 * 0.33, which is around 3%. Considering that the probability of getting in within 4 days would be 1% (0.33 * 0.33 * 0.33 * 0.33), I somehow imagined that of the remaining 47% of chances of getting in within more than two days, the 75% was represented by the probability of getting in within 3 days. The 75% of 47% is 35.2%, which is slightly higher than the chance of getting in within 0 days. The answer is 3. Given that I lack math background, I wonder if my way of solving this problem is correct (hopefully someone can follow my reasoning).
- gjm11 16y ago
  > I wonder if my way of solving this problem is correct Nope, sorry :-). First, you missed a bunch of possibilities (e.g., you said that to get in after 2 days you need to choose 2,0, but you could choose 1,1,0 instead; you said that to get in after 3 days you need to choose 1,1,1,0, but you could also choose 1,2,0 or 2,1,0). Second, at best what you've got is an estimate. Third, the question wasn't "what's the most likely time it takes", which I think is what you've tried to work out, but "how long on average". (The most likely time is actually 0 days.)
  - oscardelben 16y ago
    Thanks!
cletus 16y ago
The interesting part of this problem for me is the OP's recurrence relation he comes up with at the end that makes the problem (trivially) soluble is the same skill required to solve dynamic programming problems.
trevelyan 16y ago
Saint Augustine makes the argument that for God to exist, time must not.
- gjm11 16y ago
  Ho ho ho. But, er, does he? He says that God exists outside time, and that time is measured by its impact on human minds; he says that past and future things don't exist; but it seems to me that he says that time does exist. Whether he expected heaven to involve any experience of time for its human inhabitants, I don't know.
  - trevelyan 16y ago
    I wasn't intending to deride the point. I was just surprised I hadn't run into anyone else before who made the observation, since it implies that the very existence of time depends on one's frame of reference, that's all.
gjm11 16y ago
The answer to any question of this form is: Unless you happen to be able to solve it quickly by doing mathematics, simulate! import random def one(): n = 0 while True: k = random.randint(0,2) if k==0: return n n += k def many(k): return sum(one() for i in range(n)) / float(n) [many(1000) for i in range(10)] many(100000) will make it pretty easy to guess what the right answer is. The previous-but-one posting on the same blog has a distinctly more difficult question: repeatedly pick independent random numbers uniform on [0,1]; stop when your latest number is smaller than some previous one; what's the average number of numbers you have to pick? Exercise for the reader: provide the appropriate definition of one() to make the calculation above work. It's only a few lines. (Mathematically expert readers will be able to solve both these problems rigorously and quickly without simulating. But if such a problem comes up in a context where you actually care about the answer you'd do well to do the simulation anyway, since it's an easy way to check your reasoning.)
- ojbyrne 16y ago
  I know you just tossed off that code, but I wanted to run it. I think n should have been k in the line "return sum(one() for i in range(n)) / float(n)"
  - gjm11 16y ago
    Actually it should have been "def many(n)" instead of "def many(k)" :-), but yes. Thanks for the bugfix. Too late to edit it in, alas.
patio11 16y ago
Expected value of a single game: 1 day delay. Chance of "winning" a replay: 2/3. The has no memory so all picks are independent. Sum of infinite geometric series, done. This is math team math all the way: if you were asking any question I might have to think, but since it involves repetitive calculations of expected value (probability times result), infinite length, and a trick allowing hand calculability, I know it has to decompose to sum of an infinite geometric series somehow. Some variants left as an exercise to the reader: a) Three door game as above with doors where A = heaven, B = 2 days + retry, and C = 4 days plus retry. If you get the lesson, this should be trivial. b) Write a Satan's version of the three door game, where the rules look "simple enough" but the expected time to reach heaven is not finite. (This would be a great extra credit problem for a high school advanced math course -- and full points and a smiley face for "Doors A, B, and C all say 'come back tomorrow'.")
- bambax 16y ago
  Do you even need to think about infinite geometric series? You have a 1/3 chance of picking the direct door, so on average it will take you three tries to catch it. 1 try == 1 day delay expected (1/3 x 0 + 1/3 x 1 + 1/3 x 2). 3 tries, 3 days.
qtrng 16y ago
This was strikingly similar to a recent TopCoder problem: http://www.topcoder.com/stat?c=problem_statement&pm=11193&rd=14241 http://www.topcoder.com/stat?c=problem_statement&pm=1119... I've run into a few problems like this. The simplest solution exploits the property that there is an ordering on the states, so each "later" state can depend only on "earlier" states or itself. A more general EV problem would require Gaussian elimination instead of DP. Fun stuff, all in all.

13 points by strategy 16y ago

This is how I solved it before looking at the answers: I calculated that from a scale of 0 and 1, we have a 0.33 chance of going in in 0 days. The probability of going in within 1 day is equal to the probability of choosing the second door (0.33) multiplied to the probability of choosing the first door the second time (0.33). 0.33 * 0.33 is equal to 0.1089, so we have a 10% chance of getting in with 1 days. To get in in 2 days, we would have to choose the second door, and then the first door. Again, this is another 10% At this point I thought that we have a 53% chance of getting in within two days (33% + 10% + 10%), and 47% of getting in with more than 2 days. The probability of getting in within 3 days is 0.33 * 0.33 * 0.33, which is around 3%. Considering that the probability of getting in within 4 days would be 1% (0.33 * 0.33 * 0.33 * 0.33), I somehow imagined that of the remaining 47% of chances of getting in within more than two days, the 75% was represented by the probability of getting in within 3 days. The 75% of 47% is 35.2%, which is slightly higher than the chance of getting in within 0 days. The answer is 3. Given that I lack math background, I wonder if my way of solving this problem is correct (hopefully someone can follow my reasoning).

gjm11 16y ago
> I wonder if my way of solving this problem is correct Nope, sorry :-). First, you missed a bunch of possibilities (e.g., you said that to get in after 2 days you need to choose 2,0, but you could choose 1,1,0 instead; you said that to get in after 3 days you need to choose 1,1,1,0, but you could also choose 1,2,0 or 2,1,0). Second, at best what you've got is an estimate. Third, the question wasn't "what's the most likely time it takes", which I think is what you've tried to work out, but "how long on average". (The most likely time is actually 0 days.)
- oscardelben 16y ago
  Thanks!

cletus 16y ago

The interesting part of this problem for me is the OP's recurrence relation he comes up with at the end that makes the problem (trivially) soluble is the same skill required to solve dynamic programming problems.

trevelyan 16y ago

Saint Augustine makes the argument that for God to exist, time must not.

gjm11 16y ago
Ho ho ho. But, er, does he? He says that God exists outside time, and that time is measured by its impact on human minds; he says that past and future things don't exist; but it seems to me that he says that time does exist. Whether he expected heaven to involve any experience of time for its human inhabitants, I don't know.
- trevelyan 16y ago
  I wasn't intending to deride the point. I was just surprised I hadn't run into anyone else before who made the observation, since it implies that the very existence of time depends on one's frame of reference, that's all.

gjm11 16y ago

The answer to any question of this form is: Unless you happen to be able to solve it quickly by doing mathematics, simulate! import random def one(): n = 0 while True: k = random.randint(0,2) if k==0: return n n += k def many(k): return sum(one() for i in range(n)) / float(n) [many(1000) for i in range(10)] many(100000) will make it pretty easy to guess what the right answer is. The previous-but-one posting on the same blog has a distinctly more difficult question: repeatedly pick independent random numbers uniform on [0,1]; stop when your latest number is smaller than some previous one; what's the average number of numbers you have to pick? Exercise for the reader: provide the appropriate definition of one() to make the calculation above work. It's only a few lines. (Mathematically expert readers will be able to solve both these problems rigorously and quickly without simulating. But if such a problem comes up in a context where you actually care about the answer you'd do well to do the simulation anyway, since it's an easy way to check your reasoning.)

ojbyrne 16y ago
I know you just tossed off that code, but I wanted to run it. I think n should have been k in the line "return sum(one() for i in range(n)) / float(n)"
- gjm11 16y ago
  Actually it should have been "def many(n)" instead of "def many(k)" :-), but yes. Thanks for the bugfix. Too late to edit it in, alas.

patio11 16y ago

Expected value of a single game: 1 day delay. Chance of "winning" a replay: 2/3. The has no memory so all picks are independent. Sum of infinite geometric series, done. This is math team math all the way: if you were asking any question I might have to think, but since it involves repetitive calculations of expected value (probability times result), infinite length, and a trick allowing hand calculability, I know it has to decompose to sum of an infinite geometric series somehow. Some variants left as an exercise to the reader: a) Three door game as above with doors where A = heaven, B = 2 days + retry, and C = 4 days plus retry. If you get the lesson, this should be trivial. b) Write a Satan's version of the three door game, where the rules look "simple enough" but the expected time to reach heaven is not finite. (This would be a great extra credit problem for a high school advanced math course -- and full points and a smiley face for "Doors A, B, and C all say 'come back tomorrow'.")

bambax 16y ago
Do you even need to think about infinite geometric series? You have a 1/3 chance of picking the direct door, so on average it will take you three tries to catch it. 1 try == 1 day delay expected (1/3 x 0 + 1/3 x 1 + 1/3 x 2). 3 tries, 3 days.

qtrng 16y ago

This was strikingly similar to a recent TopCoder problem: http://www.topcoder.com/stat?c=problem_statement&pm=11193&rd=14241 http://www.topcoder.com/stat?c=problem_statement&pm=1119... I've run into a few problems like this. The simplest solution exploits the property that there is an ordering on the states, so each "later" state can depend only on "earlier" states or itself. A more general EV problem would require Gaussian elimination instead of DP. Fun stuff, all in all.