Why does this random pattern generator make an organized pattern over time?

[SMcNeill]

Code: QB64: [Select]

1. DIM SHARED Array(1000000) AS _FLOAT
2.  
3.  
4.  
5.  
6. SCREEN 12
7.  
8. DO
9.     x = Rand * _WIDTH
10.     y = Rand * _HEIGHT
11.     c = Rand * 16
12.     q = Rand
13.     PSET (x, y), c
14.     ' _LIMIT 10000
15. LOOP UNTIL _KEYHIT
16.  
17.  
18.  
19.  
20. FUNCTION Rand
21.     STATIC Init, IndexOn
22.     IF Init = 0 THEN
23.         Init = -1
24.         FOR I = 0 TO 1000000
25.             Array(I) = I / 1000001
26.         NEXT
27.     END IF
28.     IF IndexOn = 0 THEN
29.         RANDOMIZE TIMER
30.         FOR I = 0 TO 1000000
31.             SWAP Array(I), Array(INT(RND * 1000001))
32.         NEXT
33.     END IF
34.     IndexOn = (IndexOn + 1) MOD 1000000
35.     Rand = Array(IndexOn)
36. END FUNCTION
37.  

As I said above, simply shuffling a large array and using it to generate random values, usually works more than good enough to suit my needs.  It certainly creates a good "pattern" of static above.  ;)

[bplus]

Pattern removed

Code: QB64: [Select]

1. Screen 12
2.  
3. Do
4.     x = Rnd * _Width
5.     y = Rnd * _Height
6.     c = Rnd * 16
7.     PSet (x, y), c
8.     _Limit 10000
9. Loop
10.  

[SMcNeill]

This is more of a math/randomize question I suppose.  I didn't go very far in math, so if someone could explain this to me in a layman way why this occurs, I'll be thanking you.

I am playing around making what I think are random pattern makers, but over time this creates an organized pattern on the screen.  Why is that?

Run this for a little while, and slowly it makes organized stripes on the screen.  Shouldn't it remain a random mess?

- Dav

 

Code: QB64: [Select]

1. SCREEN _NEWIMAGE(600, 600, 32)
2.  
3. RANDOMIZE TIMER
4.  
5. DO
6.     FOR l = 1 TO 1000
7.         x = RND * 600: y = RND * 600: c = RND * 255
8.         LINE (x, y)-(x + 20, y + 20), _RGBA(c, c, c, RND * 1), BF
9.     NEXT
10.     _LIMIT 100
11. LOOP
12.  

One more point of interest here -- as written, this will eventually turn the whole screen a solid gray, simple because you're gradually increasing alpha levels.   (After the first pass, you've blended a gray tone onto the screen, and you just continue to blend onto that already blended screen...)

Code: QB64: [Select]

1.  
2. DIM SHARED Array(1000000) AS _FLOAT
3. SCREEN _NEWIMAGE(600, 600, 32)
4.  
5. RANDOMIZE TIMER
6.  
7. DO
8.     FOR l = 1 TO 1000
9.         x = Rand * 600: y = Rand * 600: c = Rand * 255
10.         LINE (x, y)-(x + 20, y + 20), _RGBA(c, c, c, Rand * 1), BF
11.     NEXT
12.     _LIMIT 120
13. LOOP UNTIL _KEYHIT
14.  
15. FUNCTION Rand
16.     STATIC Init, IndexOn
17.     IF Init = 0 THEN
18.         Init = -1
19.         FOR I = 0 TO 1000000
20.             Array(I) = I / 1000001
21.         NEXT
22.     END IF
23.     IF IndexOn = 0 THEN
24.         RANDOMIZE TIMER
25.         FOR I = 0 TO 1000000
26.             SWAP Array(I), Array(INT(RND * 1000001))
27.         NEXT
28.     END IF
29.     IndexOn = (IndexOn + 1) MOD 1000000
30.     Rand = Array(IndexOn)
31. END FUNCTION
32.  

[Dav]

Yes, I just posted that as is was because it showed the curious pattern.  I was getting it on several pattern makers that used colors too, and was very curious as to why.  Your swap array does prevent the pattern.

- Dav

[SMcNeill]

Your swap array does prevent the pattern.

I won’t swear that swapping an array like that won’t eventually end up repeating, but if it does, the number of iterations is more than I’ve rand across in my personal applications. 

After all, how many times do you need to shuffle a deck of 52 cards, before you get it back into perfect order?  Eventually, I imagine it’ll happen, but at what point? 

And this is an array of 1000001 elements.  I’d imagine it’d take a lot more shuffling than a deck of cards, before you end up back at the starting point once again.

If it’s not “true random”, it’s close enough of a method for all my needs.  ;)

[Dimster]

So, I'm not exactly sure of the definition of "True Random". It would seem to me that repeat numbers HAVE to be as a result of the size of a SET of numbers. No matter what the Set size is, eventually you would have to accept a repeat of a number or group of numbers. If set size dictates repeats and True Randomness excludes a repeat of a number then either the set size has to be infinity or the Random function must be set to cease/end at the first repeated number.

[bplus]

So, I'm not exactly sure of the definition of "True Random". It would seem to me that repeat numbers HAVE to be as a result of the size of a SET of numbers. No matter what the Set size is, eventually you would have to accept a repeat of a number or group of numbers. If set size dictates repeats and True Randomness excludes a repeat of a number then either the set size has to be infinity or the Random function must be set to cease/end at the first repeated number.

