Non-random, intentionally, random number

[Tyro]

My random number generator is not random or is it my programming?

I will be using an 18x to light eight LEDs with any one of them switching off for a short period. The one to be switched of is selected by a random number generator.

I am using the experimenter board and initially just the three supplied LEDs, green, yellow and red. I divided the random number byte (0-255) by three and selected which LED was off by a simple numerical filter.

Because a truly random number would allow the same LED to be selected repeatedly, I added some code so that if the same LED were to be selected again a new random number would be calculated.

Unfortunately, this approach does not work as I have never seen a green to red or a red to green transition and I counted, over a minute or so, 13 green, 26 yellow and 14 red lights.

What am I doing wrong?

To complicate matters further, if I run the code in the simulator I get different results, with all possible transitions appearing and the number of each of the three LEDs being selected being very similar to each other. That is, they appear truly random.

symbol R_LED = 0
symbol Y_LED = 1
symbol G_LED = 2
symbol randNum =b2
symbol previous = b6
symbol current = b7

main:

rand_LED:
random w0 'generate random number
randNum = b0

let previous = current
let pins = %00000000

if randNum >= 170 then two 'filter which LED to switch off
if randNum >= 85 and randNum <= 169 then goto one
if randNum <= 84 then zero

two:
let current = 2
if current = previous then goto rand_LED
high R_LED
pause 1500

goto main

one:
let current = 1
if current = previous then goto rand_LED
high Y_LED
pause 1500

goto main

zero:
let current = 0
if current = previous then goto rand_LED
high G_LED
pause 1500

goto main

PS. To make this easier to see, the LEDs are inverted. That is, all are normally off and the randomly selected one on.

 

[hippy]

It could be the way the pseudo-random number generator works combined with your using the lower byte and selecting which band of values you are in. This should give you what you want -

  Do
    previous = randNum
    Do
      Random w0
      randNum = b1 // 3
    Loop Until randNum <> previous
    On randNum Gosub Zero, One, Two
    Pause 1500
  Loop

Zero:
  High G_LED
  Return
One:
  High Y_LED
  Return
Two:
  High R_LED
  Return

 

[Tyro]

Thank you Hippy, your code is a big improvement, and elegant. All possible transitions have been observed. The “randomness” is still not good enough for my application however.

Counting the times each LED is on reveals that this is not truly random. The results are; RED 61, YELLOW 54, GREEN 41.

Is any other technique available to increase the randomness? I am good with hardware but poor with software. There are no user inputs, so I cannot use the variable time between key strokes to improve the performance.

An external oscillator is possible but I would prefer to minimise the hardware.

 

[hippy]

Counting the times each LED is on reveals that this is not truly random. The results are; RED 61, YELLOW 54, GREEN 41.

We could all debate forever about what 'truly random' means, after nearly 160 random numbers there's a bias being seen here but there might not be any after a million or so, although I suspect there will be. Don't forget that repeated colours are being thrown away and that will be influencing the outcome.

I expect that after 150 numbers you would like to have had each colour shown 50 times.

The way I've tried to resolve this has been to experiment with what the randNum generated is using things like "randNum := w0 / K // 3". If you are lucky you will find a K which gives less bias. To test you'll need a loop which counts how many of each randNum's are chosen.

Going from that, you can use the fact that a bias is being shown to modify how the random function works. If there are too many Reds, make the next random select a Green or Yellow. That would end up with long sequences of alternating Green and Yellow while catch-up is played so probably no more acceptable.

Another method would be to choose a number, say 100, then add up how many (100-R), (100-Y) and (100-G) numbers are left. Choose a random number between 1 and that total, and then use a banding based on those numbers to choose which comes next. There will be more favouring towards those which have been shown least.

Of course, this all assumes a somewhat near perfect random number generator to start with so real world results may not be ideal, and you have to deal with the situation where you don't want repeating options, but the bias means that only one option can be chosen to unbias it. You also have to keep reducing your counts to make the maths manageable.

Taking a step back, assuming you had a genuine one-of-two random selector, from Red you know you have to go Yellow or Green, and similar for each other colour. That still wouldn't remove an inherent bias though.

To get random numbers as you really want them can be a tricky business and you're probably going to have to get involved in some deep understanding of randomness and statistics. That's all well beyond my comprehension. I fall at the first hurdle of probability theory, happy to accept that if I get on a plane to New York the probability that I'll find a gold bullion bar in Times Square is 50%; it's either there or it isn't

I know why your aren't getting what you want, but I'm afraid I'm not your man when it comes to fixing it.

 

[KMoffett]

Hippy,

A quote from my wife on another subject, but I always felt it fitted perfectly about generating random numbers: "It's only complicated if you understand it!"

Ken

 

[moxhamj]

Random number generators on computers have never been anything like random. Eg in VB generate random x and y numbers and plot dots on a picture box. After lots of dots have been plotted then lines start appearing.

A user input is one source but isn't available here. The other source that is possible is to use a white noise source that fundamentally is exploiting quantum noise in semiconductors, amplify it up to 0-5V and use readadc. But this does add a few more components eg a NPN transistor, an op amp (741) and a few caps and resistors.

 

[sjremington]

Could be random!

Tyro's evidence for nonrandomness in the number generator is actually not very convincing, as too few results were generated.

In any experiment expected to generate N outcomes at random, the expected variation from N (one standard deviation, accounting for 67% of the experiments) is given by sqrt(N). This is from elementary counting statistics.

