Drawing a random number from a discrete distributi

问题:

There is a given sequence of floats (between 0 and 1) of finite length N which denotes a distribution function over integers 0..N-1. We are trying to draw a random number from this distribution. One way of doing it is to draw a uniform random variable in [0, 1] (float), and then calculate the inverse cumulative distribution function for that number.

If the distribution was in an array, the code would look something like this:

let matched distribution draw =
  let rec matchRest distribution draw start = 
    if start = Array.length distribution then start-1
    else
      let left = draw - distribution.[start]
      if left <= 0 then start
      else matchRest distribution left (start+1)
  matchRest distribution draw 0

where distribution is the distribution function and draw is the uniform [0,1] number.

How can I rewrite this function to work when distribution is any sequence? Obviously I could create a temporary array, but it doesn't seem to be an elegant solution...

回答1:

Your matched function is a search procedure. You don't have to break down the sequence to search for an appropriate index; high-order functions from Seq module could help you:

/// Taken from http://missingfaktor.blogspot.in/2012/02/f-option-cheat-sheet.html
let getOrElse d = function
    | Some a -> a
    | None -> d

let matched distribution draw =
    distribution 
    |> Seq.scan (fun (s, d0) d -> (s+1, d0-d)) (0, draw)
    |> Seq.tryPick (fun (s, d) -> if d <= 0 then Some s else None)
    |> getOrElse (Seq.length distribution-1)

In the worst case, you still enumerate the whole sequence via Seq.length. I think it's better to change Seq.length distribution-1 to a known constant if possible.