A Caltech Library Service

Efficiently Extracting Randomness from Imperfect Stochastic Processes

Zhou, Hongchao and Bruck, Jehoshua (2012) Efficiently Extracting Randomness from Imperfect Stochastic Processes. , Pasadena, CA. (Submitted)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We study the problem of extracting a prescribed number of random bits by reading the smallest possible number of symbols from non-ideal stochastic processes. The related interval algorithm proposed by Han and Hoshi has asymptotically optimal performance; however, it assumes that the distribution of the input stochastic process is known. The motivation for our work is the fact that, in practice, sources of randomness have inherent correlations and are affected by measurement's noise. Namely, it is hard to obtain an accurate estimation of the distribution. This challenge was addressed by the concepts of seeded and seedless extractors that can handle general random sources with unknown distributions. However, known seeded and seedless extractors provide extraction efficiencies that are substantially smaller than Shannon's entropy limit. Our main contribution is the design of extractors that have a variable input-length and a fixed output length, are efficient in the consumption of symbols from the source, are capable of generating random bits from general stochastic processes and approach the information theoretic upper bound on efficiency.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:This work was supported in part by the NSF Expeditions in Computing Program under grant CCF-0832824.
Funding AgencyGrant Number
Subject Keywords:Randomness Extraction, Imperfect Stochastic Processes, Variable-Length Extractors
Record Number:CaltechAUTHORS:20160120-104324682
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:63798
Deposited By: Tony Diaz
Deposited On:20 Jan 2016 20:23
Last Modified:22 Nov 2019 09:58

Repository Staff Only: item control page