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

}