algorithm - 一个偏序集的元素是最大的概率？

Question

给定一个 partially-ordered set (poset)，假设所有线性扩展的可能性相同，估计元素在线性扩展中最顶层的概率的算法是什么？

Answer 1

近似计数似乎比近似采样慢，所以你的算法应该简单地基于拒绝采样:从所有线性扩展的集合中重复(近似地)随机抽样，并直接计算你的元素所在的比例最顶层。

选择每个随机样本当然可以在 O(n^3 log n) 内完成，因此根据您需要的准确度，它最终会比您引用的 O(n^6) 更快。