# Miklos Schweitzer 1968 P11 by Renyi

Source: Miklos Schweitzer 1968, Problem 11

Let $$A_1,...,A_n$$ be arbitrary events in a probability field. Denote by $$C_k$$ the event that at least $$k$$ of $$A_1,...,A_n$$ occur. Prove that $$\prod_{k=1}^n P(C_k) \leq \prod_{k=1}^n P(A_k).$$

Attempt: I believe the first step to tackle this would be to employ Bayes rule:

$$P(C_n)=P(A_1\cap\cdots\cap A_n)=P(A_2\cap\cdots\cap A_n|A_1)P(A_1)$$

as here we accrue a $$P(A_1)$$ term times something less than or equal to one which is promising for the inequality to show. Then my guess would be to continue to establish similar correspondences with the other $$P(A_i)$$ terms. I try that by further employing Bayes to get

$$P(C_n)=P(A_1)P(A_2|A_1\cap A_3\cap\cdots\cap A_n)P(A_3\cap\cdots\cap A_n|A_1).$$

However this seems to lead to a dead end (at least with $$C_n$$) because I'm conditioning the other $$A_k$$ terms on some measurable subset of the sample space, so I can't obtain the other $$P(A_k)$$ terms unconditioned without magic. Another approach or follow-up that seems messy is to use sub-additivity of $$P$$ to look at the $$C_k$$ terms for $$k:

$$P(C_k)=P\left(\bigcup\limits_{i_1\neq i_2\neq\cdots\neq i_k} A_{i_1}\cap\cdots\cap A_{i_k}\right)\leq \sum\limits_{i_1\neq i_2\neq\cdots\neq i_k} P\left(A_{i_1}\cap\cdots\cap A_{i_k}\right)$$

but um, aside from applying Bayes here to get $$P(A_k)$$ times some constant $$\leq 1$$, this doesn't help as we are adding these factors, not multiplying.

Question: I would appreciate tactics/hints here (preferably related to my line of reasoning if possible), not full blown solutions - thanks!

• I would try to solve the case $n = 2$ first and see if it helps. Commented Jun 12, 2022 at 4:16
• I have a proof for $n=2$ but the general case looks really complicated. Commented Jun 12, 2022 at 6:09

I think I solved it. First do the case $$n = 2$$, which can be done directly using $$P(A \cap B) = P(A) - P(A \setminus B)$$, $$P(A \cup B) = P(B) + P(A \setminus B)$$. Then notice that if $$A_1 \supset \dots \supset A_n$$, then $$C_k = A_k$$ and we have equality. The strategy to reduce to this case is by modifying the sets until we have $$A_1 \supset \dots \supset A_n$$. The $$n = 2$$ case will help you do the modifications.

• Oh this is a very nice strategy - I appreciate it. If the sets are decreasing, then $P(C_1)=P(A_1\cup\cdots\cup A_n)=P(A_1)$ as the other sets are subsets of $A_1$, and so forth for $k>1$. I will have to think about how to do the modification a bit more
– user672552
Commented Jun 12, 2022 at 16:11
• Maybe a dumb question: why is there not always equality - can I not always just relabel the sets in decreasing order so $E_1=A_j,\dots,E_n=A_k$ and then as $P(C_1)=P(E_1)$, we have $P(C_1)=P(A_j)$ and so on?
– user672552
Commented Jun 12, 2022 at 16:31
• @pSrIoGcNeAsLs It isn't always possible to order sets. We might have $A_1 \not \subset A_2$ and $A_2 \not \subset A_1$. e.g. $A_1 = \{1, 2\}$, $A_2 = \{2, 3\}$. However, $A_1 \cap A_2 \subset A_1 \cup A_2$ ... Commented Jun 12, 2022 at 18:06

Write $$X_i = \mathbf{1}_{A_i}$$ and let $$S_n = X_1 + \cdots + X_n$$. Then we have $$C_k = \{ S_n \geq k \}$$, and so, the problem boils down to proving

$$\prod_{k=1}^{n} \mathbf{P}(S_n \geq k) \leq \prod_{k=1}^{n} \mathbf{P}(X_k = 1). \tag{1}$$

Now we prove this by induction. Note that we always have

$$\mathbf{P}(A)\mathbf{P}(B) \geq \mathbf{P}(A\cup B)\mathbf{P}(A \cap B). \tag{*}$$

Then

Base case. When $$n = 1$$, the claim is trivial.

Induction step. Suppose $$\text{(1)}$$ holds for some $$n > 1$$. Then

\begin{align*} \prod_{k=1}^{n+1} \mathbf{P}(X_k = 1) &\geq \mathbf{P}(X_{n+1} = 1)\left[ \prod_{k=1}^{n} \mathbf{P}(S_n \geq k) \right]. \end{align*}

