2
$\begingroup$

I have a sequence of numbers $x_1, x_2, \dots, x_n, \dots \in \mathbb{R}$ I would like to extract fair bits from that sequence.

My first thought was to use the Von Neumann extractor. For a sequence of 0 and 1,

  • divide sequence into pairs
  • eliminate all occurrences of 00 and 11
  • apply transformation 01 → 1 and 10 → 0

This produces a sequence of fair bits from biased bits *even if you do not know the bias $p = \mathbb{P}[x_i = 1]$ as long as your sequence is

  • a Bernoulli trial
  • independently distributed
  • identially distributed

The sequence of numbers I have is the hourly readings from a sensor, so it exhibits cyclic behavior every 24 hours + every week. If I compute the expected value over time, it may be possible to subtract out the daily and weekly cycles leaving sequence of loosely self-correlated real numbers.

How can I extract randomness from here in a simple way?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Presumably these are actually rational numbers? $\endgroup$ – usul May 25 '14 at 1:06
  • 2
    $\begingroup$ You'll need to make some assumption about how these numbers are generated ... how independent is each number given the previous ones? and so on. $\endgroup$ – usul May 25 '14 at 1:08
  • $\begingroup$ @usul to simplify even further, these are independent bits (just 0 and 1) but they are not identically distributed. $\endgroup$ – john mangual May 25 '14 at 11:55
  • $\begingroup$ If $p_i$ is the bias of the $i$th coin, I conjecture that you'll need to assume $0<a<p_i<b<1$ for all $i$. Further, you'll probably need to consider contiguous runs of flips of length inversely proportional to $1-b+a$. $\endgroup$ – Aryeh Mar 31 '17 at 11:17
-1
$\begingroup$

First, it depends how the quantization of the real values is performed. Using 8 bits can be really different from using 16 for example.

Assuming that a fixed number of bits is chosen, hash functions are a good and simple way to extract randomness.

Universal Hash Functions are families of hash functions that can be securely used in this context (not all hash functions are suitable for this).

| cite | improve this answer | |
$\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.