CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 88 of 92 FirstFirst ... 387885868788899091 ... LastLast
Results 1,306 to 1,320 of 1367
  1. #1306
    Join Date
    Apr 2003
    Location
    Los Angeles area
    Posts
    776

    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."

  2. #1307
    Join Date
    Aug 2002
    Location
    Kerala
    Posts
    1,183

    Re: question and answer thread.

    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.

  3. #1308
    Join Date
    Sep 2002
    Location
    Philadelphia ***Epoch: Timeless***
    Posts
    560

    Re: question and answer thread.

    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.
    SolarFlare

    Those who cling to life die and those who defy death live. -Sun Tzu

    cout << endl;
    return 0;
    }

  4. #1309
    Join Date
    Aug 2002
    Location
    Kerala
    Posts
    1,183

    Re: question and answer thread.

    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

  5. #1310
    Join Date
    Sep 2002
    Location
    Philadelphia ***Epoch: Timeless***
    Posts
    560

    Re: question and answer thread.

    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.
    SolarFlare

    Those who cling to life die and those who defy death live. -Sun Tzu

    cout << endl;
    return 0;
    }

  6. #1311
    Join Date
    Nov 2004
    Posts
    167

    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.

  7. #1312
    Join Date
    Oct 2002
    Location
    Timisoara, Romania
    Posts
    14,360

    Re: question and answer thread.

    Gertrude is a rocket!
    Marius Bancila
    Home Page
    My CodeGuru articles

    I do not offer technical support via PM or e-mail. Please use vbBulletin codes.

  8. #1313
    Join Date
    Apr 2004
    Location
    In the back seat of New Horizons.
    Posts
    1,238

    Re: question and answer thread.

    Quote 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.
    Here are the rules, you must obey them or the gender bender will get you.

    And if you ever think of posting without code-tags, the evil monkey will come after you.

  9. #1314
    Join Date
    Sep 2002
    Location
    Maryland - Fear The Turtle!
    Posts
    7,537

    Re: question and answer thread.

    Quote Originally Posted by YourSurrogateGod
    knocked out the pilot.
    How about everybody

    /Hypoxia

  10. #1315
    Join Date
    Mar 2004
    Location
    (Upper-) Austria
    Posts
    2,899

    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
    I am not offering technical guidiance via email or IM
    Come on share your photo with us! CG members photo album!
    Use the Code Tags!

  11. #1316
    Join Date
    Apr 2004
    Location
    In the back seat of New Horizons.
    Posts
    1,238

    Re: question and answer thread.

    Quote 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!
    Here are the rules, you must obey them or the gender bender will get you.

    And if you ever think of posting without code-tags, the evil monkey will come after you.

  12. #1317
    Join Date
    Sep 2002
    Location
    Maryland - Fear The Turtle!
    Posts
    7,537

    Re: question and answer thread.

    Quote 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.

  13. #1318
    Join Date
    Apr 2002
    Location
    Michigan, USA
    Posts
    869

    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.

  14. #1319
    Join Date
    Aug 2001
    Location
    Sydney, Australia
    Posts
    813

    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!!!

  15. #1320
    Join Date
    Aug 2002
    Location
    Kerala
    Posts
    1,183

    Re: question and answer thread.

    Gertrude is some kind of ariborne virus ?

Page 88 of 92 FirstFirst ... 387885868788899091 ... LastLast

Posting Permissions

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





Click Here to Expand Forum to Full Width

Featured