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 longlasting debate about the very [elusive] nature of randomness. The title of the question is equally striking: “Random numbers without prespecified distribution” which could be given some modicum of meaning in a nonparametric setting, still depending on the choices made at the different levels of the model…
Archive for random number generator
more 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'anRNG 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, Superduper on July 13, 2017 by xi'anFollowing 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 tests^{1} 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 1m 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'anatmospheric random generator?!
Posted in Books, Mountains, pictures, Statistics, Travel with tags Mersenne twister, Patagonia, PHP, rand, random number generator, randomness, surfing, The Cleanest Line on April 10, 2012 by xi'anAs I was glancing through The Cleanest Line, (the outdoor clothing company) Patagonia‘s enjoyable—as long as one keeps in mind Patagonia is a company, although with commendable ethical and ecological goals—blog, I came upon this entry “And the Winner of “Chasing Waves” is …” where the name of the winner of the book Chasing Wave was revealed. (Not that I am particularly into surfing…!) The interesting point to which I am coming so circumlocutory (!) is that they use a random generator based on atmospheric noise to select the winner! I particularly like the sentence that the generator “for many purposes is better than the pseudorandom number algorithms typically used in computer programs”. For which purpose exactly?!
Now, to be (at least a wee) fair, the site of random.org contains an explanation about the quality of their generator. I am however surprised by the comparison they run with the rand() function from PHP on Microsoft Windows, since it produces a visible divergence from uniformity on a bitmap graph… Further investigation led to this explanation of the phenomenon, namely the inadequacy of the PHP language rather than of the underlying (pseudo)random generator. (It had been a while since I had a go at this randomness controvery!)
resampling and [GPU] parallelism
Posted in Statistics, University life with tags GPU, particle MCMC, Raftery and Lewis' number of iterations, random number generator, resampling, stratified resampling, systematic resampling on March 13, 2012 by xi'anIn a recent note posted on arXiv, Lawrence Murray compares the implementation of resampling schemes for parallel systems like GPUs. Given a system of weighted particles, (x_{i},ω_{i}), there are several ways of drawing a sample according to those weights:
 regular multinomial resampling, where each point in the (new) sample is one of the (x_{i},ω_{i}), with probability (x_{i},ω_{i}), meaning there is a uniform generated for each point;
 stratified resampling, where the weights are added, divided into equal pieces and a uniform is sampled on each piece, which means that points with large weights are sampled at least once and those with small weights at most once;
 systematic resampling, which is the same as the above except that the same uniform is used for each piece,
 Metropolis resampling, where a Markov chain converges to the distribution (ω_{1},…, ω_{P}) on {1,…,P},
The three first resamplers are common in the particle system literature (incl. Nicolas Chopin’s PhD thesis), but difficult to adapt to GPUs (and I always feel uncomfortable with the fact that systematic uses a single uniform!), while the last one is more unusual, but actually wellfitted for a parallel implementation. While Lawrence Murray suggests using Raftery and Lewis’ (1992) assessment of the required number of Metropolis iterations to “achieve convergence”, I would instead suggest taking advantage of the toric nature of the space (as represented above) to run a random walk and wait for the equivalent of a complete cycle. In any case, this is a cool illustration of the new challenges posed by parallel implementations (like the development of proper random generators).
GPUs in computational statistics
Posted in pictures, Statistics, Travel with tags Coventry, CPU, GPU, haggis, random number generator, Robert Burns, Stilton, University of Warwick on January 27, 2012 by xi'anThe workshop in Warwick yesterday went on very quickly! The room was packed. The three first talks were by myself, Christophe and Pierre, so less about GPUs and more about simulation techniques which could benefit from or even require implementation on GPUS. (I did manage to have complete slides this time… More seriously, Christophe’s talk set me thinking on the issue of estimating the likelihood function in ways different (?) from the one used in ABC.) The second half was more novel for me, in that the three talks went into the computing and computer aspects of GPUS, with Chris Holmes doing sparse [Lassolike] regression on a scale otherwise [i.e. w/o GPUs] impossible, Chris [fourth Chris in the list of speakers!] Barnes explaining ABC for molecular biology and design (a point I plan to discuss on a later post), with even more details about the architecture and programming of GPUs, and Michael Stumpf delivering a grand finale, with essentially three talks into one: network analysis (incl. terrific movie bits incorporated within the beamer slides!), GPUs vs. CPUs and older alternatives, and random generators on GPU, commenting on a recent paper by Salmon et al. (SC, 2011) and showing that true gains in efficiency from using GPUs involved a heavy involvement into the hardware structure… A very exciting day followed by Stilton cheese degustation and haggis (if not poems) to celebrate Burns’ night!

Some hae meat and canna eat,
And some wad eat that want it;
But we hae meat, and we can eat,
And sae let the Lord be thankit.