[racket] Randomized bisimulation tests and Metropolis-Hastings random walk

From: Robby Findler (robby at eecs.northwestern.edu)
Date: Fri Jan 4 17:56:13 EST 2013

So maybe I should just have a smaller size bound? (the 10 in the 'gen-exp'
function)

Really, perhaps, what I should do is not have a smaller size bound but
instead just make the number of tests I do (32 in the currently pushed
thing) depend on how long I've been testing.

Robby


On Fri, Jan 4, 2013 at 4:42 PM, Neil Toronto <neil.toronto at gmail.com> wrote:

> On 01/04/2013 03:06 PM, Robby Findler wrote:
>
>> Very cool! I've run into this problem a few times.
>>
>> And here's an example where it happens right now ....
>>
>> http://drdr.racket-lang.org/**26021/collects/tests/future/**
>> random-future.rkt<http://drdr.racket-lang.org/26021/collects/tests/future/random-future.rkt>
>>
>
> Yeah, your problem is very similar. The difference is that in my case, I
> had averages and variance that changed with the number of tests I wanted to
> run. If I understand correctly how Redex generates terms, you're getting
> independent, random programs from a fixed distribution. It just happens
> that the distribution of program sizes has a *lot* of variance - it has a
> "fat tail".
>
> I'd try simple rejection sampling first:
>
>   (define gen-exp (let ([f (generate-term fut exp)])
>                     (λ ()
>                       (define t (f 10))
>                       (cond [(> (length (flatten t)) n)  (gen-exp)]
>                             [else  t]))))
>
> When I had n = 100 and a `printf' that printed expression sizes, I got
> output like this from running (gen-exp):
>
> 375
> 5092
> 45318
> 2331
> 2184
> 20
>
> I didn't see more than 13 rejections in about 30 samples (most were around
> 3-6), so the rejection loop seems fast enough.
>
> If you actually want unbounded program sizes, there are other rejection
> methods that'll thin the tail of your distribution without zeroing it out.
> But you probably don't want that.
>
> Neil ⊥
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20130104/cc73f8d3/attachment-0001.html>

Posted on the users mailing list.