So, out of 150 attempts, one would expect to see 50 +/- 7 reds, 50 +/- 7 greens, and 50 +/- 7 yellows (subject to adding to 150, of course). If one goes to 2 standard deviations (which would account for 95% of all experiments) then 50 +/- 14 reds would be expected, etc.

Thus, Tyro's results for 156 attempts are pretty much within expectation values. You *must* generate many more cases in order to determine whether the built-in generator is not random.

To carry this a bit further, if 150,000 numbers were generated, then you would expect to see 50,000 +/- 223 reds, etc. If instead you got 61,000 reds, then that number generator is truly flawed. Keep in mind that only 65,536 individual numbers can ever be generated in two-byte word.

Sadly, most people overlook this simple N +/- sqrt(N) result, for example, police reporting a drop in crime statistics, or politicians reporting a rise in same.

Cheers, Jim

 

[BrendanP]

I never ceased to be impressed by the range of skills,knowledge, expertise etc. availiable on this forum.

 

[hippy]

One thing to bear in mind is that the PICAXE random number generator is a Pseudo Random Number Generator (PRNG) which uses a maximal Long Frequency Shift Register (LFSR), so after 65536 iterations, every one of those 65536 individual numbers will have been used once and only once.

A power-of-two number of counters derived from that should therefore be perfectly equal, but any other number of counters will start to to show increasing differences after every 65536 iterations ...

1 : 65536
2 : 32768 32768
3 : 21845 21846 21845
4 : 16384 16384 16384 16384
5 : 13107 13108 13107 13107 13107
6 : 10922 10923 10923 10923 10923 10922
7 :  9362  9363  9363  9362  9362  9362  9362
8 :  8192  8192  8192  8192  8192  8192  8192  8192
9 :  7281  7282  7282  7282  7282  7282  7282  7282  7281

That's minimal and 'equally spread' bias though and well within the N+/-Sqrt(N) criteria.

For a random number purist I expect how the counters behave when less than 65536 iterations have been performed is important; after 16384 iterations, counters should all notionally be equal and fit within the +/-Sqrt(16384) limit.

Interesting with my own simulation of a PRNG ( taps on bits 15, 4, 2 and 1 ) the results aren't as perfect as they should be over 65536 iterations, but still very close to expected ...

1 : 65536
2 : 32768 32768
3 : 21845 21845 21846
4 : 16383 16384 16385 16384
5 : 13107 13107 13108 13107 13107
6 : 10922 10923 10924 10923 10922 10922
7 :  9362  9363  9363  9362  9362  9362  9362
8 :  8191  8192  8193  8192  8192  8192  8192  8192
9 :  7281  7282  7283  7282  7282  7282  7282  7281  7281

Over 16384 iterations there is considerably more divergence, outside the 128, +/-Sqrt(16384) expectations ...

1 : 16384
2 :  8271  8113
3 :  5420  5448  5516
4 :  4199  4072  4072  4041
5 :  3198  3310  3274  3291  3311
6 :  2723  2661  2761  2697  2787  2755
7 :  2390  2321  2350  2338  2346  2335  2304
8 :  2135  2064  2053  2020  2064  2008  2019  2021
9 :  1822  1772  1828  1822  1810  1847  1776  1866  1841

Over just 256 iterations the divergence is even worse. Note the bias towards six for dice-rolling when there are six counters in play ...

1 :   256
2 :   121   135
3 :    84    84    88
4 :    54    66    67    69
5 :    57    51    47    46    55
6 :    39    41    39    45    43    49
7 :    42    26    32    38    36    32    50
8 :    30    24    37    30    24    42    30    39
9 :    30    26    28    28    26    28    26    32    32

The counter to increment was determined in all cases by using "random MOD K", where K is the number of counters used.

 

[sjremington]

As random as expected

I ran the following program on a 14M, which contains an infinite loop to generate 150 random numbers, each of which is used to choose one of three LEDs to "light". The program counts how many times the red, green and yellow LED were lit in an iteration and reports these values in the debug window.

After 436 iterations of the main loop, which should exhaust the generator, the mean and standard deviation of the number of times each LED was lit were R=50.00 +/- 7.47, G= 50.01 +/-5.45 and Y= 49.98 +/- 5.47. The least and most times that any LED was lit were 32 and 72 (about 3 standard deviations from the mean), although a perfect random number generator, running in an infinite loop should, about once in the age of the universe, light one LED 150 times.

I have also verified that each possible value between 1 and 65,535 (in that many calls) is returned only once by the generator as claimed. Therefore, within the design limitations, there is no problem with the random number generator supplied by the PICAXE folks. Furthermore, one cannot expect to gain additional "randomness" by discarding values returned by the generator.

Have fun, Jim

do

b5=0 'count reds
b6=0 'count greens
b7=0 'count yellow

for w1= 1 to 150
      Random w0
      b4 = w0 // 3
    On b4 Gosub Zero, One, Two
next
debug 'output results
pause 3000
loop

Zero:
  b5=b5+1
  Return
One:
  b6=b6+1
  Return
Two:
  b7=b7+1
  Return

Partial sequence of results from debug window: (values of b5, b6, b7)

53 46 51
43 53 54
37 57 56
53 53 44
41 62 47
49 44 57
42 55 53
56 43 51
48 47 55
...
69 36 45