Welcome to our community

Be a part of something great, join today!

Expected number of light bulbs on

oyth94

Member
Jun 2, 2013
33
There are 50 light bulbs in a room each with its own switch. If a light bulb is on, Dick turns it off and if it is off , he turns it on. Initially all light bulbs are off . After 50 flips and assuming that Dick chooses switches to be flipped randomly, what is the expected number of light bulbs on in the room rounded to the nearest natural number?

To be honest, i tried many times but i can;t seem to arrive at an answer. i am stuck. any help would be appreciated!!!

so i have started with this:
Let Ei 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(Ei) and let Xi be the indicator random variable for Ei. Then E[Xi]=Pr(Ei). Now, let X be the total number of bulbs on after 50 flips. X=∑Xi, so E[X]=∑E[Xi]=n⋅Pr(Ei).
 
Last edited:

chisigma

Well-known member
Feb 13, 2012
1,704
There are 50 light bulbs in a room each with its own switch. If a light bulb is on, Dick turns it off and if it is off, he turns it on. Initially all light bulbs are off. After 50 flips and assuming that Dick chooses switches to be flipped randomly, what is the expected number of light bulbs on in the room rounded to the nearest natural number?

To be honest, i tried many times but i can;t seem to arrive at an answer. i am stuck. any help would be appreciated!!!

so i have started with this:
Let Ei 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(Ei) and let Xi be the indicator random variable for Ei. Then E[Xi]=Pr(Ei). Now, let X be the total number of bulbs on after 50 flips. X=∑Xi, so E[X]=∑E[Xi]=n⋅Pr(Ei).
The core of the problem is the meaning of 'Dick chooses switches to be flipped randomly'... if it means that any bulb has probability 1/2 to be switched by Dick at any iteration it is evident that at the end of each iteration the expected number of switched on bulbs is 25...

Kind regards

$\chi$ $\sigma$
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,725
There are 50 light bulbs in a room each with its own switch. If a light bulb is on, Dick turns it off and if it is off, he turns it on. Initially all light bulbs are off. After 50 flips and assuming that Dick chooses switches to be flipped randomly, what is the expected number of light bulbs on in the room rounded to the nearest natural number?
Fascinating problem! I have wasted half my Sunday morning on it. (Coffee) (Yawn)

Let's generalise it a bit, to the case where there are $k$ switches. Denote by $E(k,n)$ the expected number of lit bulbs after $n$ random flips, given that initially all light bulbs were off. I found $50$ much too large a number to work with, so I did some experiments with smaller numbers. For $k=4$, I found that the values of $E(4,n)$, for $n=1,2,3,4,5,6$ are $$1,\ \frac32,\ \frac74,\ \frac{15}8,\ \frac{31}{16}, \frac{63}{32},$$ which makes it seem likely that $E(4,n) = \dfrac{2^n-1}{2^{n-1}}$.

I then tried $k=6$ and found something even more interesting: for $n=1,2,3,4$, the values of $E(6,n)$ are $$1,\ \frac53,\ \frac{19}9,\ \frac{65}{27},$$ which very strongly suggests that $E(6,n) = \dfrac{3^n-2^n}{3^{n-1}}.$

If so, then it seems inevitable that the general formula must be $\boxed{E(2k,n) = \dfrac{k^n - (k-1)^n}{k^{n-1}}}.$

I'm not prepared to put money on it, but I'm 99% sure that $$E(50,50) = \dfrac{25^{50} - 24^{50}}{25^{49}} = 25 - 24\Bigl(\frac{24}{25}\Bigr)^{\!49} \approx 21.75.$$

Now it's time for Sunday lunch, so I'll leave it to others to see if those results can be proved.
 

oyth94

Member
Jun 2, 2013
33
Fascinating problem! I have wasted half my Sunday morning on it. (Coffee) (Yawn)

Let's generalise it a bit, to the case where there are $k$ switches. Denote by $E(k,n)$ the expected number of lit bulbs after $n$ random flips, given that initially all light bulbs were off. I found $50$ much too large a number to work with, so I did some experiments with smaller numbers. For $k=4$, I found that the values of $E(4,n)$, for $n=1,2,3,4,5,6$ are $$1,\ \frac32,\ \frac74,\ \frac{15}8,\ \frac{31}{16}, \frac{63}{32},$$ which makes it seem likely that $E(4,n) = \dfrac{2^n-1}{2^{n-1}}$.

