Consider \(M\) events \(A_{1}, A_{2}, \ldots, A_{M}\) defined on a probability space. In this section we shall develop formulas for the probabilities of various events, defined in terms of the events \(A_{1}, \ldots, A_{M}\) , especially for \(m=\) \(0,1, \ldots, M\) , that (i) exactly \(m\) of them, (ii) at least \(m\) of them, (iii) no more than \(m\) of them will occur. With the aid of these formulas, a variety of questions connected with sampling and occupancy problems may be answered.

In particular, for \(m=0\) , \[P\left[B_{0}\right]=1-S_{1}+S_{2}-S_{3}+S_{4}-\cdots \pm\left(S_{M}\right). \tag{6.3}\] 

The probability that at least \(m\) of the \(M\) events \(A_{1}, \ldots, A_{M}\) will occur is given by (for \(m \geq 1\) ) \[P\left[B_{m}\right]+P\left[B_{m+1}\right]+\cdots+P\left[B_{M}\right]=\sum_{r=m}^{M}(-1)^{r-m}\left(\begin{array}{c} r-1 \tag{6.4} \\ m-1 \end{array}\right) S_{r}.\] 

Before giving the proof of this theorem, we shall discuss various applications of it.

Other applications of the theorem stated at the beginning of this section may be found in a paper by J. O. Irwin, “A Unified Derivation of Some Well-Known Frequency Distributions of Interest in Biometry and Statistics”, Journal of the Royal Statistical Society , Series A, Vol. 118 (1955), pp. 389–404 (including discussion).

The remainder of this section ¹ is concerned with the proof of the theorem stated at the beginning of the section. Our proof is based on the method of indicator functions and is the work of \(\mathrm{M}\) . Loève. Our proof has the advantage of being constructive in the sense that it is not merely a verification that (6.2) is correct but rather obtains (6.2) from first principles.

The method of indicator functions proceeds by interpreting operations on events in terms of arithmetic operations. Given an event \(A\) , on a sample description space \(S\) , we define its indicator function, denoted by \(I(A)\) , as a function defined on \(S\) , with value at any description \(s\) , denoted by \(I(A ; s)\) , equal to 1 or 0, depending on whether the description \(s\) does or does not belong to \(A\) .

The two basic properties of indicator functions, which enable us to operate with them, are the following.

First, a product of indicator functions can always be replaced by a single indicator function; more precisely, for any events \(A_{1}, A_{2}, \ldots, A_{n}\) , \[I\left(A_{1}\right) I\left(A_{2}\right) \cdots I\left(A_{n}\right)=I\left(A_{1} A_{2} \cdots A_{n}\right), \tag{6.15}\] so that the product of the indicator functions of the sets \(A_{1}, A_{2}, \ldots, A_{n}\) is equal to the indicator function of the intersection \(A_{1}, A_{2}, \ldots, A_{n}\) . Equation (6.15) is an equation involving functions; strictly speaking, it is a brief method of expressing the following family of equations: for every description \(s\) \[I\left(A_{1} ; s\right) I\left(A_{2} ; s\right) \cdots I\left(A_{n} ; s\right)=I\left(A_{1} A_{2} \cdots A_{n} ; s\right).\] 

To prove (6.15) , one need note only that \(I\left(A_{1} A_{2} \ldots A_{n} ; s\right)=0\) if and only if \(s\) does not belong to \(A_{1} A_{2} \ldots A_{n}\) . This is so if and only if, for some \(j=1, \ldots, n, s\) does not belong to \(A_{j}\) , which is equivalent to, for some \(j=1, \ldots, n, I\left(A_{j} ; s\right)=0\) , which is equivalent to the product \(I\left(A_{1} ; s\right) \cdots\) \(I\left(A_{n} ; s\right)=0\) .

Second, a sum of indicator functions can in certain circumstances be replaced by a single indicator function; more precisely, if the events \(A_{1}\) , \(A_{2}, \ldots, A_{n}\) are mutually exclusive, then \[I\left(A_{1}\right)+I\left(A_{2}\right)+\cdots+I\left(A_{n}\right)=I\left(A_{1} \cup A_{2} \cup \cdots \cup A_{n}\right). \tag{6.16}\] 