Also, note that

\begin{align*} &\mathbf{P}(X_{n+1} = 1, S_{n} \geq k-1)\mathbf{P}(S_n \geq k) \\[0.25em] &\geq \mathbf{P}\left(\begin{gathered} (X_{n+1} = 1, S_{n} \geq k-1) \\ \text{ or } (S_{n} \geq k) \end{gathered}\right) \cdot \mathbf{P}\left( \begin{gathered} (X_{n+1} = 1, S_{n} \geq k-1) \\[0.25em] \text{ and } (S_{n} \geq k) \end{gathered}\right) \\ &= \mathbf{P}(S_{n+1} \geq k) \mathbf{P}(X_{n+1} = 1, S_{n} \geq k). \end{align*}

Now use this relation for $$k = 1, \ldots, n$$ to establish the induction step.

• This is too generous of a hint haha (more like a proof sketch), but thank you for the inductive approach - it makes sense!
– user672552
Commented Jun 12, 2022 at 17:23

# Solution.

We start with three remarks: Comment $$A$$. The statement is true for $$n=2$$, that is, $$P(A+B) P(A B) \leq P(A) P(B) .$$

To see this, use the notation $$A B=x, A \bar{B}=y$$, and $$\bar{A} B=z$$. Then our inequality becomes $$(P(x)+P(y)+P(z)) P(x) \leq(P(x)+P(y))(P(x)+P(z)),$$ which obviously holds. Comment $$B$$. If $$A_1 \supseteq \cdots \supseteq A_n$$, then $$C_k=A_k$$.

C. $$C_k$$ is identical to the event that at least $$k$$ occur from the events $$A_1+A_2, A_1 A_2, A_3, \ldots, A_n$$, that is, from the events $$A_1+A_2, A_1 A_2$$, $$A_3, \ldots, A_n$$, exactly as many occur as from the events $$A_1, A_2, \ldots, A_n$$. This statement is trivial.

Our proof is based on the above comments. Put $$A_i^0=A_i(i=1, \ldots, n)$$, and assume that the events $$A_1^\mu, \ldots, A_n^\mu$$ are already defined. Next, define the events $$A_1^{\mu+1}, \ldots, A_n^{\mu+1}$$ as follows: choose a pair $$A_i^\mu, A_j^\mu$$ of events, $$i, for which $$A_i^\mu \nsupseteq A_j^\mu, A_j^\mu \nsupseteq A_i^\mu$$ (that is, $$A_i^\mu$$ and $$A_j^\mu$$ are incomparable) and define $$A_i^{\mu+1}=A_i^\mu+A_j^\mu, A_j^{\mu+1}=A_i^\mu A_j^\mu$$ and $$A_k^{\mu+1}=A_k^\mu$$ for $$k \neq i, j$$. Continue this procedure until there exists at least one pair of incomparable events. This procedure will terminate in finitely many steps, since in each step the number of incomparable pairs decreases. This observation follows from the facts that $$A_i^{\mu+1}$$ and $$A_j^{\mu+1}$$ become comparable, and any event is comparable to at least as many of the events $$A_i^\mu+A_j^\mu, A_i^\mu A_j^\mu$$, as of $$A_i^\mu$$ and $$A_j^\mu$$. By comment $$A$$, $$\prod_{k=1}^n P\left(A_k^{\mu+1}\right) \leq \prod_{k=1}^n P\left(A_k^\mu\right) .$$

Observe that comment $$C$$ implies that the events $$C_k$$ remain unchanged, and because of comment $$B$$ they are identical to the final events $$A_i^\mu$$. Therefore, (1) implies the original statement.

From the proof of comment $$A$$, we see that if $$\prod_{k=1}^n P\left(A_k^\mu\right) \neq 0$$ and $$P\left(A_i^\mu \bar{A}_j^\mu\right) P\left(\bar{A}_i^\mu A_j^\mu\right) \neq 0$$, then strict inequality holds in (1). Hence, equality holds iff either $$\prod_{k=1}^n P\left(A_k\right)=0$$ or the original system of events $$\left\{A_k\right\}$$ are already "ordered." Remarks.

1. If multiplication is replaced by addition, then in the statement we always have equality. That is, $$\sum_{i=1}^n P\left(C_i\right)=\sum_{i=1}^n P\left(A_i\right) .$$
2. Let $$S_k\left(x_1, \ldots, x_n\right)$$ be the $$k$$ th elementary symmetric polynomial of the variables $$x_1, \ldots, x_n$$. Then $$S_k\left(P\left(C_1\right), \ldots, P\left(C_n\right)\right) \leq S_k\left(P\left(A_1\right), \ldots, P\left(A_n\right)\right) .$$

Slight modifications of the above proof can be applied to show the validity of this more general statement.