CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Member +  Join Date
Apr 2003
Location
Los Angeles area
Posts
776

Yes, inquriing minds would like to see the answer to this.  Reply With Quote 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.   Reply With Quote 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.  Reply With Quote 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  Reply With Quote 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.  Reply With Quote

6. Member Join Date
Nov 2004
Posts
167

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  Reply With Quote

Gertrude is a rocket!  Reply With Quote

8. Senior Member   Join Date
Apr 2004
Location
In the back seat of New Horizons.
Posts
1,238 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.  Reply With Quote Originally Posted by YourSurrogateGod
knocked out the pilot.
How about everybody /Hypoxia  Reply With Quote

The thing with the gas is not stupid. Maybe the gas or fuelt vault is called Gertrude. Or she is a Re'Tu  Reply With Quote

11. Senior Member   Join Date
Apr 2004
Location
In the back seat of New Horizons.
Posts
1,238 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 .

I take it that it was CO?

/ahh... carbon monoxide... wait a sec!  Reply With Quote Originally Posted by YourSurrogateGod
It was either that or a huge flame wreck . At the very least the pilot would have to go .

I take it that it was CO?

/ahh... carbon monoxide... wait a sec!
Loss of cabin pressure.  Reply With Quote

Gertrude is a goose that flew through the jet engine.  Reply With Quote

Goose is to jet engine as apple pie is to ............ ?  Reply With Quote

Gertrude is some kind of ariborne virus ?  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
• 