# 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[0] || 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 **************************************************