The proof of (6.16) is left to the reader. One case, in which \(n=2\) and \(A_{2}=A_{1}^{c}\) , is of especial importance. Then \(A_{1} \cup A_{2}=S\) , and \(I\left(A_{1} \cup A_{2}\right)\) is identically equal to 1. Consequently, we have, for any event \(A\) , \[I(A)+I\left(A^{c}\right)=1, \quad I\left(A^{c}\right)=1-I(A). \tag{6.17}\] From (6.15) to (6.17) we may derive expressions for the indicator functions of various events. For example, let \(A\) and \(B\) be any two events. Then \begin{align} I(A \cup B) & =1-I\left(A^{c} B^{c}\right) \tag{6.18} \\ & =1-I\left(A^{c}\right) I\left(B^{c}\right) \\ & =1-(1-I(A))(1-I(B)) \\ & =I(A)+I(B)-I(A B). \end{align} 

Our ability to write expressions in the manner of (6.18) for the indicator functions of compound events, in terms of the indicator functions of the events of which they are composed, derives its importance from the following fact: an equation involving only sums and differences (but not products) of indicator functions leads immediately to a corresponding equation involving probabilities; this relation is obtained by replacing \(I(\cdot)\) by \(P[\cdot]\) . For example, if one makes this replacement in (6.18) , one obtains the well-known formula \(P[A \cup B]=P[A]+P[B]-P[A B]\) .

The principle just enunciated is a special case of the additivity property of the operation of taking the expected value of a function defined on a probability space. This is discussed in Chapter 8 , but we shall sketch a proof here of the principle stated. We prove a somewhat more general assertion. Let \(f(\cdot)\) be a function defined on a sample description space. Suppose that the possible values of \(f\) are integers from \(-N(f)\) to \(N(f)\) for some integer \(N(f)\) that will depend on \(f(\cdot)\) . We may then represent \(f\left(\cdot\right)\) as a linear combination of indicator functions: \[f(\cdot)=\sum_{k=-N(f)}^{N(f)} k I\left[D_{k}(f)\right], \tag{6.19}\] in which \(D_{k}(f)=\{s: f(s)=k\}\) is the set of descriptions at which \(f(\cdot)\) takes the value \(k\) . Define the expected value of \(f(\cdot)\) , denoted by \(E[f(\cdot)]\) : \[E[f(\cdot)]=\sum_{k=-N(f)}^{N(f)} k P\left[D_{k}(f)\right]. \tag{6.20}\] 

In words, \(E[f(\cdot)]\) is equal to the sum, over all possible values \(k\) of the function \(f(\cdot)\) , of the product of the value \(k\) and the probability that \(f(\cdot)\) will assume the value \(k\) . In particular, if \(f(\cdot)\) is an indicator function, so that \(f(\cdot)=I(A)\) for some set \(A\) , then \(E[f(\cdot)]=P[A]\) . Consider now another function \(g(\cdot)\) , which may be written \[g(\cdot)=\sum_{j=-N(g)}^{N(g)} j I\left[D_{j}(g)\right]. \tag{6.21}\] We now prove the basic additivity theorem that \[E[f(\cdot)+g(\cdot)]=E[f(\cdot)]+E[g(\cdot)]. \tag{6.22}\] 

The sum \(f(\cdot)+g(\cdot)\) of the two functions is a function whose possible values are numbers, \(-N\) to \(N\) , in which \(N=N(f)+N(g)\) . However, we may represent the function \(f(\cdot)+g(\cdot)\) in terms of the indicator functions \(I\left[D_{k}(f)\right]\) and \(l\left[D_{j}(g)\right]\) : \[f(\cdot)+g(\cdot)=\sum_{k=-N(f)}^{N(f)} \sum_{j=-N(g)}^{N(g)}(k+j) I\left[D_{k}(f) D_{j}(g)\right].\] Therefore, \begin{align} E[f(\cdot)+g(\cdot)]= & \sum_{k=-N(f)}^{N(f)} \sum_{j=-N(g)}^{N(g)}(k+j) P\left[D_{k}(f) D_{j}(g)\right] \\ = & \sum_{k=-N(f)}^{N(f)} k \sum_{j=-N(g)}^{N(g)} P\left[D_{k}(f) D_{j}(g)\right] \\ & \quad+\sum_{j=-N(g)}^{N(g)} j \sum_{k=-N(f)}^{N(f)} P\left[D_{k}(f) D_{j}(g)\right] \\ & =\sum_{k=-N(f)}^{N(f)} k P\left[D_{k}(f)\right]+\sum_{j=-N(g)}^{N(g)} j P\left[D_{j}(g)\right] \\ & =E[f(\cdot)]+E[g(\cdot)], \end{align} and the proof of (6.22) is complete. By mathematical induction we determine from (6.22) that, for any \(n\) functions, \(f_{1}(\cdot), f_{2}(\cdot), \ldots, f_{n}(\cdot)\) ,

