Light bulb puzzle
March 11th, 2020 at 6:41:01 PM
permalink
You have 10 light bulbs going. Each has an average life of 1 year. The life expectancy of each bulb follows an exponential distribution. What this means is the bulbs are never overdue to burn out. Regardless of how long a bulb has been burning, it is no closer to burning out. The average remaining time is always one year per bulb. It is the same principle as waiting for a royal flush in video poker -- no matter how long you've been waiting for one, you're no closer to getting one (assuming no change in strategy).
That said, what is the mean waiting time for the LAST bulb to burn out?
Usual rules:
That said, what is the mean waiting time for the LAST bulb to burn out?
Usual rules:
- Please don't just plop a URL to a solution elsewhere until a winner here has been declared.
- All those who have won a beer previously are asked to not post answers or solutions for 24 after this posting. Past winners who must chime in early, may PM me.
- Beer to the first satisfactory answer and solution, subject to rule 2.
- Please put answers and solutions in spoiler tags.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 12th, 2020 at 3:56:38 PM
permalink
Tic Toc. There's still team to join the prestigious beer club. I have had correct answers by PM from those already on it. This puzzle is pretty easy, I think, so if you've ever wanted to gain some math geek points here at WoV, this is your shot.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 14th, 2020 at 10:20:11 AM
permalink
Any chance of an answer to this soon? I can't seem to find a function of probability of any sort versus time that works.
March 14th, 2020 at 3:25:43 PM
permalink
I know better than to attempt math/probability problems (better to be thought a fool than speak up and remove all doubt), but I might have had a light turn on, so:
1/365 chance of a bulb burning out on that day, but 10 bulbs to start
so, expected time to lose first bulb is 10/365 or 1/36.5 per day, or 36.5 days average time to lose first bulb.
9 bulbs left, 9/365 chance per day (365/9=40.5556) so 40.5556 days for next bulb (77.056 days total)
8/365 chance per day (365/8=45.625) 122.681 total
7/365=52.1429 122.681+52.1429=174.8239 days so far
6/365; 365/6=60.8333; 60.8333+174.8239= 235.6572
5/365; 365/5=73; 73+235.6572=308.6572
4/365; 365/4=91.25; 91.25+308.6572=399.9072
3/365; 365/3=121.6667; 121.6667+399.9072=521.5739
2/365; 365/2=182.5; 182.5+399.9072=582.4072
1/365; 365/1=365; 365+582.4072=947.4072 days expected until all 10 burn out. (2.5956 years)
March 14th, 2020 at 5:18:50 PM
permalink
This one is wide open to members and non-members of the beer club. I would hate to have to post a solution to this fairly easy problem. Very basic probability and statistics.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 14th, 2020 at 5:38:37 PM
permalink
Quote: WizardThis one is wide open to members and non-members of the beer club. I would hate to have to post a solution to this fairly easy problem. Very basic probability and statistics.
Thanks Wiz, for making "us simpletons*** " feel even worse.
Is the solution that "easy", that it will probably be an "aha" or "light-bulb" moment for most of us that didn't think of it in time?
***: I am a "statistics simpleton", yet I also consider myself "above average at probability".
March 14th, 2020 at 6:35:12 PM
permalink
Quote: ksdjdjThanks Wiz, for making "us simpletons*** " feel even worse.
I'm sorry. That could have been worded better.
I will say one probably needs to know the basics of the exponential distribution to solve this one. If you don't, I would leave this one alone.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 14th, 2020 at 8:56:46 PM
permalink
Quote: Wizard(snip) I will say one probably needs to know the basics of the exponential distribution to solve this one. If you don't, I would leave this one alone.
I will probably leave this one alone, but do we need to work out the standard deviation to solve this puzzle and if yes is it (see spoiler)
Does the standard deviation equal to the "average life" (mean)?
March 15th, 2020 at 4:49:55 AM
permalink
Quote: ksdjdj
Does the standard deviation equal to the "average life" (mean)?
Yes
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 15th, 2020 at 4:29:06 PM
permalink
Unless there is a request for more time, I will post the answer and solution myself tomorrow.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 15th, 2020 at 4:37:17 PM
permalink
Posting my PM'd answer at the Wizard's request:
First, note that if we know the expected time T_N for the first of N lightbulbs to burn out, then we can reduce the problem to T_N +T_{N-1}, since the exponential distribution is memoryless. If there are N lightbulbs, since each expires independently, then they are N times as likely to burn out as 1 lightbulb. So, the expected time T_N is equal to 1/N. IIRC, it's also true that it follows an exponential distribution with mean 1/N, but we only really need the expected time for the first lightbulb for this problem. Then, we can sum over all 10 lightbulbs, giving 1/10 + 1/9... + 1 = the 10th Harmonic number H_10 = 7381/2520.
March 15th, 2020 at 4:45:55 PM
permalink
Quote: djtehch34tPosting my PM'd answer at the Wizard's request:
First, note that if we know the expected time T_N for the first of N lightbulbs to burn out, then we can reduce the problem to T_N +T_{N-1}, since the exponential distribution is memoryless. If there are N lightbulbs, since each expires independently, then they are N times as likely to burn out as 1 lightbulb. So, the expected time T_N is equal to 1/N. IIRC, it's also true that it follows an exponential distribution with mean 1/N, but we only really need the expected time for the first lightbulb for this problem. Then, we can sum over all 10 lightbulbs, giving 1/10 + 1/9... + 1 = the 10th Harmonic number H_10 = 7381/2520.
Congratulations! This correct. I owe you another beer.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 15th, 2020 at 5:11:48 PM
permalink
I will have a go, the worst that will happen, is that I won't "win/be owed a beer" (which would be the same result as not answering at all)
Note: some of this may be "irrelevant to the question", but I am also trying to learn.
If the average life(mean) for 1 light bulb is 1 year, then 50% of the light bulbs last ~0.69*** years (or less)
*** = LN(0.5)/-1
So, this got me thinking, for 10 light bulbs to = 0.5, you need to do this
0.5√10 = 0.93....
then 1-0.93.... = 0.0669...
Therefore. the average life of the last bulb is : 2.70...^^^ years
^^^ = LN(0.0669670084631926)/-1
(Edit/update): Since the answer by djtehch34t above is correct, I didn't find the average (mean), instead I think I found the "median" (but I could easily be wrong, since I am new at this).
Note: In this case, the mean should be bigger than the median, going by the articles I have read on the internet.
Note 2: I hope I am using the term median correctly (that is why i put " " around it, in case I am wrong in my interpretation).
Note 3: Again, I know the question was "....mean waiting time for the LAST bulb to burn out" , but I am mainly trying to learn, so I will be happy if I am correct with just getting the "median"
----
Edit/update: Congrats to djtehch34t (the response from the Wiz wasn't posted, when I first started writing my post).
Note: some of this may be "irrelevant to the question", but I am also trying to learn.
If the average life(mean) for 1 light bulb is 1 year, then 50% of the light bulbs last ~0.69*** years (or less)
*** = LN(0.5)/-1
So, this got me thinking, for 10 light bulbs to = 0.5, you need to do this
0.5√10 = 0.93....
then 1-0.93.... = 0.0669...
Therefore. the average life of the last bulb is : 2.70...^^^ years
^^^ = LN(0.0669670084631926)/-1
(Edit/update): Since the answer by djtehch34t above is correct, I didn't find the average (mean), instead I think I found the "median" (but I could easily be wrong, since I am new at this).
Note: In this case, the mean should be bigger than the median, going by the articles I have read on the internet.
Note 2: I hope I am using the term median correctly (that is why i put " " around it, in case I am wrong in my interpretation).
Note 3: Again, I know the question was "....mean waiting time for the LAST bulb to burn out" , but I am mainly trying to learn, so I will be happy if I am correct with just getting the "median"
----
Edit/update: Congrats to djtehch34t (the response from the Wiz wasn't posted, when I first started writing my post).
Last edited by: ksdjdj on Mar 15, 2020
March 17th, 2020 at 10:04:08 AM
permalink
Extra credit:Quote: WizardYou have 10 light bulbs going. Each has an average life of 1 year. The life expectancy of each bulb follows an exponential distribution. What this means is the bulbs are never overdue to burn out. Regardless of how long a bulb has been burning, it is no closer to burning out. The average remaining time is always one year per bulb.
Same problem except each light bulb will be instantly* replaced once and only once after it burns out the first time. On average, how long until the last bulb burns out permanently (after being replaced once)?
No beer rules. First correct answer gets a valuable stock market tip.
*assume instantly means zero time needed to replace
It’s all about making that GTA
March 17th, 2020 at 4:43:50 PM
permalink
Quote: Ace2Same problem except each light bulb will be instantly* replaced once and only once after it burns out the first time. On average, how long until the last bulb burns out permanently (after being replaced once)?
Good question. I hope to post an answer (hopefully a correct one) later today.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 17th, 2020 at 8:08:33 PM
permalink
Assuming I programmed it right, using the recurrence T_{i, j} = ((i-j)/i T_{i-1, j} + j/i T_{i, j-1}) + 1/i, where i is the current number of bulbs and j is the number of those with a backup, calculating T_{10, 10} via dynamic programming I get ~4.6229.
March 17th, 2020 at 8:39:53 PM
permalink
Quote: djtehch34tAssuming I programmed it right, using the recurrence T_{i, j} = ((i-j)/i T_{i-1, j} + j/i T_{i, j-1}) + 1/i, where i is the current number of bulbs and j is the number of those with a backup, calculating T_{10, 10} via dynamic programming I get ~4.6229.
That is a correct approximation (all digits shown are correct), but there is a formulaic solution with the answer expressed as an integer.
Last edited by: Ace2 on Mar 17, 2020
It’s all about making that GTA
March 18th, 2020 at 9:24:40 AM
permalink
I’ll post the solution a bit later today unless someone wants more time?
It’s all about making that GTA
March 18th, 2020 at 9:46:58 AM
permalink
Quote: Ace2I’ll post the solution a bit later today unless someone wants more time?
I'd like to work on it tonight, if you don't mind.
March 18th, 2020 at 11:07:58 AM
permalink
Quote: Ace2I’ll post the solution a bit later today unless someone wants more time?
I've already invested about 3 or 4 hours into this. Yeah, give me some more time too.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 18th, 2020 at 3:03:22 PM
permalink
I've got an enormous spreadsheet going that is doing this the hard way, but I don't think I'm going to bother finishing it. Maybe something more elegant will come to me.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 18th, 2020 at 3:26:13 PM
permalink
Okay. I’ll give djtehch34t some more time before I post the solution
It’s all about making that GTA
March 18th, 2020 at 4:34:59 PM
permalink
Quote: Ace2Okay. I’ll give djtehch34t some more time before I post the solution
I had an idea while roller-blading just now. Please wait for me to officially throw in the towel first.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 18th, 2020 at 5:22:27 PM
permalink
Here is my answer only. It was done in a fairly small spreadsheet, looking at all 55 possible states of the light bulbs, the probability of getting to each one, and the expected time to get there. It is just a number, no formulas.
4.622957064
Last edited by: Wizard on Mar 19, 2020
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 18th, 2020 at 7:01:10 PM
permalink
Quote: Ace2Okay. I’ll give djtehch34t some more time before I post the solution
I was able to derive an expression for T[N][1], but T[N][N] seems out of reach of my techniques. I think generating functions might make the recurrence easier to work with, but I don't have time to try that now.
Nice problem. Looking forward to seeing a closed form solution.
Nice problem. Looking forward to seeing a closed form solution.
March 18th, 2020 at 7:47:55 PM
permalink
The answer is the integral from zero to infinity of:
1 - (1 - x/e^x - 1/e^x)^10 =
335641897646511216668163083 /
72603291141126144000000000
=~ 4.62 years
Here is my long-winded explanation of the formula. I’m sure a real math guru could explain it more eloquently.
If, for instance, we throw a single die and want to know the probability that a number has not appeared after x rolls, we take (5/6)^x. We also know that the sum of a geometric series equals 1 / (1 - a). So (5/6)^0 + (5/6)^1 + (5/6)^2 + .... = 1 / (1 - 5/6) = 6. What this infinite series says is: the sum of the probabilities that an event has not yet occurred at every possible state in time equals the average time the event will take to occur. In this case the average rolls needed to roll a number is 6.
Fortunately, this property is also true for exponential distributions. I don’t have the proof but I know it works, which seems reasonable since the exponential distribution is basically the continuous version of the geometric distribution. So to calculate the average time for our event to happen (all light bulbs to go out), we just need to sum the probabilities that they have not all gone out...at all possible times.
We use the Poisson distribution, where x is years passed, f is frequency, x/f = expected value and p = (x/f)^k / (e^(x/f)*k!). For our problem, a light burns out every 1 years on average so f = 1. The chance it has gone out once is x^1 / (e^x * 1!) and the chance it has gone out zero times is x^0 / (e^x * 0!). Therefore, the chance it has gone out more than once is the complement of those two states: 1 - x/e^x - 1/e^x. That probability for all 10 bulbs is (1 - x/e^x - 1/e^x)^10. And since we want to know the sum of the probabilities of NOT being in that state for all time, we take the integral from zero to infinity of 1 - (1 - x/e^x - 1/e^x)^10 =~ 4.62 years
1 - (1 - x/e^x - 1/e^x)^10 =
335641897646511216668163083 /
72603291141126144000000000
=~ 4.62 years
Here is my long-winded explanation of the formula. I’m sure a real math guru could explain it more eloquently.
If, for instance, we throw a single die and want to know the probability that a number has not appeared after x rolls, we take (5/6)^x. We also know that the sum of a geometric series equals 1 / (1 - a). So (5/6)^0 + (5/6)^1 + (5/6)^2 + .... = 1 / (1 - 5/6) = 6. What this infinite series says is: the sum of the probabilities that an event has not yet occurred at every possible state in time equals the average time the event will take to occur. In this case the average rolls needed to roll a number is 6.
Fortunately, this property is also true for exponential distributions. I don’t have the proof but I know it works, which seems reasonable since the exponential distribution is basically the continuous version of the geometric distribution. So to calculate the average time for our event to happen (all light bulbs to go out), we just need to sum the probabilities that they have not all gone out...at all possible times.
We use the Poisson distribution, where x is years passed, f is frequency, x/f = expected value and p = (x/f)^k / (e^(x/f)*k!). For our problem, a light burns out every 1 years on average so f = 1. The chance it has gone out once is x^1 / (e^x * 1!) and the chance it has gone out zero times is x^0 / (e^x * 0!). Therefore, the chance it has gone out more than once is the complement of those two states: 1 - x/e^x - 1/e^x. That probability for all 10 bulbs is (1 - x/e^x - 1/e^x)^10. And since we want to know the sum of the probabilities of NOT being in that state for all time, we take the integral from zero to infinity of 1 - (1 - x/e^x - 1/e^x)^10 =~ 4.62 years
Last edited by: Ace2 on Mar 18, 2020
It’s all about making that GTA
March 19th, 2020 at 4:06:00 AM
permalink
Thanks Ace.
This is vaguely coming back to me from college statistics 35 years ago (man I'm old!).
To use a simple example, the expected time to get a 6 on a fair die is also the integral from 0 to infinity of (1/6) exp (-x/6) dx
Ace submitted such a form of an answer to the first light bulb problem and I incorrectly rebuked him, thinking he was just approximating the answer.
I just spent an hour looking over my old college probability and statistics text, which is as beaten as a good Christian's bible, and couldn't find this principle in writing, but I know it's in there somewhere.
Does anyone else on the forum the term of why this is true? I'd like to see a proof of it, or at least a name for theorem.
This is vaguely coming back to me from college statistics 35 years ago (man I'm old!).
To use a simple example, the expected time to get a 6 on a fair die is also the integral from 0 to infinity of (1/6) exp (-x/6) dx
Ace submitted such a form of an answer to the first light bulb problem and I incorrectly rebuked him, thinking he was just approximating the answer.
I just spent an hour looking over my old college probability and statistics text, which is as beaten as a good Christian's bible, and couldn't find this principle in writing, but I know it's in there somewhere.
Does anyone else on the forum the term of why this is true? I'd like to see a proof of it, or at least a name for theorem.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
March 19th, 2020 at 8:14:05 AM
permalink
I first saw this method used to calculate the expected number of rolls to get all faces of a die twice.
Like the light bulb problem, calculating the expected value to get all faces once is easy: 6/6 + 6/5 + 6/4 + 6/3 + 6/2 + 6/1 = 14.7 rolls
But the calculation to get each face twice is surprisingly more complex. It’s the integral over all time of
1 - (1 - (x/6)/e^(x/6) - 1/e^(x/6))^6 =~ 24.13 rolls
Like the light bulb problem, calculating the expected value to get all faces once is easy: 6/6 + 6/5 + 6/4 + 6/3 + 6/2 + 6/1 = 14.7 rolls
But the calculation to get each face twice is surprisingly more complex. It’s the integral over all time of
1 - (1 - (x/6)/e^(x/6) - 1/e^(x/6))^6 =~ 24.13 rolls
It’s all about making that GTA
May 22nd, 2020 at 1:19:51 PM
permalink
Here is my solution to the two light bulb per socket version (PDF).
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
May 31st, 2020 at 2:10:22 PM
permalink
New light bulb problem:
Light bulbs have an average life of 1 year, following the exponential distribution. New light bulbs are turned on at an average of 1 per year, also following the exponential distribution.
Starting from t = 0 (no light bulbs are on), how long will it take, on average, for the first light bulb to burn out? The first to burn out isn’t necessarily the first to be turned on.
Caveat: I think I have the exact answer but I’m not 100% sure since I haven’t been able to confirm it with a thorough simulation (I’m not a programmer, just Excel)
Light bulbs have an average life of 1 year, following the exponential distribution. New light bulbs are turned on at an average of 1 per year, also following the exponential distribution.
Starting from t = 0 (no light bulbs are on), how long will it take, on average, for the first light bulb to burn out? The first to burn out isn’t necessarily the first to be turned on.
Caveat: I think I have the exact answer but I’m not 100% sure since I haven’t been able to confirm it with a thorough simulation (I’m not a programmer, just Excel)
It’s all about making that GTA
September 12th, 2020 at 7:37:46 AM
permalink
My latest answer, about the 6th or 7th, is apx. 1.6931468.
Last edited by: Wizard on Sep 12, 2020
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
September 12th, 2020 at 4:27:55 PM
permalink
My approach when it comes to math questions I don’t understand, is to guess Pi. Pi comes up in lots of weird unexpected places. Eventually I’ll be right.
If anyone gives you 10,000 to 1 on anything, you take it. If John Mellencamp ever wins an Oscar, I am going to be a very rich dude.
September 12th, 2020 at 5:05:59 PM
permalink
This time you might be on the right trackQuote: TinManMy approach when it comes to math questions I don’t understand, is to guess Pi. Pi comes up in lots of weird unexpected places. Eventually I’ll be right.
It’s all about making that GTA
September 13th, 2020 at 4:07:34 AM
permalink
I stand by the answer I submitted before. It turns out to be 1+ln(2) = 1.693147181.
First, it takes on average one year for somebody to turn on the first bulb.
Then consider the situation where the next event is that first bulb burns out. I won't get into why this works, because the method has been discussed in many of the craps side bet threads, but the expected time until that event equals:
Integral from 0 to infinity of pr(0 new light bulbs turned on over time t)*pr(first light bulb still on over time t)*(1/2) dt. =
Integral from 0 to infinity of exp(-t)*exp(-t)*t*(1/2) dt. = 1/8
Why the 1/2? It is because the probability the next significant event will be a bulb burning out, as opposed to another bulb being turned on.
Next, consider the expected time when a second bulb gets turned on after the first and then either goes out. This is equal to:
Integral from 0 to infinity of pr(1 new light bulbs turned on over time t)*pr(first light bulb still on over time t)*(1/2) dt. =
Integral from 0 to infinity of exp(-t)*exp(-t)*t^2*(2/3) dt. = 1/6
The general formula for the expected time when x bulbs get turned on, not including the first, before one goes out =
Integral from 0 to infinity of pr(x new light bulbs turned on over time t)*pr(no light bulbs burn out over time t)*(x+1)/(x+2) dt
Integral from 0 to infinity of exp(-t)*exp(-t)*t^x*((x+1)/(x+2)) dt
Here is a table showing the expected time by number of bulbs turned on after the first.
| Bulbs turned on after first | Expected time |
|---|---|
| 0 | 0.125000 |
| 1 | 0.166667 |
| 2 | 0.140625 |
| 3 | 0.100000 |
| 4 | 0.065104 |
| 5 | 0.040179 |
| 6 | 0.023926 |
| 7 | 0.013889 |
| 8 | 0.007910 |
| 9 | 0.004439 |
| 10 | 0.002462 |
| 11 | 0.001352 |
| 12 | 0.000737 |
| 13 | 0.000399 |
| 14 | 0.000215 |
| 15 | 0.000115 |
| 16 | 0.000061 |
| 17 | 0.000033 |
| 18 | 0.000017 |
| 19 | 0.000009 |
| 20 | 0.000005 |
| 21 | 0.000003 |
| 22 | 0.000001 |
| 23 | 0.000001 |
| 24 | 0.000000 |
| Total | 0.693147 |
Add one for the time it takes to turn on the first bulb and you're at 1.693147.
This turns out to be 1+ln(2).
To do the integration, I recommend www.integral-calculator.com/.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
September 14th, 2020 at 9:19:57 PM
permalink
A simulation, which is not easy to do with this problem, is getting a different answer, which I'll put in spoiler tags. Let's just say my confidence level is not as high.
1.718 years.
I'll run a longer simulation overnight to get more significant digits.
1.718 years.
I'll run a longer simulation overnight to get more significant digits.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
September 15th, 2020 at 4:13:30 AM
permalink
I think we can quit putting comments in spoiler tags. Here is the result of a longer simulation.
Trials = 34570000000
Total time =59401299162
Average time = 1.718290401
This is very close to e-1.
I've been communicating with ace2 via PM and he gets to e-1 directly. He should get the credit for solving it first. I'll let him explain the method. It's embarrassing I didn't do it his way to begin with.
Here is my simulation code, in case anyone is interested.
Trials = 34570000000
Total time =59401299162
Average time = 1.718290401
This is very close to e-1.
I've been communicating with ace2 via PM and he gets to e-1 directly. He should get the credit for solving it first. I'll let him explain the method. It's embarrassing I didn't do it his way to begin with.
Here is my simulation code, in case anyone is interested.
void light_bulb1(void)
{
__int64 count;
int nummin, stop;
double t, burn_out, next_burn_out,tot_time, next_turn_on;
unsigned int rn1,rn2;
time_t curtime, endtime;
cerr << "Enter number of minutes in simulation: ";
cin >> nummin;
curtime = time(NULL);
endtime = curtime + (60 * nummin);
count = 0;
tot_time = 0;
do
{
count++;
rn1 = max(1,genrand_int32());
t = -1*log(((double)rn1) / 4294967296.0); // time until first bulb is turned on
rn2 = max(1, genrand_int32());
burn_out = -1 * log((double)rn2 / 4294967296.0); // time until bulb burns out
stop = 0;
do
{
rn1 = max(1, genrand_int32());
next_turn_on = -1 * log(((double)rn1) / 4294967296.0);
if (next_turn_on > burn_out)
stop = 1;
else
{
t += next_turn_on;
burn_out -= next_turn_on;
rn2 = max(1, genrand_int32());
next_burn_out = -1 * log(((double)rn2) / 4294967296.0);
if (next_burn_out < burn_out)
burn_out = next_burn_out;
}
}
while (stop == 0);
t += burn_out;
tot_time += t;
if (count % 5000000 == 0)
{
curtime = time(NULL);
cerr << "Time remaining: " << (float)(endtime - curtime) / 60 << "\n";
// printf ("%I64i\t%f\t%f\n",count,tot_time,tot_time/(double)count);
}
}
while (curtime < endtime);
printf("count=\t%I64i\n", count);
printf("Total time=\t%f\n", tot_time);
printf("average time=\t%f\n", tot_time/(double)count);
return;
}
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
September 15th, 2020 at 7:33:45 AM
permalink
I originally thought the answer was related to pi but then I thought of a much simpler solution. It was like a light bulb came on in my head, haha
Starting from first light bulb lit, there is a 1/2 year avg waiting time until next event (new bulb or burnout). Then there is a 1/2 chance we’re done and a 1/2 chance we go to 2 bulbs. From there it’s 1/3 year avg waiting time until the next event. Then there is a 2/3 chance we’re done and 1/3 chance we go to 3 bulbs. And so on
Using a system of linear equations:
x = 1/2 + 1/2a
a = 1/3 + 1/3b
b = 1/4 + 1/4c
c = 1/5 + 1/5d
etc
The system evaluates to 1/2 + 1/6 + 1/24... = 1/2! + 1/3! + 1/4!....which equals (surprise surprise) e minus 2 or about 0.718. Add 1 for the year it takes for first bulb to light for e -1 = 1.718 average years for the first bulb to burn out
Thanks to the Wizard for confirming the solution with the simulation. The simulation was probably more difficult than the problem itself
Starting from first light bulb lit, there is a 1/2 year avg waiting time until next event (new bulb or burnout). Then there is a 1/2 chance we’re done and a 1/2 chance we go to 2 bulbs. From there it’s 1/3 year avg waiting time until the next event. Then there is a 2/3 chance we’re done and 1/3 chance we go to 3 bulbs. And so on
Using a system of linear equations:
x = 1/2 + 1/2a
a = 1/3 + 1/3b
b = 1/4 + 1/4c
c = 1/5 + 1/5d
etc
The system evaluates to 1/2 + 1/6 + 1/24... = 1/2! + 1/3! + 1/4!....which equals (surprise surprise) e minus 2 or about 0.718. Add 1 for the year it takes for first bulb to light for e -1 = 1.718 average years for the first bulb to burn out
Thanks to the Wizard for confirming the solution with the simulation. The simulation was probably more difficult than the problem itself
Last edited by: Ace2 on Sep 15, 2020
It’s all about making that GTA
September 15th, 2020 at 9:10:23 AM
permalink
Quote: Ace2Thanks to the Wizard for confirming the solution with the simulation. The simulation was probably more difficult than the problem itself
You're welcome.
Yes, it was a tricky simulation to do properly. I would hate to say how much time I spent on this problem between a calculus solution that was evidently wrong and then the simulation.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
September 15th, 2020 at 11:49:59 AM
permalink
I did my simulation in excel.
First I split a year into 10,000 units with each unit having a 1 in 10,000 of a light bulb coming on. I went out 100,000 units (10 years) and kept a cumulative total of light bulbs on. The expected number of bulbs turned on after 10 years is 10 (same as exponential distribution) and the chance of no bulbs being turned on is 1 in 22,037, not exactly the exponential distribution but very close to 1/e^10 = 1 in 22,026
The probability a bulb goes out changes as the cumulative number turned on increases. If 3 are on, then the probability one goes out in the next iteration is 1 - (1 - 1/10,000)^3
Finally a vlookup for when the first bulb went out (only 1 in 22000 chance one hasn’t gone out after 10 years)
It’s a simple simulation but 400,000 rows. I could do a max of 100 trials (columns) per calculation without my computer freezing up. But even after 100 x 200 = 20,000 trials, the answer was just starting to converge to 1.72.
First I split a year into 10,000 units with each unit having a 1 in 10,000 of a light bulb coming on. I went out 100,000 units (10 years) and kept a cumulative total of light bulbs on. The expected number of bulbs turned on after 10 years is 10 (same as exponential distribution) and the chance of no bulbs being turned on is 1 in 22,037, not exactly the exponential distribution but very close to 1/e^10 = 1 in 22,026
The probability a bulb goes out changes as the cumulative number turned on increases. If 3 are on, then the probability one goes out in the next iteration is 1 - (1 - 1/10,000)^3
Finally a vlookup for when the first bulb went out (only 1 in 22000 chance one hasn’t gone out after 10 years)
It’s a simple simulation but 400,000 rows. I could do a max of 100 trials (columns) per calculation without my computer freezing up. But even after 100 x 200 = 20,000 trials, the answer was just starting to converge to 1.72.
It’s all about making that GTA
October 2nd, 2020 at 4:35:05 PM
permalink
Another light bulb problem:
There is an infinitely long string of light bulbs, each 1 inch wide, which take an average of 1 day to burn out (following the exponential distribution).
There is a snail that crawls along the string at a constant speed of 1 inch per day. This endangered snail has eyes on the back of its head and can only see bulbs it has passed. It will stop when it sees the first bulb go out
Starting from t = 0 (all light bulbs are on), and with the snail at x=0 (start of first bulb) how far will the snail travel, on average, before stopping? Assume no spacing between the bulbs
There is an infinitely long string of light bulbs, each 1 inch wide, which take an average of 1 day to burn out (following the exponential distribution).
There is a snail that crawls along the string at a constant speed of 1 inch per day. This endangered snail has eyes on the back of its head and can only see bulbs it has passed. It will stop when it sees the first bulb go out
Starting from t = 0 (all light bulbs are on), and with the snail at x=0 (start of first bulb) how far will the snail travel, on average, before stopping? Assume no spacing between the bulbs
It’s all about making that GTA
October 2nd, 2020 at 5:54:37 PM
permalink
Quote: Ace2Another light bulb problem:
Ah. I love these light bulb problems. I'll need to percolate on this one.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
October 2nd, 2020 at 7:00:55 PM
permalink
Quote: Ace2There is a snail that crawls along the string at a constant speed of 1 inch per day. This endangered snail has eyes on the back of its head and can only see bulbs it has passed. It will stop when it sees the first bulb go out
Does the snail have to see the light bulb go out or can is see a bulb that already went out?
For example, what happens if the first bulb goes out in half a day. Will the snail see it immediately or have to wait until he travels an inch? If he has to wait until he travels an inch, does it count that he saw a bulb that went out 12 hours ago?
Can this problem be reworded like the last one, except light bulbs get turned on exactly once a day, starting with one being turned on when time starts?
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
October 2nd, 2020 at 9:15:47 PM
permalink
The snail can see everything behind. So if any bulb behind him has gone out at any time, he can see it
I just realized I must work one more facet into this problem to deal with “partial” bulbs. Probably tomorrow
I just realized I must work one more facet into this problem to deal with “partial” bulbs. Probably tomorrow
It’s all about making that GTA
October 3rd, 2020 at 8:06:33 AM
permalink
This assumes that the snail cannot see the bulb it is currently passing until it has passed it entirely.
The probability that bulb 1 is out at the end of day 1, so the snail stops after 1 bulb, is 1 x (1 - 1/e)
The probability that bulb 1 is on at the end of day 1, but bulb 1 or 2 is out at the end of day 2, so the snail stops after 2 bulbs, is 2 x 1/e x (1 - 1/e^3)
The probability that bulbs 1-2 are both on at the end of day 2, but 1-3 are all out at the end of day 3, so the snail stops after 3 bulbs, is 3 x 1/e^4 x (1 - 1/e^5)
The probability that bulbs 1-3 are both on at the end of day 3, but 1-4 are all out at the end of day 4, so the snail stops after 4 bulbs, is 4 x 1/e^9 x (1 - 1/e^7)
The solution is
(1 - 1/e) + 2/e (1 - 1/e^3)+ 3/e^4 (1 - 1/e^5) + 4/e^9 (1 - 1/e^7) + ...
= 1 - 1/e + 2/e - 2/e^4 + 3/e^4 - 3/e^9 + 4/e^9 - 4/e^16 +
= 1 + 1/e + 1/e^4 + 1/e^9 + ...
= 1 + 1/e + (1/e)^2 + (1/e)^3 + ...
= 1 + 1 / (1 - 1/e))
= 1 + e / (e - 1)
= 2 + 1 / (e - 1)
= 2.5819767
October 3rd, 2020 at 2:55:21 PM
permalink
Here is the updated versionQuote: Ace2The snail can see everything behind. So if any bulb behind him has gone out at any time, he can see it
I just realized I must work one more facet into this problem to deal with “partial” bulbs. Probably tomorrow
There is one infinitely long light bulb filament. The filament has an average failure rate of one per foot per year...meaning for any/every one foot section of the filament, some part of that section will burn out once per year (on average following the exponential distribution). You could also say that any 10 foot section will have a failure every 1/10 years and any 0.1 foot section will have a failure every 1/0.1 years. The failure of a section does not affect any other section.
An endangered snail with eyes at the back of its head crawls along the filament at a rate of one foot per year. It will stop as soon as it sees any part of the filament burnt out...anywhere between the beginning of the filament and it's current position. This snail has perfect, infinite vision.
Starting at t=0 (entire filament is lit) and x=0 (snail at beginning of filament), how far do we expect the snail to crawl before stopping ?
Last edited by: Ace2 on Oct 3, 2020
It’s all about making that GTA
October 3rd, 2020 at 3:18:14 PM
permalink
This seems too easy. It seems to be asking the mean time until the first burnout, which is one year, as given in the wording of the question.
I must not be understanding what is being asked.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
October 3rd, 2020 at 4:14:21 PM
permalink
This is similar to my previous solution, but this time, assume the lightbulbs are spaced 1/n apart for some positive value n; in this case, n = positive infinity
The solution I get is 2/n + 1/n (e^(1/n) / (e^(1/n) - 1))
As n approaches positive infinity, this approaches e^(1/n) / (n (e^(1/n) - 1))); I have tried to grind out a number using L'Hopital's Rule, but have had no success yet, so I resorted to a spreadsheet, which says that the answer is 1.
October 3rd, 2020 at 9:56:36 PM
permalink
This is not the same as individual light bulbs, which can only go out in whole numbers.
For comparison purposes, let’s say light bulbs are 1 foot wide. That entire foot can be either on or off. But in this problem any part of that 1 foot can go out at any time...the 2 inches between inch 5 and 7, the 1/16 th of an inch between inch 3.5 and 3.5625 etc. And when the snail, looking backwards, sees any portion of the filament off, it stops.
Or my reasoning is wrong. One thing I dislike about these exponential distribution problems is they are very difficult to simulate. So I can’t confirm with a simulation, not yet anyway
ThatDonGuy: I think you were on the right track with your first solution. But you have to remove your initial assumption because the snail can look back at all times. Also, any part of the filament can go out at any time. I believe you might have the answer if you modify it to fit a continuous problem
For comparison purposes, let’s say light bulbs are 1 foot wide. That entire foot can be either on or off. But in this problem any part of that 1 foot can go out at any time...the 2 inches between inch 5 and 7, the 1/16 th of an inch between inch 3.5 and 3.5625 etc. And when the snail, looking backwards, sees any portion of the filament off, it stops.
Or my reasoning is wrong. One thing I dislike about these exponential distribution problems is they are very difficult to simulate. So I can’t confirm with a simulation, not yet anyway
ThatDonGuy: I think you were on the right track with your first solution. But you have to remove your initial assumption because the snail can look back at all times. Also, any part of the filament can go out at any time. I believe you might have the answer if you modify it to fit a continuous problem
Last edited by: Ace2 on Oct 3, 2020
It’s all about making that GTA
October 4th, 2020 at 8:37:16 PM
permalink
If the snail only looks back after an entire foot is completed (looks back after 1 foot, 2 feet 3 feet etc), then the chance it seeing no burnouts after, for instance, 3 feet would be 1/e^3 for each foot and (1/e^3)^3 = 1/e^9 for all 3 feet. From the geometric distribution, we know that the expected waiting time for an event to happen is equal to the sum of the probabilities of the event not happening over all time. This property is also true for exponential distributions. So for this case, the expected waiting time for the snail to see the first burnout is 1/e^0 + 1/e^1 + 1/e^4 + 1/e^9 ... =~ 1.3863 years. This is the sum from t=0 to t=infinity of 1/e^(t^2)
When the snail is always looking back and any part of the filament can go out an any time (the continuous version of the above scenario) the expected waiting time is the integral from t=0 to t=infinity of 1/e^(t^2) = π^.5 /.2 =~ 0.8862 years. Since the snail travels 1 foot per year it will have travelled, on average, 0.8862 feet before seeing part of the filament burn out.
I don't know how to simulate it but I did confirm the answer by doing a summation at every 0.001 years.
When the snail is always looking back and any part of the filament can go out an any time (the continuous version of the above scenario) the expected waiting time is the integral from t=0 to t=infinity of 1/e^(t^2) = π^.5 /.2 =~ 0.8862 years. Since the snail travels 1 foot per year it will have travelled, on average, 0.8862 feet before seeing part of the filament burn out.
I don't know how to simulate it but I did confirm the answer by doing a summation at every 0.001 years.
Last edited by: Ace2 on Oct 4, 2020
It’s all about making that GTA
