When looking for a link in a recent post, I came across Richard Brent’ arXival of historical comments on George Forsythe’s last paper (in 1972). Which is about the Forsythe-von Neumann approach to simulating exponential variates, covered in Luc Devroye’s Non-Uniform Random Variate Generation in a special section, Section 2 of Chapter 4, is about generating a random variable from a target density proportional to g(x)exp(-F(x)), where g is a density and F is a function on (0,1). Then, after generating a realisation x⁰ from g and computing F(x⁰), generate a sequence u¹,u²,… of uniforms as long as they keep decreasing, i.e., F(x⁰) >u¹>u²>… If the maximal length k of this sequence is odd, the algorithm exists with a value x⁰ generated from g(x)exp(-F(x)). Von Neumann (1949) treated the special case when g is constant and F(x)=x, which leads to an Exponential generator that never calls an exponential function. Which does not make the proposal a particularly efficient one as it rejects O(½) of the simulations. Refinements of the algorithm lead to using on average 1.38 uniforms per Normal generation, which does not sound much faster than a call to the Box-Muller method, despite what is written in the paper. (Brent also suggests using David Wallace’s 1999 Normal generator, which I had not encountered before. And which I am uncertain is relevant at the present time.)
Archive for random number generator
George Forsythe’s last paper
Posted in Books, Statistics, University life with tags George Forsythe, John von Neumann, last paper, random number generator on May 25, 2018 by xi'anmore random than random!
Posted in Books, Kids, pictures, Statistics with tags Charles Dickens, cross validated, Oliver Twist, random number generator, random variates, randomness, xkcd on December 8, 2017 by xi'an
A revealing question on X validated the past week was asking for a random generator that is “more random” than the outcome of a specific random generator, à la Oliver Twist:
The question is revealing of a quite common misunderstanding of the nature of random variables (as deterministic measurable transforms of a fundamental alea) and of their maybe paradoxical ability to enjoy stability or predictable properties. And much less that it relates to the long-lasting debate about the very [elusive] nature of randomness. The title of the question is equally striking: “Random numbers without pre-specified distribution” which could be given some modicum of meaning in a non-parametric setting, still depending on the choices made at the different levels of the model…
RNG impact on MCMC [or lack thereof]
Posted in Books, R, Statistics, Travel, University life with tags Donald Knuth, George Marsaglia, GNU C library, MCM 2017, Montréal, R, random number generator, Super-duper on July 13, 2017 by xi'an
Following the talk at MCM 2017 about the strange impact of the random generator on the outcome of an MCMC generator, I tried in Montréal airport the following code on the banana target of Haario et al. (1999), copied from Soetaert and Laine and using the MCMC function of the FME package:
library(FME)
Banana <- function (x1, x2) {
return(x2 - (x1^2+1)) }
pmultinorm <- function(vec, mean, Cov) {
diff <- vec - mean
ex <- -0.5*t(diff) %*% solve(Cov) %*% diff
rdet <- sqrt(det(Cov))
power <- -length(diff)*0.5
return((2.*pi)^power / rdet * exp(ex)) }
BananaSS <- function (p) {
P <- c(p[1], Banana(p[1], p[2]))
Cov <- matrix(nr = 2, data = c(1, 0.9, 0.9, 1))
N=1e3
ejd=matrix(0,4,N)
RNGkind("Mars")
for (t in 1:N){
MCMC <- modMCMC(f = BananaSS, p = c(0, 0.7),
jump = diag(nrow = 2, x = 5), niter = 1e3)
ejd[1,t]=mean((MCMC$pars[-1,2]-MCMC$pars[1,2])^2)}
since this divergence from the initial condition seemed to reflect the experiment of the speaker at MCM 2017. Unsurprisingly, no difference came from using the different RNGs in R (which may fail to contain those incriminated by the study)…
quantic random generators
Posted in Books, Statistics with tags Bell inequality, hardware random generator, Nature, quantum computers, quantum physics, random number generator on January 5, 2017 by xi'an
“…the random numbers should be unpredictable by any physical observer, that is, any observer whose actions are constrained by the laws of physics.”
A review paper in Nature by Acin and Masanes is the first paper I ever read there about random number generation! The central debate in the paper is about the notion of randomness, which the authors qualify as above. This seems to exclude the use of “our” traditional random number generators, although I do not see why they could not be used with an unpredictable initialisation, which does not have to be done according to a specific probability distribution. The only thing that matters is unpredictability.
“…the standard method for certifying randomness consists of running statistical tests1 on sequences generated by the device. However, it is unclear what passing these tests means and, in fact, it is impossible to certify with finite computational power that a given sequence is random.”
The paper supports instead physical and quantum devices. Justified or certified by [violations of] the Bell inequality, which separates classic from quantum. Not that I know anything about this. Or that I can make sense of the notations in the paper, like
which is supposed to translate that the bits are iid Uniform and independent of the environment. Actually, I understood very little of the entire review paper, which is quite frustrating since this may well be the only paper ever published in Nature about random number generation!
“…a generation rate of 42 random bits after approximately one month of measurements, was performed using two entangled ions in two traps at 1-m distance.”
It is also hard to tell whether or not this approach to quantum random number generation has foreseeable practical consequences. There already exist QRNGs, as shown by this example from ANU. And this much more readable review.
random number generation
Posted in Books, Kids, pictures with tags Ayn Rand, objectivism, random number generator, randomness, simulation on October 27, 2013 by xi'an
