First random number is always smaller than rest

Question

I happen to notice that in C++ the first random number being called with the std rand() method is most of the time significant smaller than the second one. Concerning the Qt implementation the first one is nearly always several magnitudes smaller.

qsrand(QTime::currentTime().msec());
qDebug() << "qt1: " << qrand();
qDebug() << "qt2: " << qrand();

srand((unsigned int) time(0));
std::cout << "std1: " << rand() << std::endl;
std::cout << "std2: " << rand() << std::endl;

output:

qt1:  7109361
qt2:  1375429742
std1: 871649082
std2: 1820164987

Is this intended, due to error in seeding or a bug? Also while the qrand() output varies strongly the first rand() output seems to change linearly with time. Just wonder why.

Answer 1

I'm not sure that could be classified as a bug, but it has an explanation. Let's examine the situation:

1. Look at rand's implementation. You'll see it's just a calculation using the last generated value.

2. You're seeding using QTime::currentTime().msec(), which is by nature bounded by the small range of values 0..999, but qsrand accepts an uint variable, on the range 0..4294967295.

By combining those two factors, you have a pattern.

Just out of curiosity: try seeding with QTime::currentTime().msec() + 100000000

Now the first value will probably be bigger than the second most of the time.

I wouldn't worry too much. This "pattern" seems to happen only on the first two generated values. After that, everything seems to go back to normal.

EDIT:

To make things more clear, try running the code below. It'll compare the first two generated values to see which one is smaller, using all possible millisecond values (range: 0..999) as the seed:

int totalCalls, leftIsSmaller = 0;
for (totalCalls = 0; totalCalls < 1000; totalCalls++)
{
    qsrand(totalCalls);
    if (qrand() < qrand())
        leftIsSmaller++;
}
qDebug() << (100.0 * leftIsSmaller) / totalCalls;

It will print 94.8, which means 94.8% of the time the first value will be smaller than the second.

Conclusion: when using the current millisecond to seed, you'll see that pattern for the first two values. I did some tests here and the pattern seems to disappear after the second value is generated. My advice: find a "good" value to call qsrand (which should obviously be called only once, at the beginning of your program). A good value should span the whole range of the uint class. Take a look at this other question for some ideas:

• Recommended way to initialize srand?

Also, take a look at this:

• PCG: A Family of Better Random Number Generators

Answer 2

Neither current Qt nor C standard run-time have a quality randomizer and your test shows. Qt seems to use C run-time for that (this is easy to check but why). If C++ 11 is available in your project, use much better and way more reliable method:

#include <random>
#include <chrono>

auto seed = std::chrono::system_clock::now().time_since_epoch().count();
std::default_random_engine generator(seed);
std::uniform_int_distribution<uint> distribution;
uint randomUint = distribution(generator);

There is good video that covers the topic. As noted by commenter user2357112 we can apply different random engines and then different distributions but for my specific use the above worked really well.

Answer 3

Keeping in mind that making judgments about a statistical phenomena based on a small number of samples might be misleading, I decided to run a small experiment. I run the following code:

int main()
{
  int i = 0;
  int j = 0;
  while (i < RAND_MAX)
  {
    srand(time(NULL));
    int r1 = rand();
    int r2 = rand();
    if (r1 < r2) 
      ++j;
    ++i;
    if (i%10000 == 0) {
      printf("%g\n", (float)j / (float)i);
    }
  }
}

which basically printed the percentage of times the first generated number was smaller than the second. Below you see the plot of that ratio:

and as you can see it actually approaches 0.5 after less than 50 actual new seeds.

As suggested in the comment, we could modify the code to use consecutive seeds every iteration and speed up the convergence:

int main()
{
  int i = 0;
  int j = 0;
  int t = time(NULL);
  while (i < RAND_MAX)
  {
    srand(t);
    int r1 = rand();
    int r2 = rand();
    if (r1 < r2)
      ++j;
    ++i;
    if (i%10000 == 0) {
      printf("%g\n", (float)j / (float)i);
    }
    ++t;
  }
}

This gives us:

which stays pretty close to 0.5 as well.

While rand is certainly not the best pseudo random number generator, the claim that it often generates a smaller number during the first run does not seem to be warranted.