Параллельные нормальные распределения
Я работаю над симуляцией, в которой большая задача выполняется серией независимых небольших задач параллельно или последовательно. Меньшее время выполнения задачи следует за нормальным распределением со средним временем, скажем, "t" и дисперсией, скажем, "v". Я понимаю, что если эта задача повторяется последовательно, например, "n" раз, то новое общее распределение времени является нормальным со средним значением t*n и дисперсией v*n, что хорошо, но я не знаю, что происходит со средним и дисперсией если набор одних и тех же задач выполняется одновременно / параллельно, прошло некоторое время с момента появления класса stat stat. Есть ли хороший / быстрый способ найти новое распределение времени для "n" этих независимых нормально распределенных задач, выполняемых параллельно?
3 ответа
Если задачи выполняются независимо и параллельно, распределение времени до завершения зависит от времени самого длинного процесса.
К сожалению, функция max не обладает особенно хорошими свойствами для теоретического анализа, но если вы уже симулируете, есть простой способ сделать это. Для каждого подпроцесса i со средним значением t_i и дисперсией v_i, проведите время до завершения для каждого i независимо, затем посмотрите на самое большое. Повторяя это много раз, вы получите кучу сэмплов из максимального распределения, которое вас интересует: вы можете вычислить ожидание (среднее), дисперсию или что угодно.
Вопрос в том, каково распределение максимального (наибольшего значения) случайного времени завершения. Функция распределения (т. Е. Неопределенный интеграл от плотности вероятности) максимума набора независимых случайных величин является просто произведением функции распределения каждой переменной. (Функция распределения минимума составляет всего 1 - (произведение (1 - функция распределения)).)
Если вы хотите найти время, такое, что вероятность (максимум> время) = (какое-то заданное значение), вы можете решить это точно или прибегнуть к числовому методу. Тем не менее, численное решение уравнения (например, метод деления пополам) выполняется намного быстрее и точнее, чем метод Монте-Карло, как вы упоминали, что вы уже пробовали.
Это не совсем проблема программирования, но вам нужны распределения статистики порядка нормальных случайных величин, т. Е. Ожидаемое значение / дисперсия / и т. Д. Задания, которое заняло самое длинное, самое короткое и т. Д. Это решенная проблема для идентичных средних и дисперсий, потому что вы можете масштабировать все случайные величины до стандартного нормального распределения, которое было проанализировано.
Вот статья, которая дает вам ответ, хотя вам понадобятся некоторые математические знания, чтобы понять это:
Алгоритм AS 177: ожидаемая статистика нормального порядка (точная и приблизительная) JP Royston. Журнал Королевского статистического общества. Серия C (Прикладная статистика) Том. 31, № 2 (1982), с. 161-165
Смотрите этот пост на stats.stackexchange для получения дополнительной информации.