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.

  • $\begingroup$ And then how are $R$ and $U$ related? I think I'm missing some part of the question. $\endgroup$ – Alt Mar 22 '14 at 19:37
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ Is it entropy preserving? (It would have to be the joint entrophies of A and B) $\endgroup$ – PyRulez Mar 22 '14 at 21:12
  • $\begingroup$ @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$. $\endgroup$ – fgp Mar 22 '14 at 22:39
  • $\begingroup$ The point is you don't get unlimited samples. Ideally you are just applying a function to $R$. $\endgroup$ – PyRulez Mar 23 '14 at 0:02
  • $\begingroup$ @PyRulez I'm pretty certain you need to make some assumptions about $R$ then, at least of you want that function to be computable. $\endgroup$ – fgp Mar 23 '14 at 10:36

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.