1
$\begingroup$

Let $X_i$ with $i\in\mathbb N$ be a sequence of independent 6-ary random variables with distribution $\operatorname{Pr}(X_i=e)=p^e_i$ where $e\in\{1,2,3,4,5,6\}$ and $\sum_{e=1}^6p^e_i=1$. Let's assume further that $\frac19\leq p^e_i\leq\frac29$ and $\left|\bigcup_i\{(p^1_i,p^2_i,\ldots,p^6_i)\}\right|\leq200$, and that this is more or less all we know about our physical random source. The physical random source I have in mind here is the Dice-O-Matic.

For $\epsilon>0$, can we transform the sequence $X_i$ into a sequence $Y_j$ of independent binary random variables with $\frac12-\epsilon<\operatorname{Pr}(Y_j=1)<\frac12+\epsilon$?
Or can the $Y_j$ at least be approximatively independent, i.e can we achieve for all $K \subset \mathbb N\setminus\{j\}$ with $|K|<\infty$ and all $y_k\in\{0,1\}$ that $\frac12-\epsilon<\operatorname{Pr}(Y_j=1|Y_k=y_k \ k\in K)<\frac12+\epsilon$ ?

I'm thinking about the same type of transformations as in a previous question here. For example if $\left|\bigcup_i\{(p^1_i,p^2_i,\ldots,p^6_i)\}\right|=1$, we could just take two consecutive outcomes of $X_i$ together, answer $1$ if first is $\leq3$ and second is $\geq4$, answer $0$ if first is $\geq4$ and second is $\leq3$, and otherwise just discard the two outcomes repeat the game again with the next new consecutive outcomes of $X_i$ until we answer either $0$ or $1$.


In practice, we would probably use the physical random source to generate seeds for one or more deterministic random number generators, which would we then use to generate a certain "safe" number of random numbers, before we reinitialize the generator with a new seed. Because these random numbers can never be perfectly independent, the question has been modified to also allow approximatively independent $Y_j$.

$\endgroup$
  • $\begingroup$ The procedure based on two consecutive outcomes that you describe does not yield unbiased outcomes. $\endgroup$ – Did Jul 14 '14 at 9:11
  • $\begingroup$ @Did You mean I made a mistake in my description of the procedure? Or you mean you simply don't believe that such a can procedure work? Or is it just that you can't recognize the well known situation (produce unbiased random bits with the help of a single biased coin) behind my complicated and overly formal description? $\endgroup$ – Thomas Klimpel Jul 18 '14 at 0:03
  • $\begingroup$ Bis repetita: if one "take(s) two consecutive outcomes of $X_i$ (i.e. $X_{2j}$ and $X_{2j+1}$) together, (and one) answer(s) $1$ if both are $\leq3$ or both are $\geq4$, and answer $0$ otherwise", the resulting bit is not unbiased (except if the sequence one started with was already unbiased). $\endgroup$ – Did Jul 18 '14 at 6:45
  • $\begingroup$ @Did Thanks, now I see where I made a mistake in the description of the method. Should be fixed now. This also answers part of my initial confusion, i.e. why I asked this sort of questions in the first place. $\endgroup$ – Thomas Klimpel Jul 18 '14 at 8:34
1
$\begingroup$

You can get a near truly random bit from two pretty weak random sources. At least that's how Lance Fortnow described the results from Explicit Two-Source Extractors and Resilient Functions by Eshan Chattopadhyay, and David Zuckerman .

$\endgroup$

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.