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?



Sufficiently random sample
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](http://en.wikipedia.org/wiki/Pairwise_independence) 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](http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WDY-4K5SSV9-2&_user=10&_coverDate=11%252F30%252F2006&_alid=1751979224&_rdoc=3&_fmt=high&_orig=search&_origin=search&_zone=rslt_list_item&_cdi=6779&_sort=r&_st=13&_docanchor=&view=c&_ct=11541&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=f7d789c702d869ebb39ba6aed9d790e2&searchtype=a) 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$.


