2
$\begingroup$

Definition: Distribution $D$ on $\{0,1\}^n$ is called $k$-independent if for every random variable $X$ with distribution $D$ and for all $i_1, \dots, i_k \in \{1,2,\dots,n\}$ random variable $X_{i_1,\dots, i_k}$ has distribution $U_k$ (uniform distribution on $\{0,1\}^k$).

Problem: Consider probabilistic algorithm $A$ that has oracle access to the input of length $n$. It means that algorithm $A$ can adaptively request $k$ bits of input (in more detail, $A$ can request one bit, then based on the oracle answer request another bit and repeat it not more than $k$ times). Prove that if $D$ is $k$-independent distribution than $Pr_{x \sim D} [A(x) = 1] = Pr_{x \sim U_n}[A(x) = 1] $

First of all, I don't understand how adaptivity can potentially help the algorithm to distinguish the uniform distribution from a $k$-independent one. The second question is as in the problem.

$\endgroup$
9
  • $\begingroup$ "I don't understand how adaptivity can potentially help Algorithm to distinguish uniformal distribution from k-independent" - I think it's the opposite. The point is that the algorithm can't distinguish between $D$ and $U_n$. $\endgroup$
    – user114966
    Mar 17 at 20:45
  • $\begingroup$ Adaptive algorithms are more powerful than non-adaptive ones. The problem asks you to show that even adaptive algorithms cannot distinguish between $k$-independent distributions and uniform ones, as long as they make at most $k$ queries. $\endgroup$ Mar 17 at 20:55
  • $\begingroup$ Try proving this first for non-adaptive algorithms, where it follows almost immediately from the definition. The argument for adaptive algorithms is along similar lines, but requires a bit more care. $\endgroup$ Mar 17 at 20:55
  • 2
    $\begingroup$ You need to show that the algorithm runs the same on both distributions. Try to write the proof in complete detail, from first principles. When you write the proof, don’t use any intuitive shortcuts. Be meticulous. $\endgroup$ Mar 17 at 21:57
  • 1
    $\begingroup$ If $X=x_1,x_2,x_3,x_4,x_5$ then e.g. $X_{1,3}=x_1,x_3$ $\endgroup$
    – Ariel
    Mar 18 at 6:44
1
$\begingroup$

A distribution $X=(X_1,\ldots,X_n)$ on $\{0,1\}^n$ is $k$-independent if for every $k$ indices $i_1<\dots<i_k$ and bits $b_1,\ldots,b_k \in \{0,1\}$, $$ \Pr[X_{i_1} = b_1, \ldots, X_{i_k} = b_k] = \frac{1}{2^k}. $$ Equivalently, the marginal distribution of $X_{i_1},\ldots,X_{i_k}$ is the uniform distribution on $\{0,1\}^k$. A simple induction shows that a $k$-independent distribution is $\ell$-independent for all $\ell \leq k$.

More generally, two distributions $X,Y$ on $\{0,1\}^n$ are $k$-indistinguishable if for every $k$ indices $i_1<\dots<i_k$ and bits $b_1,\ldots,b_k \in \{0,1\}$, $$ \Pr[X_{i_1} = b_1, \ldots, X_{i_k} = b_k] = \Pr[Y_{i_1} = b_1, \ldots, Y_{i_k} = b_k]. $$ Equivalently, the marginal distributions of $X_{i_1},\ldots,X_{i_k}$ and $Y_{i_1},\ldots,Y_{i_k}$ are identical. If $X,Y$ are $k$-indistinguishable then they are $\ell$-indistinguishable for all $\ell \leq k$. A distribution $X$ is $k$-independent if $X,U$ are $k$-indistinguishable, where $U$ is the uniform distribution on $\{0,1\}^n$.

Now suppose that $A$ is a randomized algorithm which queries a black-box vector $(z_1,\ldots,z_n)$ in at most $k$ places. Such an algorithm is sometimes called a randomized decision tree, and $k$ is its query complexity. We would like to show that if $X,Y$ are $k$-indistinguishable then the distributions of $A(X_1,\ldots,X_n)$ and $A(Y_1,\ldots,Y_n)$ are identical.

The idea is that at any point in time, $A$ decides what to do next — which coordinate to query, or what value to return — based on the coordinates $i_1,\ldots,i_\ell$ seen so far, where $\ell \leq k$. Since $X,Y$ are $k$-indistinguishable, the distributions of $X_{i_1},\ldots,X_{i_\ell}$ and $Y_{i_1},\ldots,Y_{i_\ell}$ are identical, and so the distribution of $A$'s next move is identical in both cases.

Expressing this idea more formally would require formalizing the definition of a randomized decision tree, and is beyond the scope of this answer; but I encourage the reader to do that, if they are in the possession of such a definition (or can come up with one on their own).

$\endgroup$
1
  • $\begingroup$ Thank you for complete answer! If it Is not very difficult, could you please recommend some literature on randomized decision trees? $\endgroup$
    – Alexander
    Mar 18 at 7:23
2
$\begingroup$

$$ \Pr[A(x)=1]=\sum\limits_{i_1,...,i_j \\0\le j\le k} \Pr[A(x)=1 | \text{A requested bits $i_1,...,i_j$}]\cdot\Pr[\text{A requested bits $i_1,...,i_j$}]=\sum\limits_{i_1,...,i_j \\0\le j\le k} \Pr\left[A\left(x_{i_1,i_2,...,i_j}\right)=1\right]\cdot\Pr[\text{A requested bits $i_1,...,i_j$}] $$

Here you already see that if $A$ is non adaptive this becomes immediate, as only one summand is non zero, and $A(x_{i_1},...,x_{i_j})$ has the same distribution as $A(U_j)$. If one considers randomized $A$ then change this argument to claim that the bits requested do not depend on the input, and thus the probability of requesting a certain set of indices does not depend on the distribution of the input. For the adaptive case, try the following. Denote by $a_i$ the index of the $i'th$ bit requested by $A$.

$$ \Pr[\text{A requested bits $i_1,...,i_j$}]=\Pr\left[\bigwedge\limits_{l=1}^j a_l=i_l\right]=\Pr\left[a_j=i_j \Bigg| \bigwedge\limits_{l=1}^{j-1}a_l=i_l\right]\cdot \Pr\left[a_{j-1}=i_{j-1} \Bigg| \bigwedge\limits_{l=1}^{j-2}a_l=i_l\right]\cdot...\cdot\Pr\left[a_2=i_2 |a_1=i_1\right]\cdot\Pr[a_1=i_1]. $$

Note that in each term the probability is both over the internal randomness of $A$ and the randomness of the input $x$ (which is implicit in the above). You can now prove by induction that in each multiplier, you can switch $x$ with a uniformly distributed string. More formally, for all $1\le l\le j$, the random variable $a_l$ conditioned on $a_1,...,a_{l-1}$ has the same distribution as $a_l$ when $x$ is uniformly random. Finally, plug this back to the above sum, and now every occurence of the input $x$ was switched by a uniformly distributed string.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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