Tom Pledger wrote:
>
> Hi.
>
> <RANT>
>
> Simon Peyton-Jones writes:
> > [...]
> >
> > Suppose next produced output in the range 0..16. (It's specified
> > to produce "at least 30 bits", but the argument still holds.)
> > Suppose we want random numbers in the range 0..10. We can't just
> > take "mod 11" because that would produce too many values in the
> > range 0..5. Indeed, if we don't know the range of next's result,
> > we simply cannot generate uniformly distributed random numbers.
> >
> > The fix is [add a member function "genRange :: g -> (Int,Int)" to
> > the class RandomGen g, and remove the "next yields at least 30
> > bits" requirement]
> >
> > I regret the need for this change. Does anyone object to it? More
> > particularly, can anyone think of a flaw?
>
> I object, because I don't think there's a problem, either with bias or
> with the 30 bit requirement.
>
> It's quite common, when transforming one type of deviate into another,
> to discard a few unsuitable input values before finding some which can
> produce valid output.
>
> For example, there's a transformation [PFTV] which takes two uniform
> deviates, and returns either two normal (Gaussian) deviates (with
> probability pi/4), or nothing.
>
> A similar approach can be taken, for getting uniform deviates (of
> types in Enum) from a generator in Haskell, without the bias. Just
> keep applying next, until you get an Int whose 30 trusted bits don't
> introduce the bias.
> (You may be dealing with a range size greater than 2^30, but that's
> another story. It means consuming more than one Int at a time, from
> your generator's sequence.)
>
> The 30 bit requirement is a good practical guideline.
This sounds similar to Fergus Henderson's suggestion, for which he
supplied code. Please see my reply to him, and respond to my comments
if you like. To me, these solutions seem very inefficient and
statistically dangerous, compared to just knowing the RNG's range (which
is almost always fixed) ahead of time. It seems to me that you have to
throw out at least two numbers from next for every "good" number you
get.
>
> Koen Claessen writes:
> > [...]
> >
> > If we're fixing bugs in the part about Random.hs in the Haskell'98
> > library report, we might as well fix the following bug (spotted by
> > John Hughes, but not present at the bug page).
> >
> > About "split", it says:
> >
> > "The split operation allows one to obtain two distinct random
> > number generators. This is very useful in functional programs
> > (for example, when passing a random number generator down to
> > recursive calls), ..."
> >
> > This is not enough. An early Hugs implementation of "split" [...]
> >
> > [...]
> >
> > gen1
> > / \
> > gen1 gen2 -- once
> > / | | \
> > gen1 gen2 gen2 gen3 -- twice
> >
> > In fact, they will produce the *same* generator "gen2" on
> > both sides, which will create an undesired dependency
> > between the two recursive calls.
>
> There are two respectable basic ways of getting a generator value:
> mkStdGen (and its counterparts) and next. For most generators, it
> seems perverse to create an entirely new way for split.
>
> So, if there's to be any change to RandomGen, it should become:
>
> class RandomGen g where
> mkGen :: Int -> g
> next :: g -> (Int, g)
> split :: g -> (g, g)
> split g = (mkGen seed, g') where (seed, g') = next g
>
> That deals with the Indistinct Split problem, but leaves open the
> possibility of unusually fancy split implementations for unusually
> fancy generators.
I like this; it takes away the necessity to implement split for each
RNG, with varying quality. Meanwhile an RNG with a good built-in split
operation can supply it.
> A corresponding report change is from this:
>
> "The split operation allows one to obtain two distinct random
> number generators."
>
> to this:
>
> "The split operation allows one to obtain two random number
> generators. The second of these is new, and the first is very
> probably new, and very probably distinct from the second."
>
> </RANT>
>
> Regards,
> Tom
>
> [PFTV]
> Press, Flannery, Teukolsky, Vetterling
> Numerical Recipes in C - The Art of Scientific Computing
> Cambridge University Press
> 1988
