# Measure of intersections in probability spaces

Let $(X,\mu)$ be a probability space, and $0<\epsilon<1/2$. Let $\{A_i:i\in \mathbb{N}\}$ be a collection of measurable subsets of $X$ such that $\mu(A_i)\geq \epsilon$ for all $i\in\mathbb{N}$.

Is it always true that there are indices $i<j$ such that $\mu(A_i\cap A_j)\geq \epsilon^2$ ? Is it possible to classify the (possible) counterexamples?

• Is this a homework question? – Anthony Quas Feb 5 '16 at 16:30
• @AnthonyQuas No, it is a lemma that I needed. I could prove it assuming the bound to be $\epsilon^t$ for any $t>2$ using inclusion-exclusion (which was enough to my purposes), and I was just curious about this particular case. – Darío G Feb 5 '16 at 17:01

Take Borel measure on $[0,1]$ as an example. Cut off disjoint intervals $I_1,I_2,\dots$ where $I_i$ has length $2^{-i}\epsilon$. That's length $\epsilon$ altogether. In the remaining $1-\epsilon$, take independent events $B_1,B_2,\ldots$ with $B_i$ of measure $(1-2^{-i})\epsilon$. Define $A_i=I_i\cup B_i$. Then $A_i$ has measure $\epsilon$ for all $i$, and $A_i\cap A_j$ has measure $(1-2^{-i})(1-2^{-j})\epsilon^2\lt \epsilon^2$ for $i\ne j$.

Do I need to cite a theorem that $B_1,B_2,\ldots$ exist? I think it is standard elementary probability, and anyway it is easy to prove using finite unions of intervals.

• This is the right way to do it. – Nik Weaver Feb 8 '16 at 4:22
• For the existence of the $B_i$, you could do this: work in the product of a sequence of copies of $[0,1]$ and let $B_i'$ be the product of $[0,(1-2^{-i})\frac{\epsilon}{\delta}]$ on the $i$th factor and $[0,1]$ on ever other factor, where $\delta = 1-\epsilon$. Then scale the whole product by $\delta$. – Nik Weaver Feb 8 '16 at 5:39
• (The theorem you could cite is that this space is measurably equivalent to the interval $[0,\delta]$, but for the purpose of constructing a counterexample you could just work with the product space union an interval of length $\epsilon$. So the citation is unnecessary.) – Nik Weaver Feb 8 '16 at 5:41

The answer is negative: It is possible that there is no good choice of $i,j$. Let $T$ be a uniform spanning tree in the infinite ladder ${\bf Z} \times \{0,1\}$. To be precise, this is a weak limit of uniform spanning trees from finite ladders as shown to exist in [1]. See Chapter 4 of [2] for more information. Let $A_i$ be the event that the $i$'th rung of the ladder is an edge of $T$. Then ${\bf P}(A_i)$ does not depend on $i$ and ${\bf P}(A_i \cap A_j) < {\bf P}(A_i) {\bf P}(A_i)$ because the transfer-current matrix has positive entries. Now ${\bf P}(A_i)>1/2$, but this is easily addressed by replacing $A_i$ with the intersection $A_i \cap \{B_i=1\}$, where $\{B_i\}$ are i.i.d.\ fair coins independent of the events $\{A_i\}$.

Many other examples of stationary determinantal processes that can be used as counterexamples to your question are discussed in [3].

[1] Pemantle, R. (1991), Choosing a spanning tree for the integer lattice uniformly. Ann. Probab., 19(4), 1559–1574.

[2] Lyons, R. and Peres, Y. (2016), Probability on Trees and Networks, Cambridge University Press, to appear. Available at http://pages.iu.edu/~rdlyons

[3] Lyons, R. and Steif, J.E. (2003) Stationary determinantal processes: phase multiplicity, Bernoullicity, entropy, and domination. Duke Math. J., 120(3), 515–575. http://pages.iu.edu/~rdlyons/pdf/dyn.pdf

Yes, probably. I'm going to assume I can make all the $A_i$ have measure $\epsilon$. Making them smaller shouldn't hurt. $$0 \le \mathbb{E} (\sum(1_{A_i} - \mu(A_i))^ 2 = N \mu(A_i)(1- \mu A_i) + \sum_{i \neq j} \mu(A_i \cap A_j) - N (N-1) \epsilon^2$$ Therefore $$max \mu(A_i \cap A_j) \geq -\frac {\epsilon(1-\epsilon)} {N-1}+ \epsilon ^2$$ which, as N can be made arbitrarily large gets the result. This argument occurs in showing that finite exchangeable sequences can't have large negative correlations.

• Also, how exactly the last inequality help me to find the two indices satisfying $\mu(A_i\cap A_j)\geq \epsilon^2$? Couldn't it be possible that the indices witnessing the maximum value of $\mu(A_i\cap A_j)$ also depend on N, and the measure of the intersection keep being always strictly less than $\epsilon^2$? – Darío G Feb 5 '16 at 17:09
• There's a missing parenthesis in the inequality. It should be $\mathbb E\Big( \Big[ \sum \big(1_{A_i}-\mu(A_i)\big)\Big]^2\Big)$. It's positive because square numbers are non-negative. – Anthony Quas Feb 5 '16 at 17:35