Monte Carlo Method: Quasi vs. Pseudo-random

Although neural networks is taking the stage of AI these days, other approaches such as monte carlo methods are still relevant. In some cases, such as Alphago Zero, where a playing agent learns without any prior knowledge, neural network approaches are complemented with monte carlo simulation.

When is random random enough?

Usually in day to day code, there is a random() function that gives us a single dimenstion random quantity. In some places, to achieve entropy even lava lamps and webcams are used. These are called pseudo random numbers, are useful when a single sample is needed, in applications such as cryptography and gambling apps.
However, the pseudo random numbers have are not distributed in even way. This causes a kurtosis fenomenum which impairs the performance of random-based simulations such as this exemple.
A good example is the classic experiment of findig π by random point generation over a circle. The ratio between points inside and outside will approximate Pi by a fraction. This approach is described here and here

As ilustrated above, after 7000 samples, the quasi-random generator is converging faster than the pseudo random.

Code

Done in web assembly, experiment was done in C, compiled to WebAssembly. The following snippet illustrates the generation of quasi-random sequence. For the pseudo random, the system library was used.

#define PRIME_X 5
#define PRIME_Y 17

float van_der_corput_number(int n, int prime_base) {  
  float ret =  0.0;
  float denom = 1.0;
  while(n > 0) {
    denom = denom * prime_base;
    float rem = n % prime_base;
    n = n / prime
    ret = ret + (rem / denom);
  }
  return ret;
}

Point quasi_random_point(int max, int seq) {  
  Point ret;
  ret.x = (double)van_der_corput_number(seq, PRIME_X) * (double)max;
  ret.y = (double)van_der_corput_number(seq, PRIME_Y) * (double)max;
  return ret;
}

All code is in Github, and also a demo.

Spelling corrector in Erlang
Spelling correction is one of the coolest practical challenges in Information Retrieval. Since the famous article from Peter Norvig was published, many implementations were done. This article gave an insight of how practical problems - such simple spelling correction - are solved in Information Retrieval. Here is my contribute, in... Read More
Fixing Shellshock on ubuntu 12.10
Took a while to fix the shellshock vulnerability (did not have the kind of services that makes my host vulnerable). As is ubuntu 12.10, a simple apt-get update does not work: leonardo@pike:~$ x='() { :;}; echo ? VULNERABLE' bash -c : VULNERABLE leonardo@pike:~$ wget http://security.ubuntu.com/ubuntu/pool... Read More
Energy drink review: Black
A sweet vanila-powered drink of fast sugar-induced rush, must be drinked cold. Absense of citric aroma, but generous sugar content mildly tempered with shy herbal notes. The afterstaste is not impressive, but scales down well. Very faithful to the Polish tradition of energy drinks, but clearly not the top nectar... Read More
Quick and dirty location search tutorial
Some months ago, have been asked about how to generate a search result ordered by distance, without using spatial DB predicated. For a situation such as this, the steps are the following: Store the latitude and longitude in numeric fields in the table, something like this: create table poi(id... Read More
Energy drink review: Blue Spark (Tesco)
This drink offers a fresh start, featuring a good harmony of vanilla , citrus and berry notes. Leads to a pleasant drinking experience, easy flow and decently calibrated sweetness. However, the ending is too dry leaving an acrid aftertaste with unpleasant aspartame notes. Veredict: 3.5/5 Type: Taurine/Caffeine (0... Read More