Suppose we have a source $X$ with min-entropy $\ell$. A randomness extractor is defined as a function $f$ which satisfies the total variation $||f(X, R)-U_M||_{TV}\leq \epsilon$ where $R$ is an external randomness and $U_M$ is a uniform random variable over a set of $M$ points.

What is the largest value of $M$ for which such an extractor $f$ for source $X$ exists ?

Is there any connection between randomness extractor and the following problem:

Given two dependent random variables $X$ and $Y$, how many bits we can extract from $Y$ that are almost independent from $X$ (where the independence is measured via total variational distance) ?


  • 1
    $\begingroup$ In general, 0. If $X$ is identical to $Y$, then there's no deterministic extraction procedure that will produce uncorrelated random bits relative to $X$. If you use a seed $S$ of length $d$, then you will get at most $d$ bits that are independent of $X$ (namely, simply output the seed). Thus you'll need some assumption on the dependence of $X$ on $Y$ to get a non-trivial statement. $\endgroup$
    – Henry Yuen
    Mar 5 '14 at 19:08
  • $\begingroup$ suppose there's some nontrivial upper bound on $I(X;Y)$ in terms of $\min(H(X), H(Y))$? $\endgroup$ Mar 5 '14 at 19:56
  • $\begingroup$ @HenryYuen, Thanks for the comment, but could you please explain what kind of assumption of the dependence of $X$ and $Y$? to be honest what I want is exactly the conditions that we might impose on $X$ and $Y$ such that the length of extracted bits is maximum, particularly the connection of this with maximal correlation or common information. $\endgroup$
    – SAmath
    Mar 5 '14 at 20:20
  • $\begingroup$ @SureshVenkat I dont understand your comment, are you asking something? $\endgroup$
    – SAmath
    Mar 5 '14 at 20:21
  • $\begingroup$ I was suggesting a way to encode dependence of X and Y $\endgroup$ Mar 6 '14 at 8:16

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.