# Analogue of $k$-wise independence for other distributions than uniform

I am looking for the name of the following notion (in order to look it up for myself), and possibly pointers to the corresponding literature.

Let $$D$$ be a fixed distribution over $$\{0,1\}^n$$, and $$1\leq k\leq n$$ a fixed integer. A random variable $$X$$ over $$\{0,1\}^n$$ is said to be $$(k,D)$$-something if all size-$$\ell$$ marginals of $$X$$, for $$\ell\leq k$$, match those of $$D$$.

In particular, for $$D$$ product distribution (and, in most derandomization literature I have seen, actually for $$D$$ uniform), this is $$k$$-wise independence. I am looking for $$D$$ non-uniform, however -- for instance, $$D$$ being the distribution of the $$n$$ bits indicators obtained when choosing a subset of $$[n]$$ of size exactly $$n/2$$.

Does something have a name?

• Isn't this just "k-wise independence"?! – Jeffε Apr 10 at 21:01
• @Jeffε well, no. Is it? First, $k$-wise independence" is basically used for "$k$-wise uniform independence*" most of the time. This notwithstanding, as my last example in particular illustrates, I am considering distributions where the coordinates are not necessarily independent. – Clement C. Apr 10 at 23:20
• Sorry, I see the difference now, but no, [adjective] independence does not imply anything about uniformity. – Jeffε Apr 11 at 5:15
• @Jeffε Sorry, I should have been more precise. It's true that there ins no implication of uniformity in general; however, for derandomization (which is my end goal here), I am under the impression that, by and large, "$k$-wise independent" and "\$k wise independent uniform" are used interchangeably. See, e.g., a search for "derandomization k-wise" on Google, or for instance Chapater 3, Definition 3.21 in this monongraph, or most lecture notes (section 2), evn [...] – Clement C. Apr 11 at 6:56
• [...] a search on this very website. Hence my conflating the two in the question... Updating the question to make that clear. – Clement C. Apr 11 at 6:56

$$D$$ being the distribution of the $$n$$ bits indicators obtained when choosing [uniformly at random] a subset of $$[n]$$ of size exactly $$n/2$$.
Let more generally $$m$$ be any integer dividing $$n$$, and $$D_{n,m}$$ be the uniform distribution over all $$m$$-equipartitions of $$[n]$$. (The above corresponds to $$m=2$$.)
Since drawing such an $$m$$-equipartition is equivalent to (i) taking a deterministic partition of that sort over $$[n]$$ and (ii) applying it to a u.a.r. permutation of $$[n]$$, any family $$\mathcal{C}$$ of $$k$$-wise independent partitions of $$[n]$$ yields a $$(k,D_{n,m})$$-something random variable $$X$$ samplable with $$\log|\mathcal{C}|$$ u.a.r. bits.
Unfortunately, no exact (non-trivial) family of $$k$$-wise independent permutations is known to exist for $$k\geq 4$$, even non-constructively, as far as I know. So then one would have to settle with $$k$$-wise almost independent permutations (and see how the approximation propagates).