How to understand autocorrelation caused by over-sowing RNG?

Question

In response to this question, I conducted the following VBA experiment:

Sub Test() Dim i As Long, A As Variant Dim count1 As Long, count2 As Long ReDim A(1 To 10000) For i = 1 To 10000 Randomize A(i) = IIf(Rnd() < 0.5, 0, 1) Next i 'count how often A(i) = A(i+1) For i = 1 To 9999 If A(i) = A(i + 1) Then count1 = count1 + 1 Next i For i = 1 To 10000 A(i) = IIf(Rnd() < 0.5, 0, 1) Next i 'count how often A(i) = A(i+1) For i = 1 To 9999 If A(i) = A(i + 1) Then count2 = count2 + 1 Next i Debug.Print "First Loop: " & count1 Debug.Print "Second Loop: " & count2 & vbCrLf End Sub 

When I saw the output as follows:

 First Loop: 5550 Second Loop: 4976 

I was sure that I knew what was happening: VBA converted the system clock to something lower (possibly a microsecond), which, as a result, would have led Randomize sometimes produce the same seeds in two or more passes through the loop. In my original answer, I even confidently stated this. But then I ran the code a bit and noticed that the output was something like this:

 First Loop: 4449 Second Loop: 5042 

Overflow still causes a noticeable autocorrelation, but in the opposite (and unexpected) direction. Successive passage through a loop with the same seed should give the same outputs, so we should see that successive values ​​agree more often than probability to predict, and not contradict more often than probability to predict.

Curiously, I changed the code to:

 Sub Test2() Dim i As Long, A As Variant Dim count1 As Long, count2 As Long ReDim A(1 To 10000) For i = 1 To 10000 Randomize A(i) = Rnd() Next i 'count how often A(i) = A(i+1) For i = 1 To 9999 If A(i) = A(i + 1) Then count1 = count1 + 1 Next i For i = 1 To 10000 A(i) = Rnd() Next i 'count how often A(i) = A(i+1) For i = 1 To 9999 If A(i) = A(i + 1) Then count2 = count2 + 1 Next i Debug.Print "First Loop: " & count1 Debug.Print "Second Loop: " & count2 & vbCrLf End Sub 

which always gives the following output:

 First Loop: 0 Second Loop: 0 

Non-sequential calls to Randomize seem to sometimes return the same seed (at least not as often as to make a difference).

But if this is not a source of autocorrelation - what is it? And - why is this sometimes manifested as negative rather than positive autocorrelation?

Answer 1

Partial response, free to edit and complete.

---

Well, obviously there is a correlation when you abuse the Randomize function.

I tried the following code with conditional formatting (black fill for values> 0.5) and patterns appear explicitly (try commenting on Randomize to see a more “random” pattern. (Best seen with 20 column columns and 10% zoom)

 Function Rndmap() Dim i As Long, j As Long Dim bmp(1 To 512, 1 To 512) As Long For i = 1 To 512 For j = 1 To 512 ' Rnd -1 ' uncomment this line to get a big white and black lines pattern. Randomize 'comment this line to have a random pattern bmp(i, j) = IIf(Rnd() < 0.5, 0, 1) Next j Next i Range(Cells(1, 1), Cells(512, 512)) = bmp End Function 

Thus, although MSDN states that “Using Randomize with the same value for a number does not repeat the previous sequence”, implying that if the timer returns twice as much as the same value, Rnd should remain in the same random sequence without resection, there is still some links behind the scene.

Some screenshots:

Rnd () only:

Using Randomize:

Using Rnd -1 and Randomize:

Answer 2

The Randomize method initializes the Rnd function with the current system time as it is seed, you can also specify a number with Randomize that will be used as a seed.

I decided to check how long the sequence lasts until it repeats:

 Sub randomRepeatTest() For i = 1 To 100000 Randomize randomThread = randomThread & Int(9 * Rnd + 1) If i Mod 2 = 0 Then If Left(randomThread, i / 2) = Right(randomThread, i / 2) Then Debug.Print i / 2 Exit Sub End If End If Next i End Sub 

This subgenerator generates a random sequence of digits 0-9, and as the sequence becomes even, it is checked to see if the first half of the sequence matches the second half, and if so, it displays the length of the sequence before repeating. After starting it several times and at a discount, when the number is repeated twice at the beginning, the result is 256 (good).

Providing any value to Randomize will still return a result of 256.

---

We randomize Rnd every cycle, so what happens here?

Well, as I said at the beginning, if the Randomize value is not specified, it will use the system time as a seed. The resolution of this time is something that I seem to be unable to find, but I find it low.

I tested using a timer value that returns the time of day in seconds up to 2 decimal places (e.g. 60287.81). I also tried GetTickCount , which returns the system active time (starts counting at boot) in milliseconds. Both of them still lead to a 256 limit sequence.

So why, when we randomize each cycle, does the sequence repeat? Well, actually, the code is executed within a millisecond. Essentially, we provide the same number to randomize each cycle, and therefore we do not actually shuffle the seed.

---

So is Rnd more random without randomize?

I ran the above subgroup again without Randomize ; nothing came back. I increased the number of cycles to 2,000,000; nothing yet.

I managed to fix the algorithm used according to the formula of the book Rand , which, in my opinion, is the same as Rnd without initialized seed:

C IX, IY, IZ SHOULD BE INSTALLED FOR INTEGRATION BETWEEN 1 AND 30,000 BEFORE THE FIRST ENTRANCE

IX = MOD (171 * IX, 30269)

IY = MOD (172 * IY, 30307)

IZ = MOD (170 * IZ, 30323)

RANDOM = AMOD (FLOAT (IX) /30269.0 + FLOAT (IY) /30307.0 + FLOAT (IZ) /30323.0, 1.0)

This is an iterative function that uses the result of a previous call to generate a new number. The indicated Wichmann-Hill procedure ensures that more than 10 ^ 13 numbers will be generated before the sequence repeats.

---

Problem with Rnd

For the algorithm to work, you must first initialize it with the values ​​for IX , IY and IZ . The problem that we have here is that we cannot initialize an algorithm with random variables, since we need this algorithm to obtain random values, so the only option is to provide some static values ​​to get it.

I tested this and it seems to be so. Opening a new instance of Excel ? Rnd() ? Rnd() returns 0.70554. Executing the same result returns the same number.

Thus, the problem we have, Rnd without using Randomize , gives us a much longer sequence of random numbers, however this sequence starts in the same place every time you open Excel. If the functions depend on random generation, for example, password generation, this is not enough, since we will get the same duplicate results every time you open Excel.

---

Decision

Here is a function that I came up with and seems to work well:

 Public Declare PtrSafe Sub Sleep Lib "kernel32" (ByVal Milliseconds As LongPtr) Public Declare Function GetTickCount Lib "kernel32" () As Long Public randomCount As Long Function getRandom() If randomCount Mod 255 = 0 Then Sleep 1 End If Randomize GetTickCount getRandom = Rnd() randomCount = randomCount + 1 End Function 

The GetTickCount function is GetTickCount . Each call adds 1 to the randomCount variable, and after every 255 starts, the macro is forced to sleep for 1 millisecond (although it actually works for about 15 on my system), so the GetTickCount seed will be changed and therefore a new sequence of numbers will be returned to Rnd

This, of course, will return the same sequence if it is accidentally used in the same system time, but in most cases it will be a sufficient way to generate more random numbers. If this is not the case, some fancy work will be needed using something like the Random.Org API .