Pages: [1]   Go Down
Author Topic: Interesting probability design pattern  (Read 554 times)
0 Members and 1 Guest are viewing this topic.
Dallas, Texas
Offline Offline
God Member
*****
Karma: 31
Posts: 887
Old, decrepit curmugeon
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset 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
  randomSeed(analogRead(0));
}

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 library available at: http://code.google.com/p/avr-hardware-random-number-generation/

Current version 1.0.1

Global Moderator
UK
Offline Offline
Brattain Member
*****
Karma: 302
Posts: 26285
I don't think you connected the grounds, Dave.
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Quote
What advantages does it have?
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 Offline
God Member
*****
Karma: 31
Posts: 887
Old, decrepit curmugeon
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Quote
What advantages does it have?
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 library available at: http://code.google.com/p/avr-hardware-random-number-generation/

Current version 1.0.1

Offline Offline
Edison Member
*
Karma: 5
Posts: 1730
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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

UK
Offline Offline
Faraday Member
**
Karma: 99
Posts: 4153
Where is your SSCCE?!?!
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset 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

Get 10% off all 4D Systems TFT screens this month: use discount code MAJENKO10

Global Moderator
Dallas
Offline Offline
Shannon Member
*****
Karma: 207
Posts: 12909
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

Quote
What advantages does it have?
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 Offline
God Member
*****
Karma: 31
Posts: 887
Old, decrepit curmugeon
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset 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 library available at: http://code.google.com/p/avr-hardware-random-number-generation/

Current version 1.0.1

Offline Offline
Edison Member
*
Karma: 48
Posts: 1628
View Profile
 Bigger Bigger  Smaller Smaller  Reset 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 Offline
Faraday Member
**
Karma: 67
Posts: 3694
View Profile
 Bigger Bigger  Smaller Smaller  Reset 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 Offline
God Member
*****
Karma: 31
Posts: 887
Old, decrepit curmugeon
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset 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 library available at: http://code.google.com/p/avr-hardware-random-number-generation/

Current version 1.0.1

Pages: [1]   Go Up
Jump to: