Fog Creek Software
Discussion Board




Heaven's Infinite Sume

Here's the infinite sum for the heaven problem. You'll have to bear with the formatting here....

Sum from 1 to infinity of : (2^(n-1))/(3^n)  + (2^(n-1))/(3^n) * 2 

The first few iterations look like this (add the days together):

Day 1: 1/3 *1 + 1/3 *2

Day 2: 1/9 *1 + 1/9*1 + 1/9*2 + 1/9*2 == 2/9*1+2/9*2

Day 3: (1/27+1/27+1/27+1/27)*1 + (1/27+1/27+1/27+1/27)*2 == 4/27*1+4/27*2

Day N: 2^(n-1)/3^n*1+2^(n-1)/3^n*1

When you actually take the sum of the first 10 or so, you get about 3 days.

It grows like this because for every extra day, there is a 1/3 chance (*2) from the day before you pick the wrong door again, but there are also exponentially more paths you can get to any given state, hence the 2^n-1. For example the first three days could look like:

Day1 Day2 Day3
111
112
121
122
211
212
221
222

To pick a day 1 door on your third day, there is only 1/27 chance of it happeneing, but there are 4 different paths of three days which could lead you to this 4th day error.

I hope this was moderately coherent.

Just another kid
Thursday, September 05, 2002

*  Recent Topics

*  Fog Creek Home