1

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$.

  • The procedure based on two consecutive outcomes that you describe does not yield unbiased outcomes. – Did Jul 14 '14 at 09:11
  • @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? – Thomas Klimpel Jul 18 '14 at 00:03
  • 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). – Did Jul 18 '14 at 06:45
  • @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. – Thomas Klimpel Jul 18 '14 at 08:34

1 Answers1

1

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 .