CaltechAUTHORS
  A Caltech Library Service

Efficiently Generating Random Bits from Finite State Markov Chains

Zhao, Hongchao and Bruck, Jehoshua (2010) Efficiently Generating Random Bits from Finite State Markov Chains. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:2010.ETR102

[img]
Preview
PDF
See Usage Policy.

314Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:2010.ETR102

Abstract

The problem of random number generation from an uncorrelated random source (of unknown probability distribution) dates back to von Neumann's 1951 work. Elias (1972) generalized von Neumann's scheme and showed how to achieve optimal efficiency in unbiased random bits generation. Hence, a natural question is what if the sources are correlated? Both Elias and Samuelson proposed methods for generating unbiased random bits in the case of correlated sources (of unknown probability distribution), specifically, they considered finite Markov chains. However, their proposed methods are not efficient or have implementation difficulties. Blum (1986) devised an algorithm for efficiently generating random bits from degree-2 finite Markov chains in expected linear time, however, his beautiful method is still far from optimality on information-efficiency. In this paper, we generalize Blum's algorithm to arbitrary degree finite Markov chains and combine it with Elias's method for efficient generation of unbiased bits. As a result, we provide the first known algorithm that generates unbiased random bits from an arbitrary finite Markov chain, operates in expected linear time and achieves the information-theoretic upper bound on efficiency.


Item Type:Report or Paper (Technical Report)
Additional Information:This work was supported in part by the NSF Expeditions in Computing Program under grant CCF-0832824.
Group:Parallel and Distributed Systems Group
Subject Keywords:Random sequence, Random bits generation, Markov chain
Record Number:CaltechPARADISE:2010.ETR102
Persistent URL:http://resolver.caltech.edu/CaltechPARADISE:2010.ETR102
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26133
Collection:CaltechPARADISE
Deposited By: Imported from CaltechPARADISE
Deposited On:16 Jun 2010
Last Modified:26 Dec 2012 13:54

Repository Staff Only: item control page