2
$\begingroup$

A distribution $D$ on $\{0,1\}^n$ is $k$-wise independent if any $k$ of the underlying $n$ random variables are independent and each is uniformly distributed. To me this looks similar in spirit to $D$ having $\textit{min-entropy}$ $k$.

Is there any formal relation between $k$-wise independence of a distribution and its min-entropy?

|cite|improve this question
$\endgroup$
  • 9
    $\begingroup$ $k$-wise independence implies the min-entropy is at least $k$. on the other hand it's pretty easy to come up with distributions that are nowhere near $k$-wise independent and have min entropy $k$. $\endgroup$ – Sasho Nikolov Mar 7 '15 at 2:49

Your Answer

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

Browse other questions tagged or ask your own question.