# When is a permutation k-wise independent?

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?

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

• Thanks! You have any examples of this? Like how does one typically specify such a thing? – user6818 Jun 4 '15 at 19:25
• My question can be seen as asking if the uniform distribution over permutations is such a k-wise independent distribution. – user6818 Jun 4 '15 at 19:26
• 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. – Yuval Filmus Jun 4 '15 at 20:25
• 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 ? – user6818 Jun 4 '15 at 20:28
• How do you prove this? That given a distribution it is $k-$wise independent? – user6818 Jun 4 '15 at 21:33