Random number Generation with RNG
I would like to mention a question that posed on stackoverflow a year back, with a slight change.
Given a function which produces a random integer in the range 0 to 4, write a function which produces a random integer in the range 0 to 6.
Simply, we have let ran5() = new Random().Next(5), we would like to write ran7 using ran5, and without any other random number generator
The answers are rather interesting for this question, as it is important to have a uniformly distributed random number generator.
The first attempt, is a naive way to generate the random number by defining the sample set small.
//random number generator with 6 numbers let ran = new Random() let random5() = ran.Next(5) //naive let rantbl = [| 0 .. 6 |] let rec random7() = let i,j = random5(), random5() let sum = i + j if sum < rantbl.Length then rantbl.[sum] else random7()
Now, if you run the sample, it will generate the random numbers to 7 just fine, but it won’t be uniformly distributed, and will converge to a number as we run infinite times.
However, if we define our initial set uniformly to match out number generator, in this case we can generate 5 numbers, so a set of 25, we can hit each element by the multiplication of those two generators
//based on let randomTable = [|for i in 0 .. 24 do if i / 7<3 then yield i % 7 else yield -1 |] let rec random7_2() = let i,j = random5(), random5() let index = i * 5 + j if randomTable.[index] <> -1 then randomTable.[index] else random7_2() let sampler sample = seq { for i in 0 .. 100000 do yield sample() }
val random5 : unit -> int
val rantbl : int array
val it : int array = [|0; 1; 2; 3; 4; 5; 6|]
val randomTable : int array
val it : int array = [|0; 1; 2; 3; 4; 5; 6; 0; 1; 2; 3; 4; 5; 6; 0; 1; 2; 3; 4; 5; 6; -1; -1; -1;
-1|]
val random7 : unit -> int
val random7_2 : unit -> int
val sampler : (unit -> ‘a) -> seq<'a>
We can estimate of the value of a random variable and predict the error, which is proportional to the iterations. Since we have 2 sets, we can analyse and compare their statistical properties.
let variance sample N = let mean = sample |> Seq.average_by (fun i-> float i) (sample |> Seq.sum_by (fun i->(float i - mean) * (float i - mean) )) / N let standardDeviation varian= sqrt (varian) let standardError sample = let N = float (Seq.length sample) let vari = variance sample N let stDev = standardDeviation vari stDev / (sqrt N) let sample = sampler random7 standardError(sampler random7 ) standardError (sampler random7_2) // uniform distribution let errorSet mySet = let N = Seq.length mySet |> float mySet |> Seq.count_by (fun e-> e) |> Seq.map (fun (i,j) -> i, (float j)/N * 100.0) |> Map.of_seq errorSet (sampler random7) errorSet (sampler random7_2)
val standardDeviation : float -> float
val standardError : seq -> float
val sample : seq
val errorSet : seq<'a> -> Map<'a,float>
day, 03/14 2010. Happy 
