Go Down

Topic: Interesting probability design pattern (Read 1 time)previous topic - next topic

wanderson

Jun 04, 2012, 09:02 pm
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: [Select]

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

However, my colleague used the following approach:
Code: [Select]

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: [Select]

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);
}
}

AWOL

#1
Jun 04, 2012, 09:07 pm
Quote

Depends on how expensive it is to call "random", but I'd probably say "very few".
"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.
I speak for myself, not Arduino.

wanderson

#2
Jun 04, 2012, 09:12 pm

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...

winner10920

#3
Jun 04, 2012, 09:24 pm
Definetly can't see any advantage other than making it a little more straightfoward

majenko

#4
Jun 04, 2012, 09:24 pm
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.

#5
Jun 04, 2012, 09:33 pm
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).

wanderson

#6
Jun 04, 2012, 09:45 pm
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...

el_supremo

#7
Jun 04, 2012, 10:07 pm
Changing this:
Code: [Select]
if (random(20) == random(20))
Event Happended

to this:
Code: [Select]
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
Don't send me technical questions via Private Message.

wildbill

#8
Jun 04, 2012, 10:15 pm
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.

wanderson

#9
Jun 04, 2012, 10:20 pm

Changing this:
Code: [Select]
if (random(20) == random(20))
Event Happended

to this:
Code: [Select]
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.

Go Up