1
$\begingroup$

I am having some trouble proving this.

Let $m,n$ be positive integers, and let $s_1,\dots,s_m$ be (totally) independent random variables distributed uniformly over $\mathbf{F}_2^n$ (binary $n$-uples). For any non-empty subset $M$ of $\{1,\dots,m\}$, let $r_M = \sum_{i\in M} s_i$. Show that the $r_M$ are uniformly and pairwise independently distributed.

It seems "obvious" from the fact that if $M\ne N$, we can let without loss of generality $m \in M\setminus N$, and $r_M$ must be independent from $r_N$ since it "contains" $s_m$, whereas $r_N$ does not, but I can't seem to turn this into a formal proof. Any hints appreciated.

(This occurs in the standard proof of the Goldreich-Levin theorem, but for some reason none of the sources I have been able to get my hands on proves this claim, they are content with the above intuition.)

$\endgroup$

1 Answer 1

0
$\begingroup$

You have no problem with the first part of the problem (that $r_M$ is uniformly distributed on $\mathbb{F}_2$), right? For the second part, I suggest you show that $\text{Prob}\left(r_M=a\text{ and }r_N=b\right)=\frac{1}{4}$ for every $M,N\subseteq \{1,2,\ldots,m\}$ such that $M\neq N$ and for $a,b\in\mathbb{F}_2$, and to do so, you could use conditional expectation: $$\text{Prob}\left(r_M=a\text{ and }r_N=b\right)=\sum_{c\in\mathbb{F}_2}\,\text{Prob}\left(r_M=a\text{ and }r_N=b\,|\,r_{M\cap N}=c\right)\cdot \text{Prob}\left(r_{M\cap N}=c\right)\,.$$ Note that $$\text{Prob}\left(r_M=a\text{ and }r_N=b\,|\,r_{M\cap N}=c\right)=\text{Prob}\left(r_{M\setminus N}=a-c\text{ and }r_{N\setminus M}=b-c\,|\,r_{M\cap N}=c\right)\,.$$ The rest should be easy, as $M\setminus N$, $N\setminus M$, and $M\cap N$ are pairwise disjoint. You do need to be careful when $M\subseteq N$ or $N\subseteq M$, though.

$\endgroup$
1
  • $\begingroup$ Thank you, I will give it some thought. $\endgroup$
    – fkraiem
    Jul 22, 2015 at 5:39

You must log in to answer this question.

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