# Discrete Event Probablities

My colleague, David, had an interesting problem:

“I want to simulate exceptional events (e.g. I/O errors) at predictable rates.

For example, if an error should occur 33% of the time, it should be predictable like: `ERROR, ok, ok, ERROR, ok, ok, ...`

Or at 50% error rate: `ERROR, ok, ERROR, ok, ...`

devdriven:

“Pseudo-random function `p(t)` in range `[0,1)` at time `t` and `P` is the probability of the event (e.g. I/O error) then: `event?(t) = p(t) < P`.

Pseudo-random numbers are predictable if you know the seed."

David:

"Not really what I had in mind. There's got to be a better way..."

devdriven:

"If `p(t)` is an event probability at `t`, `p(t)` could be defined as `p(t) = (t modulo 100) / 100`.

However `p(t) < P` is not "evenly" distributed over `t in [0,100)`.

For `P = .50`, the stream of events would be: `ERROR` (50 times) `..., ok` (50 times)`, ...`

The algorithm should distribute `P * 100` events "evenly" over 100 time values. What is `P`? 33% is 33/100, 50% is 50/100: ratios.

The slope of a 2D line between two discrete points is a ratio!

Bresenham's Line Algorithm does just this when rasterizing lines to pixels -- how does it work?

It uses discrete differential error tracking to determine how far `y` is from a linear function: `f(x) = slope * x`. The change of the error's sign tells us when to increment `y` (e.g.: emit an event to move up one pixel). This technique can be extended to any polynomial by cascading errors for each derivative. It is a robust, iterative solution that guarantees correctness and repeatability over intervals of `slope.numerator * slope.denominator`."

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 # event-bres.rb require 'rational'   def bres ratio Enumerator.new do | yielder | # Note: error = 0 means zero_crossing is always true for first elem. # This can be balanced by using error = ratio.denominator / 2 error = 0 loop do error -= ratio.numerator if zero_crossing = error < 0 error += ratio.denominator end yielder.yield zero_crossing end end end   ratio = Rational(33, 100) stream = bres(ratio) y = 0 stream.take(15).each do | event | y += 1 if event puts "%.2f %s %*s" % [ ratio.to_f, event ? 'X' : ' ', y, '*' ] end puts   (0..100).step((ARGV || 10).to_i).each do | percent | ratio = Rational(percent,100) stream = bres(ratio) count = stream.take(n = 100).count{|x| x} puts "%.2f %.2f %s" % [ ratio.to_f, count.to_f / n, stream.take(50).map{|x| x ? '*' : ' '}*'' ] end```

Outputs:

``` #\ ruby event-bres.rb
0.33 X *
0.33   *
0.33   *
0.33 X  *
0.33    *
0.33    *
0.33 X   *
0.33     *
0.33     *
0.33 X    *
0.33      *
0.33      *
0.33 X     *
0.33       *
0.33       *

0.00 0.00
0.10 0.10 *         *         *         *         *
0.20 0.20 *    *    *    *    *    *    *    *    *    *
0.30 0.30 *  *  *   *  *  *   *  *  *   *  *  *   *  *  *
0.40 0.40 * *  * *  * *  * *  * *  * *  * *  * *  * *  * *
0.50 0.50 * * * * * * * * * * * * * * * * * * * * * * * * *
0.60 0.60 ** * ** * ** * ** * ** * ** * ** * ** * ** * ** *
0.70 0.70 *** ** ** *** ** ** *** ** ** *** ** ** *** ** **
0.80 0.80 **** **** **** **** **** **** **** **** **** ****
0.90 0.90 ********* ********* ********* ********* *********
1.00 1.00 **************************************************
```