About random number sequence generation

Question

I am new to randomized algorithms, and learning it myself by reading books. I am reading a book Data structures and Algorithm Analysis by Mark Allen Wessis .

Suppose we only need to flip a coin; thus, we must generate a 0 or 1 randomly. One way to do this is to examine the system clock. The clock might record time as an integer that counts the number of seconds since January 1, 1970 (atleast on Unix System). We could then use the lowest bit. The problem is that this does not work well if a sequence of random numbers is needed. One second is a long time, and the clock might not change at all while the program is running. Even if the time were recorded in units of microseconds, if the program were running by itself the sequence of numbers that would be generated would be far from random, since the time between calls to the generator would be essentially identical on every program invocation. We see, then, that what is really needed is a sequence of random numbers. These numbers should appear independent. If a coin is flipped and heads appears, the next coin flip should still be equally likely to come up heads or tails.

Following are question on above text snippet.

1. In above text snippet " for count number of seconds we could use lowest bit", author is mentioning that this does not work as one second is a long time, and clock might not change at all", my question is that why one second is long time and clock will change every second, and in what context author is mentioning that clock does not change? Request to help to understand with simple example.

2. How author is mentioning that even for microseconds we don't get sequence of random numbers?

Thanks!

Answer 1

Programs using random (or in this case pseudo-random) numbers usually need plenty of them in a short time. That's one reason why simply using the clock doesn't really work, because The system clock doesn't update as fast as your code is requesting new numbers, therefore qui're quite likely to get the same results over and over again until the clock changes. It's probably more noticeable on Unix systems where the usual method of getting the time only gives you second accuracy. And not even microseconds really help as computers are way faster than that by now.

The second problem you want to avoid is linear dependency of pseudo-random values. Imagine you want to place a number of dots in a square, randomly. You'll pick an x and a y coordinate. If your pseudo-random values are a simple linear sequence (like what you'd obtain naïvely from a clock) you'd get a diagonal line with many points clumped together in the same place. That doesn't really work.

One of the simplest types of pseudo-random number generators, the Linear Congruental Generator has a similar problem, even though it's not so readily apparent at first sight. Due to the very simple formula

you'll still get quite predictable results, albeit only if you pick points in 3D space, as all numbers lies on a number of distinct planes (a problem all pseudo-random generators exhibit at a certain dimension):

Answer 2

He means by that is you are not able to control how fast your computer or any other computer runs your code.
So if you suggest 1 second for execution thats far from anything. If you try to run code by yourself you will see that this is executed in milliseconds so even that is not enough to ensure you got random numbers !

Answer 3

1. Computers are fast. I'm over simplifying, but if your clock speed is measured in GHz, it can do billions of operations in 1 second. Relatively speaking, 1 second is an eternity, so it is possible it does not change.

2. If your program is doing regular operation, it is not guaranteed to sample the clock at a random time. Therefore, you don't get a random number.

Answer 4

Don't forget that for a computer, a single second can be 'an eternity'. Programs / algorithms are often executed in a matter of milliseconds. (1000ths of a second. )

The following pseudocode:

for(int i = 0; i < 1000; i++)
   n = rand(0, 1000) 

fills n a thousand times with a random number between 0 and 1000. On a typical machine, this script executes almost immediatly.

While you typically only initialize the seed at the beginning:

The following pseudocode:

srand(time());
for(int i = 0; i < 1000; i++)
   n = rand(0, 1000) 

initializes the seed once and then executes the code, generating a seemingly random set of numbers. The problem arises then, when you execute the code multiple times. Lets say the code executes in 3 milliseconds. Then the code executes again in 3 millisecnds, but both in the same second. The result is then a same set of numbers.

For the second point: The author probabaly assumes a FAST computer. THe above problem still holds...