next topic »

[on:]

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

[Reply #1 on:]

What advantages does it have?

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

[Reply #2 on:]

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

[Reply #3 on:]

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

[Reply #4 on:]

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.

[Reply #5 on:]

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

[Reply #6 on:]

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

[Reply #7 on:]

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.

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

[Reply #8 on:]

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.

[Reply #9 on:]

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.

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.