Probability of even number of events occuring

Question

As part of trying to fresh up on my basic probability theory I came along Ex. 1.46 in Grimmet's probability book with the second part troubling me.

If $A_1$, $A_2$ , . . . , $A_m$ are independent and $P(A_i) = p$ for $i = 1, 2, . . . , m$, find the probability that
(a) none of the $A_i$ occur,
(b) an even number of the $A_i$ occur.

a) none of $A_i$

Just computing the probability of the event $E=\Omega \ \backslash ( \cup_i A_i ) $ (i.e. 'all events without the union of all $A_i$') with $q=1-p$ and using the event's independence:
$$P \bigg ( \bigg [\bigcup_i^m A_i \bigg]^c \bigg) = P \bigg ( \bigg [\bigcap_i^m A_i^c \bigg ] \bigg ) = P(A^c)^m = q^m = (1-p)^m$$ which agrees with the answer in the back of the book.

b) even number of $A_i$

I expected this one to be as easy as part (a), but apparently I am overlooking something. My idea was to build sets that consist of an even number of sets without the rest and then computing and summing up the probability of them. E.g. for $m=4$ this would be: $$ E_1 = A_1 \cap A_2 \backslash ( A_3 \cup A_4) \\ E_2 = A_1 \cap A_3 \backslash ( A_2 \cup A_4) \\ ... \\ E_6 = A_3 \cap A_4 \backslash ( A_1 \cup A_2) \\ E_7 = (A_1 \cap A_2 \cap A_3 \cap A_4) $$ where there are 6 combinations to get two events out of four, $6=$ $4 \choose 2$. The probability for such an event in detail is $$ \begin{align} P(E_1) & =P(A_1 \cap A_2 \backslash ( A_3 \cup A_4))\\\ &= P(A_1 \cap A_2) - P((A_1 \cap A_2) \cap (A_3 \cup A_4))\\ &= P(A_1) P(A_2) - P(A_1 \cap A_2) P(A_3 \cup A_4)\\ &= p^2 - p^2 \ P(A_3 \cup A_4)\\ &= p^2 - p^2 \ ( P(A_3)+P(A_4)-P(A_3 \cap A_4))\\ &= p^2 - p^2 \ ( p+p-p^2) = p^2 ( 1-2p+p^2)\\ &= p^2 (1-p)^2 \\ &= p^2 q^2 \end{align} $$ which is true for $E_1$ to $E_6$, where we have each two events happening ($p^2$) while two other events are not happening (the $q^2$), and $E_7$ just giving $P(E_7)=p^4$ because four events are happening.

So for the case of m=4 we should get that the probability for an even number of events to occur should be $$ P(\text{even number})=\sum_i P(E_i)=P(E_1)+ ... +P(E_7) = 6 p^2 q^2 + p^4 $$ Apart from the back of the book giving a different answer anyway, namely $$ P(\text{even number})_{book}=\frac{1}{2} [1+(q-p)^m],$$ I would not even know how to generalize my example for $m=4$ to any m.

Studying the book's answer and expanding the bracket term gives $$ (q-p)^4=p^4 - 4 p^3 q + 6 p^2 q^2 - 4 p q^3 + q^4 $$ in which two parts of the sum agree with my result. It looks like the event of 4 times happening 'not $A_i$' ($q^4$) is also counted as an even event of the$A_i$'s, while the uneven events are being subtracted ($p^3q$ and $pq^3$). But even then, I do not see how to get there or where the $\frac{1}{2}$ comes from.
Does anyone know where I am going wrong? Thanks!

Answer 1

First observe that expanding $(p+q)^m$ enumerates all the things that can happen. For example, the term $4p^3q=pppq+pqpp+ppqp+pppq$ in the expansion of $(p+q)^4$ represents the four ways in which exactly three of the events occur. The numerical value of $(p+q)^m$ is the sum of the probabilities of anything happening, which is of course $1$.

If we instead expand $(-p+q)^m$, then we count positively the probabilities that have an even number of $p$ factors and we count negatively those with an odd number of $p$ factors.

Therefore the numerical value of $(-p+q)^m$ is $P_e-P_o$, where $P_e$ is the probability of an even number of events and $P_o$ is the probability of an odd number of events.

The number of $A_i$ that occur is either odd or even (note that 0 is an even number), but not both, so $P_e+P_o=1$, and we just figured out that $P_e-P_o=(-p+q)^m$. Adding these equations, we get $$2P_e=(P_e+P_o)+(P_e-P_o)=(-p+q)^m+1,$$ which leads immediately to the book's answer.

Answer 2

Writing $X=\sum_{k=1}^m\mathbf1_{A_k}$ we are dealing with a sum of iid Bernoulli random variables with parameter $p$.

That gives $X$ binomial distribution with parameters $m$ and $p$.

To be found is: $$P(X\text{ is even})=\sum_{k\text{ even}}P(X=k)=\sum_{k\text{ even}}\binom{n}{k}p^kq^{m-k}\tag1$$where $q:=1-p$.

Working out the answer in the book by means of: $$\frac12[1+(q-p)^m]=\frac12[(p+q)^m+(q-p)^m]$$ you will arrive at the RHS of $(1)$.

---

P.S. I haven't checked your answer completely (yet), but in the case $m=4$ there are $\binom40+\binom42+\binom44=1+6+1=8\neq7$ possibilities.

Answer 3

The probability that exactly $k$ of the events occur is the coefficient of $x^k$ in $g(x) = (q + p x)^n$. Consider $(g(-x) + g(x))/2$. This has the same terms in even powers of $x$ as $g(x)$, but the terms in odd powers cancel. To add the coefficients of a polynomial we just substitute $x=1$. Thus the probability that the number of events that occur is even, i.e. the sum of coefficients of the even powers of $x$ in $g(x)$, is $(g(-1) + g(1))/2 = ((q - p)^n + 1)/2$.

Answer 4

Perhaps a bit more machinery than required. Note that $X=\sum_{k=1}^m I(A_k)\sim \text{Bin}(m,p)$ is the number of events that occur. Note that $X$ has probability generating function $$ g_{X}(t)=Et^X=\sum_{k=0}^m t^kP(X=k)=\sum_{k=0}^m t^k\binom{n}{k}p^{k}q^{n-k}=(q+pt)^m $$ In particular $$ P(\text{X is even})=\sum_{k=0\; \text{k even}}^mP(X=k)=\sum_{k=0\; \text{k even}}^m \binom{n}{k}p^{k}q^{n-k}=\frac{g(1)+g(-1)}{2}=\frac{1+(q-p)^m}{2} $$