Pages: [1]   Go Down
 Author Topic: Interesting probability design pattern  (Read 392 times) 0 Members and 1 Guest are viewing this topic.
Dallas, Texas
Offline
God Member
Karma: 1
Posts: 695
Old, decrepit curmugeon
 « on: June 04, 2012, 02:02:53 pm » Bigger Smaller Reset

While reviewing a colleagues code for a hard to identify bug, I encountered what for me is a new design pattern for triggering events with a given probability.  In the past when needing to trigger an event with a certain probability, say 5% I would also use a code snippet like the following:

Code:
event = random(100);
if (event < 5)
Event Happened.

However, my colleague used the following approach:
Code:
if (random(20) == random(20))
Event Happended

At first, it seemed counter intuitive that his approach would produce a 5% chance of the event occurring, but looking at the math and running a few simulations proved that it would...  Has anyone else ever seen this design pattern?  What advantages does it have?

Oh, and for those of you interested in seeing that it works you can run this sketch...

Code:
int chance;
int gambler, house;
long hits=0;
long total=0;
float odds;

void DisplayResults(long h, long t, float o)
{
Serial.print("Hits = ");
Serial.print(h);
Serial.print(", Total = ");
Serial.print(t);
Serial.print(", Chance = ");
Serial.print(o);
Serial.print(", Should = ");
Serial.println(0.05);
}

void setup()
{
Serial.begin(115200);
chance = 20;  // Represent a 5% chance 1/0.05
}

void loop()
{
gambler = random(chance);
house = random(chance);
total++;
if (gambler == house)
{
hits++;
odds = hits / (1.0 * total);
DisplayResults(hits, total, odds);
}
}
 Logged

New true random number generation library available at: http://code.google.com/p/avr-hardware-random-number-generation/

Current version is Entropy.v0.6.zip

Global Moderator
UK
Offline
Brattain Member
Karma: 225
Posts: 23619
I don't think you connected the grounds, Dave.
 « Reply #1 on: June 04, 2012, 02:07:49 pm » Bigger Smaller Reset

Quote
Depends on how expensive it is to call "random", but I'd probably say "very few".
 Logged

"Pete, it's a fool looks for logic in the chambers of the human heart." Ulysses Everett McGill.
Do not send technical questions via personal messaging - they will be ignored.

Dallas, Texas
Offline
God Member
Karma: 1
Posts: 695
Old, decrepit curmugeon
 « Reply #2 on: June 04, 2012, 02:12:04 pm » Bigger Smaller Reset

Quote
Depends on how expensive it is to call "random", but I'd probably say "very few".

Frankly, I can't think of any advantages.  But I wanted to ask more globally before I talk with my colleague.  To me it shows his tendency to pick what he describes as "more elegant" solutions, which I tend to describe as overly complicated rube goldbergs...
 Logged

New true random number generation library available at: http://code.google.com/p/avr-hardware-random-number-generation/

Current version is Entropy.v0.6.zip

Offline
Edison Member
Karma: 4
Posts: 1722
 « Reply #3 on: June 04, 2012, 02:24:38 pm » Bigger Smaller Reset

Definetly can't see any advantage other than making it a little more straightfoward
 Logged

UK
Offline
Karma: 90
Posts: 3900
 « Reply #4 on: June 04, 2012, 02:24:38 pm » Bigger Smaller Reset

The random number generator is quite a heavy-weight algorithm.  Your colleague's way of doing it uses twice as many calls to the random() function, which doubles the amount of processing for the random number.

From an efficiency point of view, it's about 50% as efficient as your way.  It's also hard to understand.
 Logged

Why not visit my eBay shop? http://stores.ebay.co.uk/Majenko-Technologies
Replacement for the Arduino IDE: UECIDE - Proper serial terminal, graphing facilities, plugins, overhauled internals.
Java isn't bad in itself, but it has enabled morons to write programs.

Global Moderator
Dallas
Online
Shannon Member
Karma: 171
Posts: 12054
 « Reply #5 on: June 04, 2012, 02:33:49 pm » Bigger Smaller Reset

Quote
Depends on how expensive it is to call "random", but I'd probably say "very few".

On a 16 MHz Uno, the Libc random function takes 94.481 microseconds to generate the next value.  The Arduino random function with one parameter takes 137.663 microseconds.  With two calls, that's roughly 1/4 of a millisecond.  The comparison is insignificant (a few machine instructions in the worst case).

I agree with AWOL (not worth the CPU time) and majenko (not worth the CPU time and a nightmare for maintenance).
 Logged

Dallas, Texas
Offline
God Member
Karma: 1
Posts: 695
Old, decrepit curmugeon
 « Reply #6 on: June 04, 2012, 02:45:49 pm » Bigger Smaller Reset

The system the original code runs on is not AVR based, but I thought (and still do) the principal is interesting.  While thinking about this design pattern, I have thought of a situation where it is an advantage.  Most of the time, we expect a function like random(20) to return a number between 0 and 19 with equal probability; however, if the random function is not uniform (or if biased to certain values), then comparing two random calls would tend to eliminate the influence of the bias on the probability of the outcome.

One area this could apply for the arduino, is when using a hardware based random number generator...  Since those generators either have to include some form of software whitening to make them less biased which reduces their generation speed, one could use this approach without the whitening (the raw biased generator) and still obtain the probability desired...
 Logged

New true random number generation library available at: http://code.google.com/p/avr-hardware-random-number-generation/

Current version is Entropy.v0.6.zip

Offline
Edison Member
Karma: 29
Posts: 1368
 « Reply #7 on: June 04, 2012, 03:07:19 pm » Bigger Smaller Reset

Changing this:
Code:
if (random(20) == random(20))
Event Happended
to this:
Code:
if (random(20) == 3)
Event Happended
has the same effect and calls random() once. You can use any number from 0 - 19 in place of 3.

Quote
then comparing two random calls would tend to eliminate the influence of the bias on the probability of the outcome.
I don't see how this would work. If, for example, the RNG was so badly biased that random(20) always produced 3, then random(20)==random(20) would succeed 100% of the time.

Pete
 Logged

New Jersey
Offline
Karma: 42
Posts: 3271
 « Reply #8 on: June 04, 2012, 03:15:40 pm » Bigger Smaller Reset

Quote
At first, it seemed counter intuitive that his approach would produce a 5% chance of the event occurring, but looking at the math and running a few simulations proved that it would.

The very fact that you (and anyone else who looks at it later) had to go to this trouble to convince yourself it was ok tells you very clearly that it isn't a good idea.
 Logged

Dallas, Texas
Offline
God Member
Karma: 1
Posts: 695
Old, decrepit curmugeon
 « Reply #9 on: June 04, 2012, 03:20:14 pm » Bigger Smaller Reset

Changing this:
Code:
if (random(20) == random(20))
Event Happended
to this:
Code:
if (random(20) == 3)
Event Happended
has the same effect and calls random() once. You can use any number from 0 - 19 in place of 3.

Quote
then comparing two random calls would tend to eliminate the influence of the bias on the probability of the outcome.
I don't see how this would work. If, for example, the RNG was so badly biased that random(20) always produced 3, then random(20)==random(20) would succeed 100% of the time.

Pete

If the RNG were too heavily biased it wouldn't work to eliminate that bias, but if only moderately biased it does.  I tried using the raw biased RNG values from my WDT random number generator which display bias for values 0 & 255, and it produced the expected 5% probability even so.  So far that is the only reason i can find to use this design pattern.
 Logged

New true random number generation library available at: http://code.google.com/p/avr-hardware-random-number-generation/

Current version is Entropy.v0.6.zip