Sufficiently random sample

Question

Let $d$ be an integer $\geq 2$, and let $\Omega = \lbrace 0,1 \rbrace^d$, $A \subseteq \lbrace 0,1 \rbrace^2 $ and $i,j$ integers with $1 \leq i < j \leq d$. If we select an element $(x_1,x_2, \ldots, x_d)$ in $\Omega$ randomly, the probability $p(\Omega,i,j,A)$ that $(x_i,x_j)\in A$ is exactly $\frac{|A|}{4}$.

If $\Omega'$ is a subset ("sample") of $\Omega$, we may similarly define $p(\Omega',i,j,A)$. We say that $\Omega'$ is an efficient substitute for $\Omega$ if $p(\Omega',i,j,A)=p(\Omega,i,j,A)$ for all $i,j$ and $A$.

We denote by $f(d)$ the smallest possible size for an efficient substitute for $\Omega$. We have the trivial bound $f(d) \leq 2^d$ (take $\Omega'=\Omega$) and , for example, $f(3)=4$ (take $\Omega'=\lbrace (x,y,x+y-2xy) |(x,y) \in \lbrace 0,1 \rbrace^2 \rbrace$). What is the value of $f(d)$ in general?

Answer 1

I like the question. You are actually asking, what is the smallest finite probability space (in size of $\Omega'$) on which one can have $d$ distinct pair-wisely independent (but not necessarily independent) events of probability $\frac{1}{2}$. Just to explain the reformulation: once the $i$-th event is defined to be $$E_{i}=\lbrace\omega\in\Omega'\;|\;\omega(i)=1\rbrace,$$ the "efficient substitute" criterion amounts to $\mathrm{Pr}(E_{i})=\frac{1}{2}$ and $\mathrm{Pr}(E_{i}\cap E_{j})=\frac{1}{4}$ for every $i,j$ with $1\le i,j\le d$ and $i\not=j$. The example for $d=3$ is a well known case of this situation.

Now, every such space satisfies $|\Omega'|=4n$ for some natural $n$ (the reason being obvious). Knowing this, we could ask an inverse question: given a $4n$-set $\Omega'$, what is the maximum size of a family $\mathcal{F}$ of $2n$-subsets of $\Omega'$ such that every two of them have intersection of size $n$. Knowing a precise answer to this, the original problem is solved as well: given a $d$ take the smallest $4n$ such that the maximum size of $\mathcal{F}$ is at least $d$.

There is a paper titled "Pairwise intersections and forbidden configurations". Let me quote from the abstract:

Let $f_{m}(a,b,c,d)$ denote the maximum size of the family $\mathcal{F}$ of subsets of an $m$-element set for which there is no pair of subsets $A,B\in\mathcal{F}$ with $|A\cap B|\ge a$, $|A^{c}\cap B|\ge b$, $|A\cap B^{c}|\ge c$, and $|A^{c}\cap B^{c}|\ge d$.

The count we are looking for is exactly $f_{4n}(n+1,n+1,n+1,n+1)$. Besides other interesting things, the paper gives also asymptotic estimates for this count; one of them gives $\Theta(4n^{2n-1})$ in our case.

Edit: unfortunately, I was too quick with the asymptotic estimate. The paper gives an estimate only for fixed $a,b,c,d$ as $m$ tends to $\infty$.

Answer 2

You can find a set $\Omega$ with size $O(d)$. Assume for simplicity that $d=2^k-1$ for an integer $k$. Let $y_1,..,y_k$ be binary variables and define $x_j = \sum_i y_i \alpha_i(j)$ where $\alpha_i(j)$ is simply the $i$-th digit of $j$ when represented in binary. (For example, if $n=7$, you'll get $y_1, y_2, y_3, y_1+y_2, y_1+y_3, y_2+y_3, y_1+y_2+y_3$). You can get $2^k-1$ such linear combinations and they're all balanced and independent - that is $Pr(x_i=1)=1/2$ and $Pr(x_i=a,x_j=b)=1/4, \: \forall a,b=0,1$. This will satisfy the condition $p(\Omega,i,j,A) = |A|/4$. When $d=2^k-1$ this gives $f(d)\leq d+1$. For general $d$ (not be a power of two minus one) you should get $f(d) \leq 2d$ taking $d=2^k$ as the worst case.