从离散分布函数中绘制一个随机数,该函数存储为F#中的一系列概率

Question

存在有限长度N的给定浮点序列(在0和1之间),其表示在整数0..N-1上的分布函数.我们试图从这个分布中抽取一个随机数.一种方法是在[0,1](浮点)中绘制一个均匀的随机变量,然后计算该数字的逆累积分布函数.

如果分发在数组中,代码看起来像这样:

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

其中distribution是分布函数,draw是统一的[0,1]数.

当分布是任何序列时,如何重写此功能？显然我可以创建一个临时数组,但它似乎不是一个优雅的解决方案......

Answer 1

您的matched功能是搜索过程.您不必分解序列来搜索适当的索引; Seq模块的高阶函数可以帮助您:

/// 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)

在最坏的情况下,您仍然可以枚举整个序列Seq.length.我认为Seq.length distribution-1如果可能的话,最好换成已知的常数.