True random could repeat numbers million times, but not usually.

[SMcNeill]

True random could repeat numbers million times, but not usually.

Aye, and that’s the one big drawback to shuffling an array like I illustrated above.  Imagine it as playing cards  — you don’t reshuffle the deck until ALL cards are played.  If you’re a card counter, you realize that once the Ace of Spades has been played, it’s not going to be dealt again until all the other cards are played first.  The bigger the array, the harder it is to count, but it’s very obvious if you use such a method just for coin tosses.  If the first toss is heads, the second toss is tails, and vice-versa.

Array shuffling is a pseudorandom method that isn’t useable for all purposes, but it’s useful for non-repeating patterns like we’re discussing here.  ;)

[bplus]

Just shuffle your deck between every call, too bad for card counters ;-))

This makes is possible to have a million numbers in a row?

[SMcNeill]

Just shuffle your deck between every call, too bad for card counters ;-))

You can do that, but then there’s the hit on performance with shuffling so constantly.  You’re not just saying, “Quick, give me a random number so I can decide if the ghost goes left or right after Pac-man!”  Instead, you’re saying, “Quick, shuffle a million element array and then give me a number...”

[Bert22306]

Well, okay, getting away from Steve's highjacking of the thread(!), and back to these odd patterns people are experiencing, I went back to Luke's example. Yes, I got patterns again. But the question is, what causes that?

So I wrote this almost identical program, except using Screen _NewImage (which has no effect), then doing nothing more than either:

(a) eliminate the one, useless, q = Rnd, or

(b) define that one useless variable, but undo the random color variable used in Pset (just use white pixels), or

(c) copy what Luke did, but define another extra s = Rnd variable,

and you see no pattern. You'd think, if this PRNG is so bad, I'd see a patterns with these other examples too, no?

In the code here, you should see patterns. But, uncomment one, or both, of the Rem statements, or add another few useless random variables, and the pattern goes away. Really, try it.

Code: [Select]

Screen _NewImage(840, 480, 12)
Randomize Timer
Do
    x = Rnd * _Width
    y = Rnd * _Height
    c = Rnd * 16
    q = Rnd
    Rem    r = Rnd
    Rem    s = Rnd
    PSet (x, y), c
    If InKey$ = Chr$(27) Then End
    _Limit 10000
Loop
End

(Edited only to correct typos.)

[bplus]

(a) eliminate the one, useless, q = Rnd, or

as I posted ;)

Random number generator patterns are susceptible to 2's (read in wiki) when having one of these discussions on another forum. Notice Luke's q makes the number of calls even every cycle.

wiki suggests for heads tails if rnd repeats last head or tail to take the next flip as the official one, something like that.

[Bert22306]

Random number generator patterns are susceptible to 2's (read in wiki) when having one of these discussions on another forum. Notice Luke's q makes the number of calls even every cycle.

wiki suggests for heads tails if rnd repeats last head or tail to take the next flip as the official one, something like that.

Well, sumbich, you're exactly right, bplus. I entered a few extra useless variables, to total 8, and got a similar pattern.

So, bottom line, when using Rnd in a loop, make sure the total number of variables which use Rnd is not a power of 2. If it is a power of 2, add one dummy random variable, in that loop.

Thanks for that info!

[SMcNeill]

I’d think even odd values would repeat; just at different intervals.

Let’s say I have a list of 4 numbers, from 1 to 4.

Now, I get records in sequence of 4:

(1, 2, 3, 4) (1, 2, 3, 4) (1, 2, 3, 4)...  these repeat instantly!

Now, let’s get records in sequences of 3:

(1, 2, 3) (4, 1, 2) (3, 4, 1) (2, 3, 4), (1, 2, 3)....repeat.

It’s not that your sequence of 3 won’t repeat — it’ll just take the LCD (Lowest Common Denominator) times for it to repeat...

Which is what you guys are producing with your tests.  ;)

[Bert22306]

I have to ponder on your suggestion, Steve.

In the meantime, here's demo, split screen, where the left side sees the looping Rnd variables to be non-power-of two, while the right side sees 8 Rnd variables in the loop.

But puzzle me this: Why does the right side appear to be a lighter color, overall? If you use _Height and _Width, to size the screen, the result looks darker, than if you use the actual pixel count. Rewrite the right side, using

z = (_Width / 2) + (420 * Rnd)

and you will see both sides equally dark. Weird.

Code: [Select]

Screen _NewImage(840, 480, 12)
Rem -------
Rem  Moral of the story: make sure *not* to define a power of 2, as total
Rem  number of random variables in the loop. Test this with 4 or 8 Rnd
Rem  variables, and you sill see diagonal patterns in the image.
Rem -------
Randomize Timer
Do
    x = Rnd * _Width
    y = Rnd * _Height
    z = 420 + Rnd * 420
    w = Rnd * _Height
    c = 1 + Int(Rnd * 15)
    q = Rnd
    r = Rnd
    s = Rnd
    Rem    t = Rnd
    Rem    u = Rnd
    PSet (x, y), c
    PSet (z, w), c
    If InKey$ = Chr$(27) Then End
    _Limit 10000
Loop
End