Expected number of light bulbs on

There are 50 light bulbs in a room each with its own switch.

Initially all light bulbs are off.

Dick follows the following procedure 50 times:

He randomly selects a light bulb and flips the switch, turning it on if it is off and off if it is on.

What is the expected number of light bulbs on in the room after 50 flips, rounded to the nearest natural number?

-
Some (hopefully) useful figures: probability a given bulb is never flipped – 36.4%. Flipped once – 37.2%. Flipped twice – 18.6%. 3 times – 6.07%. 4 times – 1.45%. 5 or more – .32% (negligible). –  Omnomnomnom Jul 20 '13 at 22:35

$\newcommand{E}{\mathbf{E}}$ Let $E_i$ be the event that bulb $i$ is on after $50$ flips. This is the case if switch $i$ is chosen an odd number of times. Compute $\Pr(E_i)$ and let $X_i$ be the indicator random variable for $E_i$. Then $\E[X_i] = \Pr(E_i)$. Now, let $X$ be the total number of bulbs on after $50$ flips. $X=\sum_{i=1}^{50}X_i$, so $\E[X] = \sum_{i=1}^{50} \E[X_i] = 50 \cdot \Pr(E_i)$. So you just need to compute the probability that a given switch is flipped an odd number of times in 50 flips.

One way to compute $\Pr(E_i)$ is as follows. Let $P_k$ be the probability that switch $i$ is flipped an odd number of times in the first $k$ flips. Let $p = 1/50$. Then $P_0 = 0$, and $P_k = p(1-P_{k-1}) + (1-p)P_{k-1}$ for any $k>0$. You can compute $P_{50}$ by repeatedly applying this recurrence, which gives you the value of $\Pr(E_i)$.

-

The probabilities that a given bulb is flipped $0$, $2$, or $4$ times are $$\binom{50}{0}\left(\frac{1}{50}\right)^{0}\left(\frac{49}{50}\right)^{50}=.364\\ \binom{50}{2}\left(\frac{1}{50}\right)^{2}\left(\frac{49}{50}\right)^{48}=.186\\ \binom{50}{4}\left(\frac{1}{50}\right)^{4}\left(\frac{49}{50}\right)^{46}=.0145\\$$

Therefore, the probability that a given bulb flipped an even number of times is approximately $$.364+.186+.0145 = .565$$ Since the probability that a given bulb will be flipped any more than $5$ times is so low that it only negligibly contributes to the expectation.

Thus, we can expect $0.565\cdot50\approx 28\,$ bulbs to have been flipped an even number of times. Thus, the expectation is that $28\,$ bulbs will be off, and the remaining $22$ will be on.

The full computation tells you that we expect this many bulbs to be off at the end of the experiment. Again, the answer is that (to the nearest integer) $22$ bulbs should be on.

-
If $N$ ~ Bin(50, 1/2), $P${$N$ is even} = 1/2. One can calculate this with transforms. –  Stephen Herschkorn Jul 20 '13 at 23:32
@StephenHerschkorn I'll have to take your word for that one, and I'd be interested to see how one "calculates this with transforms". For this problem, however, if $N$ is the number of flips of a given switch, $N\sim\text{Bin}(50,1/50)$ –  Omnomnomnom Jul 21 '13 at 1:42
I don't understand what you are saying "calculate this with transforms".. –  oyth94 Jul 21 '13 at 1:54
Oops, my bad. Bin(50, 1/50) is correct. See my comment below my answer to explain what I mean by transforms. –  Stephen Herschkorn Jul 21 '13 at 4:00

Warning: check for errors.

The probability that a given switch (of $n$ switches) will be flipped an odd number of times in $k$ turns is given by \begin{gather*} f(0) = 0 \\ f(k+1) = \frac{n-1}{n}f(k)+\frac 1 n (1-f(k)) \end{gather*}

Then $$f(k+1)=\frac 1 n + \frac{n-2}{n}f(k)$$

The steady state for this difference equation is clearly $\frac 1 2$, so we can simplify it to $$f(k+1)-\frac 1 2 = \frac{n-2}{n}(f(k)-\tfrac 1 2)$$

The solution is $f(k) - \frac 1 2 = -\frac 1 2 \left(\frac{n-2}{n}\right)^{k}$

So $$f(n) = \frac 1 2 - \frac 1 2 \left(1-\frac 2 n\right)^n.$$

This last form should look familiar. If $n$ is large, $$f(n)\approx \frac 1 2 - \frac 1 2 e^{-2}\approx 0.432.$$

-

As noted above, the expected value of a sum is the sum of the expected values. One can determine the probability a random variable is odd via one if its transforms (e.g., its moment generating function).

I would give more detail if I didn't think this is homework. If it is not and you want more information, ask in comments and I will respond there. If it is, you should have noted so in your tags.

I get $25[1 - (24/25)^{50}] \approx 22$ as an answer. (If I didn't have a calculator, I don't know if I would have been able to give the approximation.)

-
This question was on my test. I had trouble answering this one. How did you get 25? What approach did you take? My TA said he got 28 off and 22 bulbs on.. –  oyth94 Jul 21 '13 at 1:52
22 is correct. Edited my answer. –  Stephen Herschkorn Jul 21 '13 at 3:47
Let $I_i$ indicate that the ith switch is flipped an odd number of time. As note above, the desired expected value is $50EI$. $I = [1 - (-1)^N] / 2$, where $N$ ~ Bin(50, 1/50). Then $EI = [1 - \pi(-1)]/2$, where $\pi(z) = Ez^N = (49/50 +z/50)^{50}$ is the probability generating function for $N$. –  Stephen Herschkorn Jul 21 '13 at 3:57

Consider a single switch. The total number of times the switch is flipped is a Binomial random variable with n = 50, p = 1/50. We would like to know the probability that the switch is flipped an odd number of times. So let's say the switch is flipped i times. Note that

$(49/50 + x/50)^{50} = \sum_{i=0}^{50} \binom{50}{i} (x/50)^i (49/50)^{50-i}$ and $(49/50 - x/50)^{50} = \sum_{i=0}^{50} (-1)^i \binom{50}{i} (x/50)^i (49/50)^{50-i}$

Subtracting the second equation from the first, $(49/50 + x/50)^{50} - (49/50 - x/50)^{50} = 2 \sum_{i \; odd} \binom{50}{i} (x/50)^i (49/50)^{50-i}$

Letting x=1, we have

$(49/50 + 1/50)^{50} - (49/50 - 1/50)^{50} = 2 \Pr(\text{i is odd})$

Whence $\Pr(\text{i is odd}) \approx 0.43506$ and the expected number of switches on is

$50 \cdot \Pr(\text{i is odd}) \approx 21.75$

-