0
$\begingroup$

I am a bit confused about what it means for a permutation to be k-wise independent.

If I pick a permutation uniformly at random from $\sigma \in S_n$ then isn't it true that for any $k$ integers, $i_1,i_2,..,i_k$ $\in \{1,2,..,n\}$, the numbers $\sigma(i_1),\sigma(i_2),..,\sigma(i_k)$ are k-wise independent?

$\endgroup$
3
$\begingroup$

A permutation cannot be $k$-wise independent. A distribution of permutations is $k$-wise independent if for $\pi$ sampled according to the distribution and any $k$ different indices $i_1,\ldots,i_k$ and $k$ different values $j_1,\ldots,j_k$, the probability that $\pi(i_1)=j_1,\ldots,\pi(i_k)=j_k$ is $1/n(n-1)\cdots(n-k+1)$. (An earlier version of this answer contained a different definition that, while interesting, is not the standard one.)

A $k$-wise independent distribution is $\ell$-wise independent for any $\ell \leq k$, and the uniform distribution over all permutations is trivially $n$-wise independent. A $k$-wise independent distribution is a distribution which "looks like" the uniform distribution when considering at most $k$ points at a time.

It is easy to see that any $k$-wise independent distribution needs to have support $n^{\Omega(k)}$, and conversely, Alon and Lovett construct such distributions with support $n^{O(k)}$.

Here is a simple example of a $1$-wise independent distribution: it is the uniform distribution over the permutations $\pi_1,\ldots,\pi_n$ given by $\pi_t(x) = (x+t) \pmod{n}$. It is easy to check that for all $1 \leq i,j \leq n$, the probability that $\pi_t(i) = j$ is exactly $1/n$.

$\endgroup$
  • $\begingroup$ Thanks! You have any examples of this? Like how does one typically specify such a thing? $\endgroup$ – user6818 Jun 4 '15 at 19:25
  • $\begingroup$ My question can be seen as asking if the uniform distribution over permutations is such a k-wise independent distribution. $\endgroup$ – user6818 Jun 4 '15 at 19:26
  • $\begingroup$ The uniform distribution is $n$-wise independent, and so $k$-wise independent for any $k$. It's more interesting if you have $k$-wise distributions with small support. In fact, the entire point of the definition is that a $k$-wise independent random permutations "looks like" a uniformly random permutation, at least when you only consider $k$ points at a time. $\endgroup$ – Yuval Filmus Jun 4 '15 at 20:25
  • $\begingroup$ By "small support" you mean that the $\pi$ is sampled from a small subset of $S_n$ ? You have examples of such k-wise independent small-support distributions in S_n ? $\endgroup$ – user6818 Jun 4 '15 at 20:28
  • $\begingroup$ How do you prove this? That given a distribution it is $k-$wise independent? $\endgroup$ – user6818 Jun 4 '15 at 21:33

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.