11
$\begingroup$

My question is somewhere in the interface of combinatorics, probability, and measure theory. It is quite ad-hoc, and I wonder if there is a counter example.

Consider for example the unit interval $[0,1]$, and the collection of subsets $\{K_j\}_{j\leq n}$ such that almost every point lies in at least $\epsilon n$-many sets. That is, $$\epsilon\leq \int \frac{1}{n}\sum_{j\leq n} \mathbb{1}_{K_j}d\mathrm{Leb},$$ where $\epsilon>0$ is small.

My question is, can I find a subsequence $\mathcal{L}\subseteq\{1,\ldots,n\}$ and a subset $E\subseteq [0,1]$ such that $\frac{1}{n}\#\mathcal{L}\geq \epsilon’$ and $\mathrm{Leb}(E)\geq \epsilon’$, and $$1-\epsilon’\leq \frac{1}{\mathrm{Leb}(E)}\int_E \frac{1}{\#\mathcal{L}}\sum_{j\in \mathcal{L}} \mathbb{1}_{K_j}d\mathrm{Leb},$$ where $\epsilon’>0$ is small (but independent of $n$)? We may assume for simplicity that $\mathrm{Leb}(K_j)\geq \epsilon$ for all $j\leq n$.

To put in words, we start with a sequence of events which are observed with positive but small frequencey, and we wish to choose a smaller portion of the space and a subset of the events, where they are observed with a relative high frequency.

$\endgroup$
1
  • $\begingroup$ Regarding your less technical question in words, this is the subject of importance sampling in statistics. $\endgroup$
    – Kimball
    Commented Aug 20 at 20:44

1 Answer 1

20
$\begingroup$

The answer is no.

This is a good illustration of a reasoning principle identified explicitly in

Gowers, W. T., The two cultures of mathematics, Arnold, V. (ed.) et al., Mathematics: Frontiers and perspectives. Providence, RI: American Mathematical Society (AMS). 65-78 (2000). ZBL0998.00003.

