# Largest size for randomness extractor

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) ?

Thanks

• 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. Mar 5 '14 at 19:08
• suppose there's some nontrivial upper bound on $I(X;Y)$ in terms of $\min(H(X), H(Y))$? Mar 5 '14 at 19:56
• @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. Mar 5 '14 at 20:20
• @SureshVenkat I dont understand your comment, are you asking something? Mar 5 '14 at 20:21
• I was suggesting a way to encode dependence of X and Y Mar 6 '14 at 8:16