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

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

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 ⊥