Exact Sampling And Prefix Distributions

Abstract

This thesis explores some new means to generate random numbers without incurring any numerical inaccuracies along the way. In the context of continuous distributions this leads to the discussion of prefix distributions – discrete distributions that fully capture a continuous distribution by describing their initial digits. These are first studied graphically, then analytically, which also leads to a general examination of the behavior of the distribution of trailing digits of continuous distributions. Finally, some slightly novel, related results from the theory of computation are presented.