Information-theoretic limits of distributed randomness generation
- Randomness generation has numerous important applications, for example, in statistical sampling, randomized algorithms and cryptography. In this dissertation, we study randomness generation from an information-theoretic point of view. Extending the seminal work of Knuth and Yao on generating random variables from coin flips, we investigate several multi-terminal randomness generation settings. First we consider the distributed generation setting in which Alice and Bob share a common random source, and each of them would like to generate a random variable such that the two random variables follow a prescribed joint distribution. The goal is to minimize the amount of common randomness needed. We show that for log-concave distributions, the amount of common randomness is within a constant gap of the mutual information. The proof uses a novel construction called dyadic decomposition. We then consider the remote generation setting in which Alice, who knows the chosen distribution, wishes to send a message to Bob to enable him to generate a random variable distributed according to this distribution. We design a scheme that applies to any continuous distribution and establish an upper bound on its expected codeword length using dyadic decomposition. Finally, we consider the one-shot channel simulation setting with unlimited common randomness. We strengthen the result by Harsha et al. using a new strong functional representation lemma, and show that it can be applied in designing schemes for one-shot lossy source coding, and providing a simple proof of the Gelfand-Pinsker theorem for channels with state.
|Type of resource
|electronic; electronic resource; remote
|1 online resource.
|Li, Cheuk Ting
|Stanford University, Department of Electrical Engineering.
|El Gamal, Abbas A
|El Gamal, Abbas A
|Statement of responsibility
|Cheuk Ting Li.
|Submitted to the Department of Electrical Engineering.
|Thesis (Ph.D.)--Stanford University, 2017.
- © 2017 by Cheuk Ting Li
Also listed in
Loading usage metrics...