Miklos Schweitzer 1968 P11 by Renyi

Question

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<n$:

$$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!

Answer 1

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.

Answer 2

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.

Answer 3

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<j$, 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.