Given the distribution of a random variable $R$, who do you get a uniform random variable $U$?

Let us say you have a random variable $R$. How would one generate a uniform random variable $U$, with the maximum possible entropy (or infinite entropy, if $R$ has such)? (For simplicity, you may assume that $R$'s sample space is a subset of the real numbers.)

Note: $U$ is essentially gotten by applying a function to $R$. I believe what I am seeking is called a "randomness extractor", specifically one that preserves entropy, and works based a probability distribution.

• And then how are $R$ and $U$ related? I think I'm missing some part of the question. – Alt Mar 22 '14 at 19:37
• Randomness extractors are an entire area of study; I don't think you can just answer such a broad question. Usually in computer science one would assume that R and U are over bitstrings of a certain length, and the answer might depend on for instance the "min entropy" of R. Googling "randomness extractors" turns up some surveys. – usul Mar 22 '14 at 19:54

Here's an idea, assuming that you don't know anything about the distribution of $R$.

Let $(A_i)_{i\in\mathbb{N}}$, $(B_i)_{i\in\mathbb{N}}$ be samples of $R$, i.e. i.i.d. random variables with the distribution of $R$, and set $$C_i = \begin{cases} -1 & \text{if A_i < B_i,} \\ 1 & \text{if A_i > B_i,} \\ 0 & \text{if A_i = B_i.} \ \end{cases}$$ Then let $D_i$ be the $i$-th value of $C_i$ which isn't zero.

By construction, the $C_i$ are mutually independent, and so are thus the $D_i$. By symmetry, $P(C_i = -1) = P(C_i = 1)$, so the $D_i$ are uniformy distributed on $\{-1,1\}$. You can then use the $D_i$ to produce uniformy distributed values on larger probability spaces.

• Is it entropy preserving? (It would have to be the joint entrophies of A and B) – PyRulez Mar 22 '14 at 21:12
• @PyRulez Depends on how exactly you define that. $D_i$ has entropy 1. $R$ might have a larger entropy. But you can always combine multiple $D_i$ into some $F_i$ with higher entropy - but then you'll use more samples of $R$ to generate on $F_i$. – fgp Mar 22 '14 at 22:39
• The point is you don't get unlimited samples. Ideally you are just applying a function to $R$. – PyRulez Mar 23 '14 at 0:02
• @PyRulez I'm pretty certain you need to make some assumptions about $R$ then, at least of you want that function to be computable. – fgp Mar 23 '14 at 10:36