<div dir="ltr">Very cool! I've run into this problem a few times.<div><br></div><div style>And here's an example where it happens right now ....</div><div style><br></div><div style><a href="http://drdr.racket-lang.org/26021/collects/tests/future/random-future.rkt">http://drdr.racket-lang.org/26021/collects/tests/future/random-future.rkt</a><br> </div><div><br></div><div>Robby</div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Jan 4, 2013 at 3:45 PM, Neil Toronto <span dir="ltr"><<a href="mailto:neil.toronto@gmail.com" target="_blank">neil.toronto@gmail.com</a>></span> wrote:<br> <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">I get excited about applying statistics to programming. Here's something exciting I found today.<br> <br> I'm working on a Typed Racket implementation of Chris Okasaki's purely functional random-access lists, which are O(1) for `cons', `first' and `rest', and basically O(log(n)) for random access. I wanted solid randomized tests, and I figured the best way would be bisimulation: do exactly the same, random thing to a (Listof Integer) and an (RAList Integer), then ensure the lists are the same. Iterate N times, each time using the altered lists for the next bisimulation step.<br> <br> There's a problem with this, though: the test runtimes are all over the place for any fixed N, and are especially wild with large N. Sometimes it first does a bunch of `cons' operations in a row. Because each bisimulation step is O(n) in the list length (to check equality), this makes the remaining steps very slow. Sometimes it follows up with a bunch of `rest' operations, which makes the remaining steps very fast.<br> <br> More precisely, random bisimulation does a "simple random walk" over test list lengths, where `cons' is a step from n to n+1 and `rest' is a step from n to n-1. Unfortunately, the n's stepped on in a simple random walk have no fixed probability distribution, and thus no fixed average or variance. That means each bisimulation step has no fixed average runtime or fixed variation in runtime. Wildness ensues.<br> <br> One possible solution is to generate fresh test lists from a fixed distribution, for each bisimulation step. This is a bad solution, though, because I want to see whether RAList instances behave correctly *over time* as they're operated on.<br> <br> The right solution is to use a Metropolis-Hastings random walk instead of a simple random walk, to sample list lengths from a fixed distribution. Then, the list lengths will have a fixed average, meaning that each bisimulation step will have a fixed average runtime, and my overall average test runtime will be O(N) instead of wild and crazy.<br> <br> First, I choose a distribution. The geometric family is good because list lengths are nonnegative. Geometric with p = 0.05 means list lengths should be (1-p)/p = 19 on average, but are empty with probability 0.05 and very large with very low probability.<br> <br> So I add these two lines:<br> <br> (require math/distributions)<br> <br> (define length-dist (geometric-dist 0.05))<br> <br> In a Metropolis-Hastings random walk, you step from n to n' with probability min(1,P(n')/P(n)); this is called "accepting" the step. Otherwise, you "reject" the step by staying in the same spot. Adding this new test takes only two defines and a `cond':<br> <br> (define r (random 5)) ; Randomly choose an operation<br> (cond<br> [(= r 0)<br> ;; New! Only cons with probability P(n+1)/P(n)<br> (define n (length lst))<br> (define accept (/ (pdf length-dist (+ n 1))<br> (pdf length-dist n)))<br> (cond [((random) . < . accept)<br> .... Accept: cons and ensure continued equality ....]<br> [else<br> .... Reject: return the same lists ....])]<br> [(= r 1)<br> .... Accept: `rest' each list and ensure continued equality ....]<br> .... Other random operations ....)<br> <br> I left off the acceptance test for `rest' because P(n-1) > P(n) ==> P(n-1)/P(n) > 1, so the test would always pass. (This is because the geometric distribution's pdf is monotone. If I had chosen a Poisson distribution, which has a bump in the middle, I'd have to do the acceptance test for both `cons' and `rest'.)<br> <br> I instrument the test loop to record list lengths, verify that their mean is about 19, and do some density plots vs. the geometric distribution. It all looks good: the randomized bisimulation test does indeed operate on lists whose length is distributed Geometric(0.05), so the overall average test runtime is O(N), and it still tests them as they're operated on over time.<br> <br> Neil ⊥<br> ____________________<br> Racket Users list:<br> <a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/<u></u>users</a><br> </blockquote></div><br></div>