Monday 13 August 2012

Bulbs & Switches

Suppose you have 'n' lightbulbs and 'n' switches that correspond to each of the lightbulbs. Initially, all the lightbulbs are turned off. After you flip a switch, the corresponding lightbulb turns on. If you flip the same switch again, the lightbulb turns off. Each switch corresponds to only 1 lightbulb and vice versa. After 'k' random switches are flipped, what is the expected number of lightbulbs turned on?

1 comment:

  1. Let after l operations X_l be the number of lights that are on .So in the next step either we switch on an "off" light or switch off an "on" light.
    So E(X_l+1|X_l)=(X_l + 1)(1-X_l/n) + (X_l-1)(X_l/n).

    so E(X_l+1)=(n-2)/n E(X_l) + 1;E(X_1)=1;
    Solving this recursion :
    E(X_k+1)=(n/2)[1-(n-2/n)^(k+1)]

    ReplyDelete