Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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$.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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