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

Leave a Reply

Your email address will not be published. Required fields are marked *


*