Achievable key rates for universal simulation of random data with respect to a set of stati.pdfVIP

Achievable Key Rates for Universal Simulation of Random Data with Respect to a Set of Statistical Tests Neri Merhav Information Theory Research Group HP Laboratories Palo Alto HPL-2002-271 September 30th , 2002* E-mail: merhav@ee.technion.ac.il random number generators, random process simulation,m statistical tests, typical sequences We consider the problem of universal simulation of an unknown source from a certain parametric family of discrete memoryless sources, given a training vector X from that source and given a limited budget of purely random key bits. The goal is to generate a sequence of random vectors {Yi}, all of the same dimension and the same probability laws as the given training vector X, such that a certain, prescribed set of M statistical tests will be satisfied. In particular, for each statistical test, it is required that for a certain event, Eλ, 1 ≤ λ ≤ M, the relative frequency of occurrence of Eλ in Y1Y2...YN would converge, as N → ∞, to a random variable (depending on X), that is typically as close as possible to the expectation of the indicator function 1Eλ (X) of Eλ with respect to (w.r.t.) the true unknown source, namely, to the probability of the event Eλ. We characterize the minimum key rate needed for this purpose and demonstrate how this minimum can be approached in principle. * Internal Accession Date Only Approved for External Publication Department of Electrical Engineering, Technion – Israel Institute of Technology, Technion City, Haifa 32000, Israel ? Copyright Hewlett-Packard Company 2002 Achievable Key Rates for Universal Simulation of Random Data with Respect to a Set of Statistical Tests Neri Merhav September
  Department of Electrical Engineering Technion Israel Institute of Technology Technion City
Haifa 
ISRAEL merhavee
technion
ac
il Abstract We consider the