Prove that it exists $i \neq j$ s.t. $P(A_i \cap A_j) \geq \frac{nc^2-c}{n-1}$ with $P(A_i) \geq c $

Question

Question:

Let $A_1,A_2,...,A_n \subset \Omega $ a sequence of outcome such that $P(A_i) \geq c $ for all $i$.
Prove that it exists $i \neq j$ s.t. $P(A_i \cap A_j) \geq \frac{nc^2-c}{n-1}$

I have tried different ways including the following one but I did not succeed to conclude.

1-First note that: $\int (\sum_{1 \leq i \leq n} I_{A_i})^2dP= \sum_{i \neq j} \int I_{A_i}I_{A_j}dP + \sum_{i = j} \int I_{A_i}^2dP= \sum_{i \neq j} P(A_i \cap A_j) + \sum_{i = j}P(A_i)$

2-Now we know that $\sum_{i = j}P(A_i)$ is the sum of $n$ element, thus $\sum_{i = j}P(A_i) \geq nc$

3-We know too that $\sum_{i \neq j} P(A_i \cap A_j)$ is the sum of $n(n-1)$ elements.
More over $\forall i \neq j$ by absurd let suppose that $P(A_i \cap A_j) < \frac{nc^2-c}{n-1}$.
But after I don't succeed to continue. Can someone help me please?

Thank for your help.

Answer 1

HINT:

It is enough to show the following fact: if $\sum P(A_i) \ge s$, then $\sum_{i< j} P(A_i\cap A_j) \ge \binom{s}{2}$ as follows. Consider the polytope formed by all possible values $(\sum P(A_i), \sum P(A_i \cap A_j)$. It is the image under a linear map of a $2^n-1$ dimensional simplex consisting of all the possible $(P(A_1^{\epsilon_1} \cap A_2^{\epsilon_2} \cap \ldots A_n^{\epsilon_n}))$, where $\epsilon_k = \pm 1$, $A_k^1 = A_k$, $A_k^{-1} = A_k^c$ ( the complement). The vertices of the simplex ( $2^n$ of them) correspond to the $A_i$ being $\emptyset$ or $\Omega$ ( the total set). The vertices map to $(k, \binom{k}{2})$, where $k \in \{0,1, \ldots,n\}$ (meaning $k$ of the $A_i$ are $\Omega$, the other $\emptyset$). We conclude: the set of possible values of $(\sum P(A_i), \sum P(A_i \cap A_j)$ is the convex hull of $(k, \binom{k}{2})$, with $0 \le k \le n$. Notice that these points form a convex polygon with $n+1$ vertices, inscribed in the parabola $(x, \binom{x}{2})_{x\ge 0}$. Now the inequality follows.

Answer 2

Remark: $z = \sum_{i = j}P(A_i)$

4-Let define $X = \sum_i I_{A_i} $ so according to the Jensen inequality we have that $(E[X])^2 \leq E[X^2]$ or equivalently $(E[X])^2 = (\int \sum_i I_{A_i} dP)^2 = ( \sum_i P(A_i))^2 = z^2 \leq E[X^2] = \int (\sum_i I_{A_i} )^2 dP $.

5-Remind that by absurd assumption we have that: $ (E[X])^2= \sum_{i \neq j} P(A_i \cap A_j) + \sum_{i = j}P(A_i) < n(n-1) \frac{nc^2-c}{n-1} + \sum_{i = j}P(A_i) = nc(nc-1) + \sum_{i = j}P(A_i) = z + nc(nc-1)$

6- From "-5" and "-4" combine we get that $z^2 < z + nc(nc-1) \Rightarrow z^2 - z = z(z-1) < nc(nc-1) $.
On an other side $z^2 - z$ is an increasing function on $z \geq 1$ and $nc \geq 1$ (other wise it is negative and the given inequality is satisfied). And let remember that $z=\sum_{i = j}P(A_i)$ with $ \forall i $ we have that $P(A_i) \geq c \Rightarrow z \geq nc $. So We should have $z(z-1) \geq nc(nc-1)$ and not $z(z-1) < nc(nc-1)$.

Q.E.D.