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?

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.

ReplyDeleteSo 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)]