Transformations of probability distributions
METADATA ONLY
Loading...
Author / Producer
Date
2024-09-04
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
Almost all of computer science is concerned with transformations of information in the form of strings. We initiate the study of a neglected transformation type, namely transformations between probability distributions. We begin by examining the deceivingly simple-looking case of Bernoulli distributions and procedures to transform them. A p-coin is a coin that, whenever tossed, lands heads up with probability p and tails up with probability 1−p. A neat trick due to von Neumann allows us to simulate a 1/2-coin with any p-coin for an arbitrary unknown p∈(0,1). We show how to apply this trick to simulate a q-coin for an arbitrary computable q∈(0,1). In contrast, it is impossible to simulate a q-coin with a noncomputable q. More generally, we are interested in what transformations between probability distributions are feasible. Is it possible to simulate a p/2-coin with a p-coin for unknown p? How about 2p or p2? We attempt to characterize the feasible transformations. For example, we show how to transform a p-coin into an f(p)-coin where any finite number of pairs (pi,f(pi)) of non-zero, non-one probabilities is prescribed, and that it is impossible to do the same for an infinite number of pairs. We also examine which probability distributions are feasible to approximate to arbitrary precision, showing that this is impossible for discontinuous ones but feasible for most but not all remaining ones.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
1018
Pages / Article No.
114786
Publisher
Elsevier