4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Is this a homework question? $\endgroup$ – Anthony Quas Feb 5 '16 at 16:30
  • $\begingroup$ @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. $\endgroup$ – Darío G Feb 5 '16 at 17:01
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is the right way to do it. $\endgroup$ – Nik Weaver Feb 8 '16 at 4:22
  • $\begingroup$ 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$. $\endgroup$ – Nik Weaver Feb 8 '16 at 5:39
  • $\begingroup$ (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.) $\endgroup$ – Nik Weaver Feb 8 '16 at 5:41
9
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Darío G Feb 5 '16 at 17:09
  • $\begingroup$ 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. $\endgroup$ – Anthony Quas Feb 5 '16 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.