Lightbulbs in a circle — expected number of bulbs with itself and next one on?

Question

I attempted the following Tripos question a while ago:

A collection of $n$ lightbulbs are arranged in a circle. Each bulb is on independently with probability $p$. Let $X$ be the number of bulbs such that both that bulb and the next bulb clockwise are on.

i) Find $\mathbb{E}(X)$ and $\text{Var}(X)$.

Let $B$ be the event that there is at least one pair of adjacent bulbs that are both on.

ii) Use Markov’s inequality to show that if $p=n^{-0.6}$ then $\mathbb{P}(B)\to0$ as $n\to\infty$. Use Chebyshev’s inequality to show that if $p=n^{-0.4}$ then $\mathbb{P}(B)\to1$ as $n\to\infty$.

For part i), I get that the expected number of bulbs on is just $np$. However, how do we deal with $X$ in this case? Is it just $np^2$ still by linearity of expectation, or am I overcounting around where the $n$th and $1$st bulb are connected? Is the probability I should consider $p^2$ also ii)?

Answer 1

Yes, the probability that a bulb and its clockwise neighbor are both on is $p^2$. By linearity the expected number of pairs is then $np^2$. For ii as well, the probability of a given pair being on is $p^2$. For both, plug in the given value of $p$ and observe the behavior as $n$ gets large.

Answer 2

Just to stress: Variance is quite a bit harder than Expectation, because you can't ignore the dependence.

Sketch:

There are $n$ consecutive pairs. Let $X_i$ be the indicator variable for the $i^{th}$ pair. Thus, $X_i=1$ if bulbs $b_i, b_{i+1}$ are both on and $X_i=0$ otherwise. Clearly $E[X_i]=p^2$ for all $i$. Then, by linearity we get $$E[X]=E\left[ \sum X_i\right]=\sum E[X_i]=np^2$$

What about variance? Well we start with $$\text {Var} [X]=E[X^2]-E[X]^2$$ We know $E[X]^2$ of course. We then compute $$X^2=(X_1+\cdots X_n)^2=(X_1^2+\cdots X_n^2)+ 2\left(\sum_{i< j} X_iX_j\right)$$

We remark that $X_i^2=X_i$. By linearity we quickly get down to trying to compute $E[X_iX_j]$. Now we see that there are two cases. If $j=i+1$ then $E[X_iX_{i+1}]=p^3$. Otherwise $E[X_iX_j]=p^4$.

Now you just have to put the terms together.

Note: because the algebra is a bit messy I suggest working it out explicitly for small $n$ so you have something to test against.

Answer 3

I think it's easier if you use the hidden variables (the individual bulbs) rather than the visible variables (the pairs of adjacent bulbs) because the former are independent. Number the bulbs $0$ to $n-1$ $\pmod{n}$ so that bulb $n$ is actually bulb $0$. Let $$Y_i=\begin{cases}0&\text{if bulb }i\text{ is off}\\ 1&\text{if bulb }i\text{ is on}\end{cases}$$ And $E(Y_i)=E(Y_i^2)=p$. Then $X_i=Y_iY_{i+1}$ so $$E(X)=\sum_{i=0}^{n-1}E(X_i)=\sum_{i=0}^{n-1}E(Y_iY_{i+1})=\sum_{i=0}^{n-1}E(Y_i)E(Y_{i+1})=\sum_{i=0}^{n-1}p^2=np^2$$ $$E(X^2)=\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}E(Y_iY_{i+1}Y_jY_{j+1})$$ Where $$E(Y_iY_{i+1}Y_jY_{j+1})=\begin{cases}E(Y_iY_{i+1}^2Y_{i+2})=p^3&\text{if }j=i+1\\ E(Y_i^2Y_{i+1}^2)=p^2&\text{if }j=i\\ E(Y_{i-1}Y_i^2Y_{i+1})=p^3&\text{if }j=i-1\\ E(Y_iY_{i+1}Y_{i+2}Y_{i+3})=p^4&\text{otherwise}\end{cases}$$ Thus $E(X^2)=n\left(p^3+p^2+p^3+(n-3)p^4\right)$ and $$\operatorname{var}(X)=E(X^2)-\left(E(X)\right)^2=n(p^2+2p^3-3p^4)=np^2(1-p)(3p+1)$$ If $p=n^{-0.6}$ then by Markov's inequality, $P(X\ge1)\le E(X)/1\le n^{-0.2}\rightarrow0$ as $n\rightarrow\infty$. If $p=n^{-0.4}$ then by Chebyshev's inequality, $P(X<1)<P(|X-\mu|>k\sigma)\le\frac1{k^2}$. For this we need $$\begin{align}\frac12n^{0.2}&<n^{0.2}-1=np^2-1=\mu-1=k\sigma\\ &=kp\sqrt{n(1+2p-3p^2)}=kn^{0.1}\sqrt{1+2p-3p^2}<kn^{0.1}\end{align}$$ So the critical point happens when $k>n^{0.1}/2$ so $$P(X<1)<\frac1{k^2}<\left(\frac2{n^{0.1}}\right)^2=\frac4{n^{0.2}}\rightarrow0$$ As $n\rightarrow\infty$.