I then tried $k=6$ and found something even more interesting: for $n=1,2,3,4$, the values of $E(6,n)$ are $$1,\ \frac53,\ \frac{19}9,\ \frac{65}{27},$$ which very strongly suggests that $E(6,n) = \dfrac{3^n-2^n}{3^{n-1}}.$

If so, then it seems inevitable that the general formula must be $\boxed{E(2k,n) = \dfrac{k^n - (k-1)^n}{k^{n-1}}}.$

I'm not prepared to put money on it, but I'm 99% sure that $$E(50,50) = \dfrac{25^{50} - 24^{50}}{25^{49}} = 25 - 24\Bigl(\frac{24}{25}\Bigr)^{\!49} \approx 21.75.$$

Now it's time for Sunday lunch, so I'll leave it to others to see if those results can be proved.
Thank you so much! I arrived with the same answer but I used either Poisson or Binomial. But my approach I didn't involve expected value...which I should...
 

zzephod

Well-known member
Feb 3, 2013
134
Fascinating problem! I have wasted half my Sunday morning on it. (Coffee) (Yawn)

Let's generalise it a bit, to the case where there are $k$ switches. Denote by $E(k,n)$ the expected number of lit bulbs after $n$ random flips, given that initially all light bulbs were off. I found $50$ much too large a number to work with, so I did some experiments with smaller numbers. For $k=4$, I found that the values of $E(4,n)$, for $n=1,2,3,4,5,6$ are $$1,\ \frac32,\ \frac74,\ \frac{15}8,\ \frac{31}{16}, \frac{63}{32},$$ which makes it seem likely that $E(4,n) = \dfrac{2^n-1}{2^{n-1}}$.

I then tried $k=6$ and found something even more interesting: for $n=1,2,3,4$, the values of $E(6,n)$ are $$1,\ \frac53,\ \frac{19}9,\ \frac{65}{27},$$ which very strongly suggests that $E(6,n) = \dfrac{3^n-2^n}{3^{n-1}}.$

If so, then it seems inevitable that the general formula must be $\boxed{E(2k,n) = \dfrac{k^n - (k-1)^n}{k^{n-1}}}.$

I'm not prepared to put money on it, but I'm 99% sure that $$E(50,50) = \dfrac{25^{50} - 24^{50}}{25^{49}} = 25 - 24\Bigl(\frac{24}{25}\Bigr)^{\!49} \approx 21.75.$$

Now it's time for Sunday lunch, so I'll leave it to others to see if those results can be proved.
I can report that simulation gives the mean number off after 50 flips of the 50 switchs is 21.74 with a standard error ~0.034

(another exercise on my Python learning curve)

.
 
Last edited:

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,725
I now see how to prove the formula for $E(2k,n)$, and it's really quite easy. When the $(n+1)$th switch is flipped, the probability that it is already on is $\dfrac{E(2k,n)}{2k}$, in which case the flip turns it off, and the number of "on" switches is reduced by $1$. Likewise, the probability that the $(n+1)$th switch is off is $\dfrac{2k-E(2k,n)}{2k}$, in which case the flip turns it on, and the number of "on" swiches is increased by $1$. Therefore $$E(2k,n+1) = \frac{E(2k,n)}{2k}(E(2k,n)-1) + \frac{2k-E(2k,n)}{2k}(E(2k,n)+1) = \frac{(k-1)E(2k,n) + k}k.$$ Now assume as an inductive hypothesis that $E(2k,n) = \dfrac{k^n-(k-1)^n}{k^{n-1}}$. Then $$E(2k,n+1) = \frac{(k-1)E(2k,n) + k}k = \frac{(k-1)k^n-(k-1)^{n+1} + k^n}{k^n} = \frac{k^{n+1} - (k-1)^{n+1}}{k^n},$$ which completes the inductive step. The base case $E(2k,1) = 1$ is easy to check, so the result is proved.