Specifically, the following principle was identified by Gowers as one of the key takeaways from the probabilistic method in combinatorics (and specifically, Erdos's famous probabilistic construction of a random graph with no large cliques or independent sets):

if one is trying to maximize the size of some structure under certain constraints, and if the constraints seem to force the extremal examples to be spread about in a uniform sort of way, then choosing an example randomly is likely to give a good answer.

(The rest of Gowers' article is worth reading, by the way.)

Anyway, let's follow this principle and try to construct a counterexample "randomly", or more precisely to give a random construction that obeys all the properties required for a counterexample with positive probability. The calculations are may seem somewhat lengthy to someone not familiar with the probabilistic method, but the argument below is actually rather standard in the subject, so much so that it could be described to an expert as "just use the probabilistic method / the random construction".

One immediate issue is that the unit interval $[0,1]$ has uncountably many points, and so there are measure-theoretic difficulties in creating a perfectly "random" subset of $[0,1]$; but we can get around this by the usual device of discretization. Accordingly, let us subdivide $[0,1]$ into $N$ intervals $I_1,\dots,I_N$ of length $1/N$, for some parameter $N$ we can optimize in later. We choose each $K_1,\dots,K_n$ to be the union of random subcollections of these intervals, chosen independently at random; for simplicitly let us take the uniform model, in which each $I_i$ is contained in $K_j$ with an independent probability of $1/2$. Another way of thinking about this is to consider a discrete rectangle $\{1,\dots,N\} \times \{1,\dots,n\}$ and select a random subset $S$ of points $(i,j)$ in it, with each point selected with an independent probability of $1/2$; each set $K_j$ then corresponds to one row of this random set, and the pointwise behavior of the sets is determined by the columns.

From the law of large numbers we see that when $nN$ is large, the mean density $\int \frac{1}{n} \sum_{j \leq n} 1_{K_j}\ d\mathrm{Leb}$ (which is also the density of $S$ in the rectangle) will be close to $1/2$, in particular larger than $\varepsilon$ with probability $1-o(1)$ if $\varepsilon$ is small and $nN$ is sufficiently large depending on $\varepsilon$.

Now we study the subaverages $\frac{1}{\mathrm{Leb}(E)} \int_E \frac{1}{\# \mathcal L} \sum_{j \in {\mathcal L}} 1_{K_j}\ d\mathrm{Leb}$ for various ${\mathcal L} \subset \{1,\dots,n\}$ and $E \subset [0,1]$. The standard approach here is to apply the union bound ${\mathbf P}(\bigcup_\alpha F_\alpha) \leq \sum_\alpha {\mathbf P}(F_\alpha)$ to bound the total failure probability of the construction. This looks okay for taking unions over ${\mathcal L}$, since there are only $O(2^n)$ possibilities here, but there are uncountably many measurable subsets $E$ of $[0,1]$ to deal with. But there are various ways to proceed here. A standard way is the second moment method, and specifically to try to establish a second moment bound $$ \int_{[0,1]} |\frac{1}{\# \mathcal L} \sum_{j \in {\mathcal L}} 1_{K_j} - \frac{1}{2}|^2\ d\mathrm{Leb} \leq o(1)$$ for each candidate ${\mathcal L}$, as the required claim would then be contradicted for all sets $E$ of measure at least $\varepsilon'$ (if the $o(1)$ bound is sufficiently small depending on $\varepsilon$) just from Cauchy-Schwarz. This eliminates the need to take the union over $E$; there is still an exponential number (in $n$) of ${\mathcal L}$'s to deal with, but as we shall see we can cut down on this "entropy" as well (although for this particular problem we could in fact tolerate metric entropies that were exponentially growing in $n$, just by taking $N$ to be even larger than this).

By expanding out the square, it would suffice to establish the first moment estimate $$ \int_{[0,1]} \frac{1}{\# \mathcal L} \sum_{j \in {\mathcal L}} 1_{K_j}\ d\mathrm{Leb} = \frac{1}{2} + o(1)$$ and the second moment estimate $$ \int_{[0,1]} (\frac{1}{\# \mathcal L} \sum_{j \in {\mathcal L}} 1_{K_j})^2 d\mathrm{Leb} = \frac{1}{4} + o(1).$$ Using the very standard Fubini--Tonelli trick of rearranging the sum and integrals, this becomes $$ \frac{1}{\# \mathcal L} \sum_{j \in {\mathcal L}} |K_j| = \frac{1}{2}+o(1)$$ and $$ \frac{1}{(\# \mathcal L)^2} \sum_{j,k \in {\mathcal L}} |K_j \cap K_k| d\mathrm{Leb} = \frac{1}{4} + o(1).$$

The measure of $K_j$ is the density of the $j^{th}$ row of $S$. The law of large numbers indeed suggests that this density is close to $1/2$; the more precise Hoeffding inequality tells us that it is $1/2+O(\delta)$ with probability $1 - O(\exp(-c \delta^2 N))$ for any small fixed $\delta>0$ and some absolute constant $c>0$, assuming $N$ is large. There are $n$ choices of $K_j$, so by the union bound we see that with probability at least $1 - O(n \exp(-c \delta^2 N))$, all of the $K_j$ will simultaneously have measure $1/2+O(\delta)$, which will imply the first moment bound if $\delta$ is small enough depending on $\varepsilon'$. Similarly, there are $O(n^2)$ choices of pair $K_j, K_k$, and one can similarly show that with probability at least $1 - O(n^2 \exp(-c \delta^2 N))$, all the pairwise intersections of $K_j, K_k$ for $j \neq k$ have measure $1/4+O(\delta)$ if $\delta$ is sufficiently small (and $n$ sufficiently large) depending on $\varepsilon'$. So now one just has to take $N$ large enough depending on all previous parameters to make the failure probability go to zero, and we are done.

There are ways to "derandomize" the above construction and find a deterministic example, for instance by selecting $K_j$ to be those $x \in [0,1]$ whose $j^{th}$ binary digit is equal to $1$. I'll leave you to work out the details of this as an exercise. [An even quicker way to proceed is to take $S$ to basically be the incidence matrix of a bipartite expander graph of positive density and apply the expander mixing lemma, and indeed the classical Pinsker construction of a random expander graph (also previously discovered by Kolmogorov and Barzdin) is very closely related to the argument provided here.]

$\endgroup$
1
  • 4
    $\begingroup$ Wow wonderful explanation! Thank you very much for the enlightening and detailed answer! $\endgroup$ Commented Aug 19 at 16:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .