-
February 25th, 2005, 08:05 PM
#1306
Re: question and answer thread.
Yes, inquriing minds would like to see the answer to this.
"The Chicken and Rice MRE is not a personal lubricant."
-
February 25th, 2005, 11:08 PM
#1307
Re: question and answer thread.
Originally Posted by SolarFlare
This process is repeated n times (so that n total toggles are made). What is the expected value for the number of lights that will be on when the process is complete, in terms of n and k?
Do you mean "n number of switches are toggled" ? You could toggle the same switch a trillion times.
-
February 26th, 2005, 11:56 AM
#1308
Re: question and answer thread.
Originally Posted by Sahir
Do you mean "n number of switches are toggled" ? You could toggle the same switch a trillion times.
Yeah. Well, I'll try to solve this now, two ways.
Method 1
I am looking for L(n,k), the number of lights on after n toggles of k switches. I will treat k as a constant, since it doesn't change once it has been selected, so I may use the notation L_n to mean L(n,k).
Suppose we know L_n. It is fairly simple to find the expected value L_(n+1) recursively:
L_(n+1) = L_n + (probability next lightswitch is turned on) - (probability next lightswitch is turned off) = L_n + p_on - p_off.
Well, p_on and p_off depend on the number of lights that are currently on (L) and the number of total lights (k):
p_off = L_n/k
p_on = (k-L_n)/k
So L_(n+1) = L_n + (k-L)/k - L/k = L_n + (k-2L_n)/k = (k+L_n*(k-2))/k.
Also it should be clear intuitively that L_0 = 0 (no lights are on at the beginning), and L_1 = 1 (you will always have one light on after one toggle), establishing a base case and completing the recursive formula.
That only helps a little, since the solution is supposed to be in closed form. So I have to escape recursion somehow. This is a little tricky. Consider what a graph of L vs n would look like. It would start off at 0, climb rapidly at first and then slow down, until it approached approximately k/2, because for n>>k, about half of the lights should be on. This sounds a lot like what an exponential graph does, so perhaps our formula can be modeled by an exponential formula.
Let L_n = k/2-b^n for some b.
Now k/2 - b^(n+1) = L_(n+1) = (k+L_n*(k-2))/k = (k+(k/2 - b^n)*(k-2))/k
k^2/2 - kb^(n+1) = k+(k/2 - b^n)*(k-2)
k^2/2 - kb^(n+1) = k + k^2/2 - k - kb^n +2b^n
- kb^(n+1) = - kb^n +2b^n
kb = k-2
b = (k-2)/k
Thus we have L_n = k/2 - ((k-2)/k)^n satisfying the recursion.
But does it satisfy the base case as well? L_0 = k/2 - ((k-2)/k)^0 = k/2 - 1 != 0 and we can see that it does not. So, let's tweak the proposed formula a little to see if that helps.
Let L_n = k/2-a*b^n for some a, b.
The 'a's fall out leaving the same solution for b, so L_n = k/2 - a((k-2)/k)^n.
Solving for a using the known base case (L_0=0), 0 = L_0 = k/2 - a((k-2)/k)^0 = k/2 - a, so a=k/2.
Putting it all together gives L_n = k/2 - k/2((k-2)/k)^n = k/2 * [ 1 - ((k-2)/k)^n ] as the final solution, which satisfies both the recursion and the base case.
Method 2
Suppose k=2. Once one of the switches is turned on, the expected value is always 1, since there is an equal chance of a light being turned off as it is being turned on. Using this fact, we can group pairs of lights for other values of k.
Now suppose k is arbitrary, as per the guidelines of the question. Consider the first two lightbulbs. The probability that neither has been turned on after n toggles is ((k-2)/k)^n. So the probability that at least one has turned on (giving the pair an expected value of 1) is 1 - ((k-2)/k)^n.
In exactly half these circumstances, the first lightbulb is on. This means the expected value for the first bulb is (1 - ((k-2)/k)^n)/2.
Since the first bulb is symmetric with all other bulbs, the expected value for all the bulbs is the sum of each bulb's expected value, or L = E_total = sum(E_i) = k*E_i = k*(1 - ((k-2)/k)^n)/2 = k/2 * (1 - ((k-2)/k)^n), as above.
==========
Notice that the solutions are radically different in both length, method, and the number of assumptions it asks you to believe.
SolarFlare
Those who cling to life die and those who defy death live. -Sun Tzu
cout << endl;
return 0;
}
-
February 27th, 2005, 11:19 PM
#1309
Re: question and answer thread.
Originally Posted by SolarFlare
Suppose there is a row of k lightswitches, each wired to its own lightbulb, and initially off. Someone turns on one of the lightswitches randomly. Then they toggle another lightswitch randomly (if it's the same one as the first one, the light goes off. Otherwise a second light comes on). This process is repeated n times (so that n total toggles are made). What is the expected value for the number of lights that will be on when the process is complete, in terms of n and k?
Suppose k = 2 and n = 2 let the switches be s1, s2
if you toggle s1 twice you have 0 lights on
if you toggle s1 and s2 once each you have 2 lights on
-
February 28th, 2005, 06:43 AM
#1310
Re: question and answer thread.
Originally Posted by Sahir
Suppose k = 2 and n = 2 let the switches be s1, s2
if you toggle s1 twice you have 0 lights on
if you toggle s1 and s2 once each you have 2 lights on
If this is a challenge to my solution, then perhaps the meaning of Expected Value has been misunderstood.
In the instance of k=n=2, there is a 1/2 chance that no lights will be on and a 1/2 chance that both lights will be on, so E = (1/2)*(0) + (1/2)*(2) = 1.
SolarFlare
Those who cling to life die and those who defy death live. -Sun Tzu
cout << endl;
return 0;
}
-
March 13th, 2005, 12:12 AM
#1311
Re: question and answer thread.
hhmm...... okay i think that was is far over my head. I know It is not my turn but
I would like to ask a question any way. I prolly won't be here long enough for
the points to matter.
Code:
Gertrude entered a Boeing 707 (I don't know if this is a real plane or not, it
doesn'tmatter either way.) which seated 300 people, it is full. No one saw
Gertrude get on. Gertrude exited the plane. No one saw Gertrude exit the plane.
Gertrude killed 300 people. How did she do it?
Note: You do NOT need any knowledge about jet liners aside from what you
would learn by 6th grade. Or anything else for that matter. A logic problem not a
technical problem.
It has been a while since i read this last, and the wording may be a little off. I
hope it is close enough that some one could answer it.
Last edited by Sravoff; March 13th, 2005 at 12:13 AM.
Reason: weird
I am me. Just so you know.
-
March 13th, 2005, 09:54 AM
#1312
Re: question and answer thread.
-
March 13th, 2005, 10:18 AM
#1313
Re: question and answer thread.
Originally Posted by Sravoff
hhmm...... okay i think that was is far over my head. I know It is not my turn but
I would like to ask a question any way. I prolly won't be here long enough for
the points to matter.
Code:
Gertrude entered a Boeing 707 (I don't know if this is a real plane or not, it
doesn'tmatter either way.) which seated 300 people, it is full. No one saw
Gertrude get on. Gertrude exited the plane. No one saw Gertrude exit the plane.
Gertrude killed 300 people. How did she do it?
Note: You do NOT need any knowledge about jet liners aside from what you
would learn by 6th grade. Or anything else for that matter. A logic problem not a
technical problem.
It has been a while since i read this last, and the wording may be a little off. I
hope it is close enough that some one could answer it.
Qaueda operative with a parachute?
Either that or it's an odorless and colorless gas of some sort that knocked out the pilot.
-
March 13th, 2005, 10:34 AM
#1314
Re: question and answer thread.
Originally Posted by YourSurrogateGod
knocked out the pilot.
How about everybody
/Hypoxia
-
March 13th, 2005, 11:53 AM
#1315
Re: question and answer thread.
The thing with the gas is not stupid. Maybe the gas or fuelt vault is called Gertrude. Or she is a Re'Tu
-
March 13th, 2005, 07:30 PM
#1316
Re: question and answer thread.
Originally Posted by Mick
How about everybody
/Hypoxia
It was either that or a huge flame wreck . At the very least the pilot would have to go .
[edit]
I take it that it was CO?
/ahh... carbon monoxide... wait a sec!
-
March 13th, 2005, 07:54 PM
#1317
Re: question and answer thread.
Originally Posted by YourSurrogateGod
It was either that or a huge flame wreck . At the very least the pilot would have to go .
[edit]
I take it that it was CO?
/ahh... carbon monoxide... wait a sec!
Loss of cabin pressure.
-
March 13th, 2005, 10:20 PM
#1318
Re: question and answer thread.
Gertrude is a goose that flew through the jet engine.
Verere testudinem! (Fear the turtle)
Once you can accept the universe as matter expanding into nothing that is something, wearing stripes with plaid comes easy. -Albert Einstein
Robots are trying to steal my luggage.
-
March 13th, 2005, 10:38 PM
#1319
Re: question and answer thread.
Goose is to jet engine as apple pie is to ............ ?
Microsoft LVP - Least Valuable Professional
Please rate this post... Pleeeeeeaaassee!!!
-
March 13th, 2005, 11:38 PM
#1320
Re: question and answer thread.
Gertrude is some kind of ariborne virus ?
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|