Universal variable to fixed-length random number generators for finite memory sources
G. Seroussi, M.J. Weinberger · 2013
We study variable to fixed-length random number generators (VFRs) that input a variable number of symbols from a finite memory source of arbitrary order and unknown parameters, and output a number uniformly distributed in {0, 1, ..., M-1} for arbitrary fixed M. We further require that the VFR output be uniformly distributed also if an arbitrary bound N is imposed on the input length, at the cost of a positive probability of the VFR terminating with no output (failing). We characterize the essentially unique optimal VFR, which minimizes both the expected input length and the failure probability for all truncation levels N. We precisely characterize, up to an additive constant, the expected input length of the optimal VFR, which includes a model cost term similar to those encountered in universal data compression and universal simulation.