[racket] Neil: Is there a sensible way to sample from the naturals? EOM

On 02/19/2014 03:33 PM, Sam Tobin-Hochstadt wrote:
> On Wed, Feb 19, 2014 at 5:02 PM, Neil Toronto <neil.toronto at gmail.com> wrote:
>>
>>    (: random-natural/no-mean (-> Real Natural))
>>    (define (random-natural/no-mean prob-zero)
>>      (define n (exact-floor (sample (geometric-dist prob-zero))))
>>      (define m1 (assert (expt 2 n) integer?))
>>      (define m0 (quotient m1 2))
>>      (max 0 (random-integer m0 m1)))
>>
>> The "max 0" keeps TR from complaining that `random-integer' returns an
>> Integer.
>
> These both look like places where `math` could do better here with types.
>
> Specifically, `geometric-dist` should probably say that it produces
> non-negative floats.  That would fix the need for the `assert`.

Ah, of course.

> Second, `random-integer` could have the type: (case-> (Natural Natural
> -> Natural) (Integer Integer -> Integer)).  That would fix the need
> for `max`.

I hadn't thought of doing that.

When I wrote that function, the math library was taking 45% of the total 
compilation time, so I had stopped considering case-> types that weren't 
strictly necessary. I know TR has gotten faster in the meantime, so it 
might be time to revisit making some of the types more precise.

Uh, after I finish writing my dissertation. :) I'm so close...

> Finally, I don't understand why `geometric-dist` returns floats and
> not integers, anyway.

The inverse CDF of any geometric distribution evaluated at 1 should be 
infinity, as here:

 > (inv-cdf (geometric-dist 0.5) 1)
+inf.0

My original reasoning was that I didn't want to deal with types like (U 
Natural +inf.0) or ask users to deal with them. But now I realize that 
it should be (U Natural Positive-Infinity):

 > (inv-cdf (geometric-dist 0.5) 1)
+inf

i.e. the answer should be exact, not inexact.

Neil ⊥