\[E\left[f_{1}(\cdot)+\cdots+f_{n}(\cdot)\right]=E\left[f_{1}(\cdot)\right]+\cdots+E\left[f_{n}(\cdot)\right]. \tag{6.23}\] 

Finally, from (6.23) , and the fact that \(E[I(A)]=P[A]\) , we obtain the principle we set out to prove; namely, that, for any events \(A, A_{1}, \ldots, A_{n}\) , if \[I(A)=c_{1} I\left(A_{1}\right)+c_{2} I\left(A_{2}\right)+\cdots+c_{n} I\left(A_{n}\right), \tag{6.24}\] in which the \(c_{i}\) are either +1 or -1, then \[P[A]=c_{1} P\left[A_{1}\right]+c_{2} P\left[A_{2}\right]+\cdots+c_{n} P\left[A_{n}\right]. \tag{6.25}\] 

We now apply the foregoing considerations to derive (6.2) . The event \(B_{m}\) , that exactly \(m\) of the \(M\) events \(A_{1}, A_{2}, \ldots, A_{M}\) occur, may be expressed as the union, over all subsets \(J_{m}=\left\{i_{1}, \ldots, i_{m}\right\}\) of size \(m\) of the integers \(\{1,2, \ldots, M\}\) , of the events \(A_{i_{1}} \ldots A_{i_{m}} A_{i_{m+1}}^{c} \ldots A_{i_{M I}}^{c}\) ; there are \(\left(\begin{array}{l}M \\ m\end{array}\right)\) such events, and they are mutually exclusive. Consequently, by (6.15) - (6.17) , \[I\left(B_{m}\right)=\sum_{J_{m}} I\left(A_{i_{1}}\right) \cdots I\left(A_{i_{m}}\right)\left[1-I\left(A_{i_{m+1}}\right)\right] \cdots\left[1-I\left(A_{i_{M}}\right)\right]. \tag{6.26}\] Now each term in (6.26) may be written \begin{align} I\left(A_{i_{1}}\right) \cdots I\left(A_{i_{m}}\right) & \left\{1-H_{1}\left(J_{m}\right)+\cdots+(-1)^{k} H_{k}\left(J_{m}\right)\right. \tag{6.27} \\[1mm] & \left.+\cdots \pm H_{M-m}\left(J_{m}\right)\right\}, \end{align} where we define \(H_{k}\left(J_{m}\right)=\Sigma I\left(A_{j_{1}} \ldots A_{j_{k}}\right)\) , in which the summation is over all subsets of size \(k\) of the set of integers \(\left\{i_{m+1}, \ldots, i_{M}\right\}\) . Now because of symmetry and (6.15) , one sees that \[\sum_{J_{m}} I\left(A_{i_{2}}\right) \cdots I\left(A_{i_{m}}\right) H_{k}\left(J_{m}\right)=\left(\begin{array}{c} m+k \tag{6.28} \\ m \end{array}\right) H_{k+m}.\] 

\(H_{k+m}=\Sigma I\left(A_{j_{1}} \ldots A_{j_{k+m}}\right)\) , in which the summation is over all subsets of size \(k+m\) of the set of integers \(\{1,2, \ldots, M\}\) . To see (6.28) , note that there are \(\left(\begin{array}{l}M \\ m\end{array}\right)\) terms in \(J_{m},\left(\begin{array}{c}M-m \\ k\end{array}\right)\) terms in \(H_{k}\left(J_{m}\right)\) , and \(\left(\begin{array}{c}M \\ m+k\end{array}\right)\) terms in \(H_{k+m}\) and use the fact that \(\left(\begin{array}{c}M \\ m\end{array}\right)\left(\begin{array}{c}M-m \\ k\end{array}\right) \div\left(\begin{array}{c}M \\ m+k\end{array}\right)=\) \(\left(\begin{array}{c}m+k \\ m\end{array}\right)\) .

Finally, from (6.24) to (6.28) and (6.1) we obtain \[P\left[B_{m}\right]=\sum_{k=0}^{M-m}(-1)^{k}\left(\begin{array}{c} m+k \tag{6.29} \\ m \end{array}\right) S_{k+m},\] which is the same as (6.2) . Equation (6.4) follows immediately from (6.2) by induction.

Theoretical Exercises

Exercises