f# - 从存储为 F# 中的概率序列的离散分布函数中提取随机数

Question

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

如果分布在一个数组中，代码将如下所示：

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一个已知的常数。