Non-uniform random variate generation

Non-uniform random variate generation or pseudo-random number sampling is the numerical practice of generating pseudo-random numbers (PRN) that follow a given probability distribution. Methods are typically based on the availability of a uniformly distributed PRN generator. Computational algorithms are then used to manipulate a single random variate, X, or often several such variates, into a new random variate Y such that these values have the required distribution. The first methods were developed for Monte-Carlo simulations in the Manhattan project, published by John von Neumann in the early 1950s. For a discrete probability distribution with a finite number n of indices at which the probability mass function f takes non-zero values, the basic sampling algorithm is straightforward. The interval [0, 1) is divided in n intervals [0, f(1)), [f(1), f(1) + f(2)), ... The width of interval i equals the probability f(i). One draws a uniformly distributed pseudo-random number X, and searches for the index i of the corresponding interval. The so determined i will have the distribution f(i). Formalizing this idea becomes easier by using the cumulative distribution function It is convenient to set F(0) = 0. The n intervals are then simply [F(0), F(1)), [F(1), F(2)), ..., [F(n − 1), F(n)). The main computational task is then to determine i for which F(i − 1) ≤ X < F(i). This can be done by different algorithms: Linear search, computational time linear in n. Binary search, computational time goes with log n. Indexed search, also called the cutpoint method. Alias method, computational time is constant, using some pre-computed tables. There are other methods that cost constant time. Generic methods for generating independent samples: Rejection sampling for arbitrary density functions Inverse transform sampling for distributions whose CDF is known Ratio of uniforms, combining a change of variables and rejection sampling Slice sampling Ziggurat algorithm, for monotonically decreasing density functions as well as symmetric unimodal distributions Convolution random number generator, not a sampling method in itself: it describes the use of arithmetics on top of one or more existing sampling methods to generate more involved distributions.

Secondary structure of the human mitochondrial genome affects formation of deletions

Jacques Fellay, Konstantin Popadin, Dmitry Knorre

BackgroundAging in postmitotic tissues is associated with clonal expansion of somatic mitochondrial deletions, the origin of which is not well understood. Such deletions are often flanked by direct nucleotide repeats, but this alone does not fully explain ...

BMC2023

Chaotic microcomb-based parallel ranging

Tobias Kippenberg, Aleksandr Tusnin, Junqiu Liu, Anton Lukashchuk

The intrinsic random amplitude and phase modulation of 40 distinct lines of a microresonator frequency comb operated in the modulation instability regime are used to realize massively parallel random-modulation continuous-wave light detection and ranging, ...

NATURE PORTFOLIO2023

Non-uniform random variate generation

Secondary structure of the human mitochondrial genome affects formation of deletions

Chaotic microcomb-based parallel ranging

Stop Wasting my FLOPS: Improving the Efficiency of Deep Learning Models

Stop Wasting my FLOPS: Improving the Efficiency of Deep Learning Models

Chaotic microcomb-based parallel ranging

Secondary structure of the human mitochondrial genome affects formation of deletions