Reliability of a loop of seven bulbs that will stay on as long as no two adjacent lamps fail

Question

I'm an engineer and I know probability and combinatorics reasonably well, but this problem has me stumped.

I have tried approaching the problem as a 7-bit binary string, then joining the ends to make a loop.

I've seen a solution that considers the general case of $n$ bulbs. It begins by snipping the loop into a string and computing the number of $k$-bulb failures. It sets up this recurrence, which seems incorrect to me:

${n \choose k}$ = ${n-2 \choose k-1}$ + ${n-1 \choose k}$

I know that this holds: ${n \choose k}$ = ${n-1 \choose k-1}$ + ${n-1 \choose k}$.

That's where I get stumped and can't continue.

Thank you in advance for the help.

Answer 1

I will offer a very simple (i.e. inelegant) solution that does not generalize well, but that is easy to understand, for the specific case of $7$ lamps, looped together.

For simplicity, I am assuming that the probability that a specific lamp is good is $p$, that the probability that a specific lamp is bad is $q = (1 - p)$, that the $p,q$ constants apply to each of the lamps, and that the probability of any lamp being good is independent of any other lamp being good.

In effect, you have the lamps seated at a round table in positions 1,2,3,4,5,6,7, where 7 is right next to 1. My approach to exploring having no consecutive bad lamps will be to examine the mutually exclusive cases of $0$ bad lamps, $1$ bad lamp, $2$ bad lamps, or $3$ bad lamps.

Note that $4$ or more bad lamps can be rejected, since this would compel two consecutive bad lamps.

I will let the partial sums be denoted as $~P_k ~: ~k \in \{0,1,2,3\}$, where $P_k$ is the partial sum under the assumption that $k$ of the lamps are bad.

Clearly, if $k=0$, you are automatically satisfied, so

$$P_0 = p^7.$$

Similarly, if $k = 1,$ you also can't have consecutive bad lamps. So,

$$P_1 = \binom{7}{1}p^6q = 7p^6q.$$

For $k=2$, things get complicated. If you select any two lamps, arbitrarily, you are looking at a probability of $p^5q^2.$ The issue is, how many of the $~\displaystyle\binom{7}{2} = 21~$ ways of selecting the two bad lamps are unsatisfying. Answer: $(7)$ :

$(1,2), (2,3), \cdots, (6,7), (7,1)$.

Therefore,

$$P_2 = \left[\binom{7}{2} - 7\right] p^5q^2 = 14p^5q^2.$$

---

The enumeration of $P_3$ is similar. If you have $(3)$ bad lamps, out of the $~\displaystyle \binom{7}{3} = 35~$ ways of selecting the bad lamps, the only satisfying ways of selecting them are

$(1,3,5), (1,3,6), (1,4,6), (2,4,6), (2,4,7), (2,5,7), (3,5,7).$

Therefore,

$$P_3 = 7 p^4q^3.$$

---

Putting this all together,

the overall probability of having satisfying lamps is

$$P_0 + P_1 + P_2 + P_3$$

$$= p^7 + 7p^6q + 14p^5q^2 + 7p^4q^3.$$

---

Note that I gave a very inelegant analysis that does not generalize well. This is the specific answer to the specific posted question. If you (the OP - i.e. original poster) need a more elegant approach that generalizes well, leave a comment, following my answer, and I will provide a (complicated) general approach.

Taking your posting at face value, the answer given is a good answer to provide to an Engineer, rather than to a Mathematician.

Answer 2

A recursive solution is as follows. Let $P_L(n)$ be the probability of failure in a loop of $n$ bulbs and $P_S(n)$ the probability of failure in a string of $n$ bulbs. Then $$P_L(n)=pP_S(n-1)\mbox{ [bulb 1 survives]}$$ $$+qp^2P_S(n-3) \mbox{ [bulb 1 fails but bulbs 2 and n survive]}$$ $$+q(1-p^2) \mbox{ [bulb 1 and at least one of 2 and n fail]}.$$ and $$P_S(n)=q^2 \mbox{ [bulbs 1 and 2 fail]}$$ $$+pP_S(n-1) \mbox{ [bulb 1 survives]}$$ $$+qpP_S(n-2) \mbox{ [bulb 1 fails but bulb 2 survives]}.$$ This reproduces the solution of @user2661923 for $n=7$.

$P_S(1)=0$ and $P_S(2)=q^2$, so $P_S(3)=q^2(1+p)$, $P_S(4)=q^2(1+2p)$, $P_S(5)=q^2(1+2p+2p^2-p^3)$,$P_S(6)=q^2(1+2p+3p^2-p^4)$ so $$P_L(7)=q^2(1+2p+3p^2+4p^3-2p^4-p^5)=1-p^4[p^3-7p+7]$$

Answer 3

The probability of having no bulb fail is $p^7$. Otherwise (if there is at least one failed bulb), the number of ways to select $r > 0$ out of $n$ objects in a circular arrangement with no two adjacent is $$\frac{n}{r}\binom{n-r-1}{r-1} \tag{*}$$ So the probability that $7$ bulbs arranged in a circle will have no two adjacent bulbs fail is $$p^7 + \sum_{r=1}^3 \frac{7}{r}\binom{7-r-1}{r-1} q^r p^{7-r}$$ where the probability that a bulb fails is $q$, and $p=1-q$.

To show $(*)$, we first consider the number of ways to select integers $a_1, a_2, \dots ,a_r$ from the set $\{1,2, \dots ,n\}$ with no two adjacent. For the choices to be non-adjacent, we must have $1 \le a_1$, $a_1 < a_2-1$, $a_2 < a_3-1$, $a_3 < a_4-1$, ..., $a_{r-1} < a_r -1$, and $a_r \le n$. An equivalent set of inequalities is $$1 \le a_1 < a_2-1 < a_3-2 < a_4-3 < \dots < a_r-r+1 \le n-r+1$$ So we may equivalently pick the values $ a_1 , a_2-1 , a_3-2 , a_4-3 , \dots , a_r-r+1$ from $\{1, 2, 3, \dots ,n-r+1 \}$, and this can be done in $\binom{n-r+1}{r}$ ways.

Now suppose we make selections from a circular arrangement of $\{1,2,\dots,n\}$ with no two selections adjacent; this differs from a linear arrangement only in that we may not select both $1$ and $n$. So how many arrangements does this eliminate? If a selection is bad in the sense that both $1$ and $n$ are selected but otherwise acceptable, then it must also be that neither $2$ nor $n-1$ is selected. We are left with $r-2$ non-adjacent integers to select from the $n-4$ integers from $3$ to $n-2$, and we know from above that this can be done in $\binom{(n-4)-(r-2)+1}{r-2}$ ways. So the number of ways to select $r$ integers from $\{1,2,\dots,n\}$ with no two adjacent in the circular sense is $$\binom{n-r+1}{r}-\binom{(n-4)-(r-2)+1}{r-2} = \frac{n}{r}\binom{n-r-1}{r-1}$$