Probabilistic adaptive algorithm that can explore only $k$ bits of input can’t distinguish $k$-independent distribution from uniform

Question

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.

Answer 1

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

Answer 2

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