平行正态分布

Question

我正在做一个模拟，在这个模拟中，一个大的任务是由一系列独立的小任务并行或串联完成的。较小任务的完成时间服从正态分布，平均时间为"t“，方差为"v”。我知道，如果这项任务连续重复"n“次，那么新的总时间分布是正态的，均值为t*n，方差为v*n，这很好，但我不知道如果一组相同的任务同时/并行完成，均值和方差会发生什么，因为已经有一段时间没有prob stat类了。有没有一种很好的/快速的方法来找到"n“个独立的正态分布并行任务的新时间分布？

Answer 1

如果任务是独立和并行执行的，则直到完成的时间分布取决于最长进程的时间。

不幸的是，对于理论分析，max函数没有特别好的属性，但如果您已经在模拟，那么有一种简单的方法可以做到这一点。对于具有mean t_i和variance v_i的每个子过程I，分别绘制每个I的完成时间，然后查看最大值。重复多次会得到你感兴趣的最大分布中的一堆样本:你可以计算期望(平均值)、方差或任何你想要的东西。

Answer 2

问题是，随机完成时间的最大(最大值)分布是什么。一组独立随机变量的极大值的分布函数(即概率密度的不定积分)恰好是每个变量的分布函数的乘积。(最小值的分布函数正好是1-( (1 -分布函数)的乘积)。)

如果你想找到一个概率(maximum> time) =(某个给定值)的时间，你也许能够精确地解决这个问题，或者求助于一种数值方法。尽管如此，数值求解方程(例如二分法)比蒙特卡罗方法快得多，也更准确，正如你所说的，你已经尝试过了。

Answer 3

这并不是一个确切的编程问题，但您要寻找的是正态随机变量的分布，即所需时间最长、最短的作业的期望值/方差/等。这是一个解决了均值和方差相同的问题，因为您可以将所有随机变量缩放到标准正态分布，这已经被分析过了。

这篇论文给出了答案，尽管你需要一些数学知识才能理解它：

Algorithm AS 177: Expected Normal Order Statistics (Exact and Approximate) J. P. Royston皇家统计学会杂志。C系列(应用统计)第31卷第2期(1982)，第161-165页

有关详细信息，请参阅stats.stackexchange上的this post。