Comparison of Random Functions According to their Exploration Performance (STL, .NET, Java)

Today, I’ll analyze and compare the performance of random functions of different libraries: namely STL, .NET and Java. I choose a well known problem in stochastic processes to apply some simulations. I will give the details of the problem below.

Particle Moving Around A Circle

Moving Particles

Consider a particle that moves along a set of M+1 nodes, labelled with 0, 1, 2, …, M, that are arranged around a circle. At each step, the particle is equally likely to move one position in either the clockwise or counterclockwise direction. That is, if X[N] is the position of the particle after its Nth step then

P{ X[n+1] = i+1 | X[n] = i } =
    P{ X[n+1] = i-1 | X[n] = i } = 0.5

where i+1 = 0 when i = m and, i-1 = m when i = 0. Suppose now that the particle starts at node 0 and continues to move around according to the above rules until all the nodes 1, 2, .., M have been visited. What is the probability that node i (i = 1, 2, … M) is the last one visited?

SOLUTION:

According to stochastic theory, the solution of such a complicated problem is absolutely simple. No matter where the particle starts,

P{ i is the last node visited } = 1 / M.

Is it abnormal? Look details of the proof from “Stochastic Processes – Sheldon M. Ross, p:42″.

SIMULATION:

Now, we have the problem that gives same probabilities for each node to be the last visited one. We have a simple algorithm and the C++ code is given below. You may simply adapt this code for other languages.

bool x[M]; // is visited ?
int y[M] = {0}; // number of wins of nodes (be the last one visited)
for (int t = 0; t < TEST; ++t)
{
    for (int i = 0; i < M; ++i)
        x[i] = false;
    int cur = 0;
    bool cont = true;
    x[cur] = true;

    while (cont)
    {
        if (rand() % 2 == 0)
            cur = (cur+1) % M;
        else cur = (cur+M-1) % M;
            x[cur] = true;

        cont = false;
        for (int i = 0; i < M; ++i)
            if (!x[i])
                cont = true;
    }

    ++y[cur];
}

I assume that M = 65; therefore, we have totally 64 non-visited nodes in the beginning. I have run the simulation TEST = 10000 times and here is the figure of results.
Simulaton Results for Random Function Comparison
Now, it is interesting to see in the chart that STL rand() performs poor when we consider the exploration performance. It gives symmetrical results for both ends and can not distribute the winners to the whole set. On the other hand, .NET and Java Random classes gives satisfactory results for this test. This analyze show that if exploration of the environment is critical for your application, then stay away from STL random function and find a better one. As a last comment, you may also try “Mersenne Twister” yourself to see the satisfactory results.

added 4 years ago

- What does chess ELO ratings mean?
- WAMP Mysqli: Your password has expired
- Search Engine optimization: Google's 200 Ranking Factors
- MySQL Dump/Restore, Dumping MySQL Database and Tables using MysqlDump command
- iPhone 4S vs iPhone 5 vs Samsung Galaxy S3 comparison results
- Source Code of Matrix Multiplication
- How to Install Oracle Java on Ubuntu Linux? Java Performance Problems
- How to create your own PHP caching system? A simple example
- What is CSS and why is it useful?
- Domain Life Cycle
- How to Use a Router as a Repeater?
- Comparison of Random Functions According to their Exploration Performance (STL, .NET, Java)
- How to install Memcached on Win 7 + WAMP Server, the simplest way of all
- How to draw double buffered in C# or Java using GDI+
- How to restart page numbering for each chapter in Word 2007 – 2010
- How to recover Ubuntu after installing Windows using Ubuntu live cd