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

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

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

CC BY-SA 3.0
2017-03-30T20:50:36.753Z
2017-03-30T20:50:36.753Z
Vladi
<p>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.  </p>

<hr>

<p>My first thought was to use the <a href="http://stat-www.berkeley.edu/~peres/mine/vn.pdf" rel="nofollow">Von Neumann</a> extractor.  For a sequence of <strong>0</strong> and <strong>1</strong>,</p>

<ul>
<li>divide sequence into pairs</li>
<li>eliminate all occurrences of <strong>00</strong> and <strong>11</strong></li>
<li>apply transformation <strong>01</strong> &#8594; <strong>1</strong> and <strong>10</strong> &#8594; <strong>0</strong></li>
</ul>

<p>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</p>

<ul>
<li>a Bernoulli trial</li>
<li>independently distributed</li>
<li>identially distributed</li>
</ul>

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

<p>How can I extract randomness from here in a simple way?  </p>

CC BY-SA 3.0
2014-05-25T01:06:45.860Z
Presumably these are actually rational numbers?
usul
CC BY-SA 3.0
2014-05-25T01:08:55.990Z
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.
usul
CC BY-SA 3.0
2014-05-25T11:55:46.780Z
@usul to simplify even further, these are independent bits (just `0` and `1`) but they are **not** identically distributed.
john mangual
CC BY-SA 3.0
2017-03-31T11:17:01.643Z
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$.
Aryeh
<pr.probability><randomness>
randomness extraction of real valued sequences of numbers
john mangual
# randomness extraction of real valued sequences of numbers

(Asked by: username_0 on 2014-05-24)

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](http://stat-www.berkeley.edu/~peres/mine/vn.pdf) 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?

**Tags:** pr.probability, randomness
> **Comments:**
> **username_1**: Presumably these are actually rational numbers?  
> **username_1**: 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.  
> **username_0**: @usul to simplify even further, these are independent bits (just `0` and `1`) but they are **not** identically distributed.  
> **username_2**: 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$.  

---

## 1 answers

### Answer by username_3 on 2017-03-30. Score: -1

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


---

