Imagine a room with 50 light bulbs all connected to separate switches. Switches have two positions ON and OFF which controls the light bulb's state in a similar way. All switches are initially OFF. Now a restless genie is playing with the switches inside the room. Genie fiddles with any of the switches at random and toggles its state. This, the genie does 50 times and then leaves the room. Now the question is - how many light bulbs are ON on an average at the end of the genie episode?
I saw this question in a Quantitative finance discussion board.
I will sketch my solution to the problem and suggest some of properties and generalizations of the question.
Let us label the task of genie randomly playing with switches as a trial. The question asks us to find the average number of bulbs with an odd number of switch toggles after sufficiently large number of trials. (First (odd) toggle of the switch changes its state from OFF to ON, Second (even) toggle changes from ON to OFF and so on..) Let us concentrate on an arbitrary switch and corresponding light bulb. There is 1/50 chance that it will be toggled and 49/50 that it is left untouched in a single instance of an arbitrary trial. This chance is independent of the number of instances and number of trials, and also on what is happening to the other light bulbs. (I had earlier though that a single light bulb cannot be analyzed in isolation as its state at the end of a trial is thought to be dependent on what states other light bulbs are. That is a light bulb cannot be ON say 35 times, if another light bulb is ON more than 15 times in a very very freakish trial. But the average case allows us to disregard this dependence in a single trial and to find the distribution of trials of a single light bulb spread over multiple trials. This independence over large number of trials allows us to focus on state of a single light bulb.
Note that in this solution we seek the probability distribution of number of toggles of a single light bulb spread over multiple trials. Other equivalent method (which was discussed in the forum thread) is non intuitive. Here (in my reasoning) we intuitively think of what happens to a light bulb in many trials (average case calculation) and find the probability of its states.
The process followed by the single light bulb is the binomial one (as discussed - independence criterion over multiple trials allows us to model with binomial distribution) with p=49/50 (prob of no toggle) and q=1/50 (prob of toggle) and n=50. Now the question is to find the probability of this light bulb to have odd number of switch toggles at the end of a trial. This is the sum of probabilities of 1 toggle, 3 toggle, 5 toggle etc in multiple trials. Let P(n) denote probability of n toggles. Hence Podd = P(1)+P(3)+P(5)+...+P(49)
Podd = C(50,1)q^1p^49+C(50,3)q^3p^47+.C(50,5)q^5p^45+...+C(50,49)q^49p^1
This is calculated as 1/2*((p+q)^50-(p-q)^50), where p and q are as defined.
Podd = 1/2*(1-(48/50)^50) = 0.43505710323898
Now after sufficiently large number of trials, an arbitrary light bulb is ON with probability Podd. Now the distribution ON and OFF light bulbs in each trial is again a binomial distribution. Expected number of ON light bulbs is 50*Podd = 50*0.43505710323898 = 21.7528551619
We find that on average, we expect only less than half light bulbs to be ON after a trials. This may initially seem counter intuitive - How can less than 25 light bulbs be on if I randomly twiddle with switches 50 times in a 50 bulb array? But solution is found to be correct with a simple computer simulation, with the sample code pasted below.
#include
#include
int IMAX = 50; //Global definition of Random MAX to be used in this program
int IMIN = 0; //Global definition of Random MIN to be used in this program
int main()
{
int bulb[50],i,j,k,m; //All int variables including index are defined
double l=0,n=0; //Variables for calculation of probability
{ //We run the trial 1000 times
for(j=0;j<1000;j++) { for(i=0;i<50;i++) {bulb[i]=0;} //initialize array before every trial
for(i=0;i<50;i++) {k = IMIN+rand()%(IMAX-IMIN); bulb[k]++;} //random switching simulation
for(i=0;i<50;i++) { if((bulb[i]%2)!=0) {l++;}}
}
printf("%lf",l/1000);
}
}
Now to generalize the question with an infinitely large array of light bulbs (or countable infinity of anything), we find that the Podd = (e^2-1)/e^2
What of the outcome of twiddling with a fixed array an very large number of time, say a 50 array with 1000 random switchings? What is the solution in the limit case? I give this problem to the reader who may find it trivial to solve in the above reasoning.
Hari S Warrier
I saw this question in a Quantitative finance discussion board.
I will sketch my solution to the problem and suggest some of properties and generalizations of the question.
Let us label the task of genie randomly playing with switches as a trial. The question asks us to find the average number of bulbs with an odd number of switch toggles after sufficiently large number of trials. (First (odd) toggle of the switch changes its state from OFF to ON, Second (even) toggle changes from ON to OFF and so on..) Let us concentrate on an arbitrary switch and corresponding light bulb. There is 1/50 chance that it will be toggled and 49/50 that it is left untouched in a single instance of an arbitrary trial. This chance is independent of the number of instances and number of trials, and also on what is happening to the other light bulbs. (I had earlier though that a single light bulb cannot be analyzed in isolation as its state at the end of a trial is thought to be dependent on what states other light bulbs are. That is a light bulb cannot be ON say 35 times, if another light bulb is ON more than 15 times in a very very freakish trial. But the average case allows us to disregard this dependence in a single trial and to find the distribution of trials of a single light bulb spread over multiple trials. This independence over large number of trials allows us to focus on state of a single light bulb.
Note that in this solution we seek the probability distribution of number of toggles of a single light bulb spread over multiple trials. Other equivalent method (which was discussed in the forum thread) is non intuitive. Here (in my reasoning) we intuitively think of what happens to a light bulb in many trials (average case calculation) and find the probability of its states.
The process followed by the single light bulb is the binomial one (as discussed - independence criterion over multiple trials allows us to model with binomial distribution) with p=49/50 (prob of no toggle) and q=1/50 (prob of toggle) and n=50. Now the question is to find the probability of this light bulb to have odd number of switch toggles at the end of a trial. This is the sum of probabilities of 1 toggle, 3 toggle, 5 toggle etc in multiple trials. Let P(n) denote probability of n toggles. Hence Podd = P(1)+P(3)+P(5)+...+P(49)
Podd = C(50,1)q^1p^49+C(50,3)q^3p^47+.C(50,5)q^5p^45+...+C(50,49)q^49p^1
This is calculated as 1/2*((p+q)^50-(p-q)^50), where p and q are as defined.
Podd = 1/2*(1-(48/50)^50) = 0.43505710323898
Now after sufficiently large number of trials, an arbitrary light bulb is ON with probability Podd. Now the distribution ON and OFF light bulbs in each trial is again a binomial distribution. Expected number of ON light bulbs is 50*Podd = 50*0.43505710323898 = 21.7528551619
We find that on average, we expect only less than half light bulbs to be ON after a trials. This may initially seem counter intuitive - How can less than 25 light bulbs be on if I randomly twiddle with switches 50 times in a 50 bulb array? But solution is found to be correct with a simple computer simulation, with the sample code pasted below.
#include
#include
int IMAX = 50; //Global definition of Random MAX to be used in this program
int IMIN = 0; //Global definition of Random MIN to be used in this program
int main()
{
int bulb[50],i,j,k,m; //All int variables including index are defined
double l=0,n=0; //Variables for calculation of probability
{ //We run the trial 1000 times
for(j=0;j<1000;j++) { for(i=0;i<50;i++) {bulb[i]=0;} //initialize array before every trial
for(i=0;i<50;i++) {k = IMIN+rand()%(IMAX-IMIN); bulb[k]++;} //random switching simulation
for(i=0;i<50;i++) { if((bulb[i]%2)!=0) {l++;}}
}
printf("%lf",l/1000);
}
}
Now to generalize the question with an infinitely large array of light bulbs (or countable infinity of anything), we find that the Podd = (e^2-1)/e^2
What of the outcome of twiddling with a fixed array an very large number of time, say a 50 array with 1000 random switchings? What is the solution in the limit case? I give this problem to the reader who may find it trivial to solve in the above reasoning.
Hari S Warrier
