Sampling from a Discrete Distribution While Preserving Monotonicity

This article describes a cutpoint sampling method for efficiently sampling from an n-point discrete distribution that preserves the monotone relationship between a uniform deviate and the random variate it generates. This property is useful for developing a sampling plan to reduce variance in a Monte Carlo or simulation study. The expected number of comparisons with this method is derived and shown to be bounded above by (m + n ?1)/n, where m denotes the number of cut-points. The alias sampling method, which is regarded as the most efficient table sampling technique, generally lacks the monotone property and requires 2n storage locations, whereas the proposed cutpoint sampling method requires m + n storage locations. The article describes two modifications for cases in which n is large and possibly infinite. It is shown that circumstances arise in which the cutpoint method requires fewer comparisons on average than the alias method does for exactly the same space requirement. The article also describes an algorithm to implement the proposed method.