Probability Question

[CChow]

Suppose you have 50 lightbulbs and 50 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 50 random switches are flipped, what is the expected number of lightbulbs turned on?

 

[chiadam]

Maybe I'm reading it wrong but it starts with all the light bulbs being turned off. You then turn one on, then off again - therefore flipping all 50 switches would turn all 50 light bulbs on.

I think the question is that you randomly flip 50 switches...for example, it could be 50 different switches, or it could be the same switch 50 times.

 

[CChow]

yes randomly flip

 

[pruse]

I saw this question and a bulb went off.

The probability that a given bulb is on is the probability that it was flipped an odd number of times: (\binom{50}{1}0.02^10.98^{49}+\binom{50}{3}0.02^30.98^{47}+\cdots+\binom{50}{49}0.02^{49}0.98^1). This is equal to (\frac{1}{2}[1-(0.98-0.02)^{50}]=\frac{1}{2}(1-0.96^{50})). The answer is then (50\cdot \frac{1}{2}(1-0.96^{50})\approx 21.75).

 

[euroazn]

I saw this question and a bulb went off.

The probability that a given bulb is on is the probability that it was flipped an odd number of times: (\binom{50}{1}0.02^10.98^{49}+\binom{50}{3}0.02^30.98^{47}+\cdots+\binom{50}{49}0.02^{49}0.98^1). This is equal to (\frac{1}{2}[1-(0.98-0.02)^{50}]=\frac{1}{2}(1-0.96^{50})). The answer is then (50\cdot \frac{1}{2}(1-0.96^{50})\approx 21.75).

No go. The events aren't independent

 

[pruse]

No go. The events aren't independent

so?

 

[oldfishdk]

I think it is just a random walk with equal probability that one more light on or one less. So the answer is zero?

 

[chiadam]

I think it is just a random walk with equal probability that one more light on or one less. So the answer is zero?

I am almost certain this is incorrect.

 

[pruse]

Obviously that's incorrect... only if exactly half of all the bulbs are currently on can we say that the probability of one more on is the same as the probability of one more off. Trust me, the answer is about 21.75.

 

[euroazn]

so?

Good point :p

Anyways I ran:

import java.util.*;
class Tester{
public static void main(String[] args){
int sum=0;
for(int test=0;test<500;test++){
boolean[] switches = new boolean[50];
for(int flip=0;flip<50;flip++){
int toFlip=(new Random()).nextInt(50);
switches[toFlip]=!switches[toFlip];
}
for(int count=0;count<50;count++)
if(switches[count])
sum++;
}
System.out.println((double)sum/500.0);
}
}

(*GASP*... Java I know... I was very lazy and used an online IDE, lol)

And got a result equal to peterruse's answer.

 

[stochan]

Let us call (X_n) the number of light bulbs on after (n) switches. Clearly (X_1=1). Find
(E(X_{n+1}|X_n)=(X_n+1)P(A_n) + (X_n-1)(1-P(A_n))) where the event (A_n) means switching an "off" bulb at time (n), hence (P(A_n)=1-\frac{X_n}{50}).
Get (E_{n+1}=\frac{48}{50}E_n+1).

Hence (E_{50}=25\large(1-\large(\frac{48}{50}\right)^{50}\right)\approx 21.752855 )

 

[euroazn]

Let us call (X_n) the number of light bulbs on after (n) switches. Clearly (X_1=1). Find
(E(X_{n+1}|X_n)=(X_n+1)P(A_n) + (X_n-1)(1-P(A_n))) where the event (A_n) means switching an "off" bulb at time (n), hence (P(A_n)=1-\frac{X_n}{50}).
Get (E_{n+1}=\frac{48}{50}E_n+1).

Hence (E_{50}=25\large(1-\large(\frac{48}{50}\right)^{50}\right)\approx 21.752855 )

nice.

 

[maxareo]

Let I_i = 1 if after 50 switches, the ith light bulb is on, and I_i = 0 if the ith is off; then E(N) = sum_{i=1}^50 E(I_i) = 50E(I_i) = 50P(I_i=1), where P(I_i=1) = 0.5 *(1-(24/25)^50), so E(N) = 21.75286.

How can I type formulas here like stochan did?

 

[Jeffrey K.W. Lo]

Nice solution stochan.

Can someone please explain how he got the final equation E50 = 25 * [ 1 - (48/50)^50]? Is it from some kind of known formula? Also, which field of mathematics does this fall into specifically? I am very interested to learn more about it.

Thanks in advance.

 

[Vincent Tan]

Nice solution stochan.

Can someone please explain how he got the final equation E50 = 25 * [ 1 - (48/50)^50]? Is it from some kind of known formula? Also, which field of mathematics does this fall into specifically? I am very interested to learn more about it.

Thanks in advance.

Basic probability theory, in particular, conditional expectation. What is really elegant about this solution is the use of recursion.

 

[Andrzej]

my code in Mathematica:

counts = {};
Do[
  list = Table[x*0, {x, 1, 50}];
  For[i = 1, i <= 50, i++,
   n = RandomInteger[{1, 50}];
   If[list[[n]] == 0, list[[n]] = 1, list[[n]] = 0]];
  AppendTo[counts, Total@list], {k, 1, 1000}];
Print[N@Mean@counts]