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

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 11 years ago

- What is x-ray?
- The Wink home automation
- Skype works, shows I have internet, but browser wont go online
- If LED lights are so efficient then why do they get almost as hot as incandescents?
- How to correctly optimize your SSD for windows 10
- WAMP Mysqli: Your password has expired
- MySQL Dump/Restore, Dumping MySQL Database and Tables using MysqlDump command
- Source Code of Matrix Multiplication
- How to create your own PHP caching system? A simple example
- Domain Life Cycle
- Comparison of Random Functions According to their Exploration Performance (STL, .NET, Java)
- How to draw double buffered in C# or Java using GDI+
- How to recover Ubuntu after installing Windows using Ubuntu live cd
2
1