<p>Suppose we have a source $X$ with min-entropy $\ell$. A <em>randomness extractor</em> 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. </p>

<blockquote>
  <p>What is the largest value of $M$ for which such an  extractor
  $f$ for source $X$ exists ?</p>
</blockquote>

<p>Is there any connection between randomness extractor and the following problem: </p>

<blockquote>
  <p>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) ?</p>
</blockquote>

<p>Thanks</p>

CC BY-SA 3.0
2014-03-05T19:08:10.387Z
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.
Henry Yuen
CC BY-SA 3.0
2014-03-05T19:56:53.057Z
suppose there's some nontrivial upper bound on $I(X;Y)$ in terms of $\min(H(X), H(Y))$?
Suresh Venkat
CC BY-SA 3.0
2014-03-05T20:20:12.930Z
@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.
SAmath
CC BY-SA 3.0
2014-03-05T20:21:48.483Z
@SureshVenkat I dont understand your comment, are you asking something?
SAmath
CC BY-SA 3.0
2014-03-06T08:16:06.623Z
I was suggesting a way to encode dependence of X and Y
Suresh Venkat
CC BY-SA 3.0
2014-03-06T16:32:56.293Z
I think I could find a bound for this. Leftover hash lemma asserts the existence of a randomness extractor for random variable $X$ with  length close to the min entropy of $X$. We can hence say that  $M<H_{\infty}(X)$.
SAmath
<randomness><it.information-theory><pseudorandomness>
Largest size for randomness extractor
SAmath
# Largest size for randomness extractor

(Asked by: username_0 on 2014-03-05)

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

**Tags:** randomness, it.information-theory, pseudorandomness

> **Comments:**
> **username_1**: 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.  
> **username_2**: suppose there's some nontrivial upper bound on $I(X;Y)$ in terms of $\min(H(X), H(Y))$?  
> **username_0**: @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.  
> **username_0**: @SureshVenkat I dont understand your comment, are you asking something?  
> **username_2**: I was suggesting a way to encode dependence of X and Y  
> **username_0**: I think I could find a bound for this. Leftover hash lemma asserts the existence of a randomness extractor for random variable $X$ with  length close to the min entropy of $X$. We can hence say that  $M<H_{\infty}(X)$.  

---

## 0 answers

