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

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];
}

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.