Электронный миссионер

Для отладки, чтобы не гонять прибор, мне нужен генератор случайных чисел с экспоненциальным распределением. Вот я его реализовал. Поглядел, удовлетворяет ли он моим требованиям.

From:

Это еще ничего. Мне как-то в одной модели нужен был генератор случайных чисел с распределением сложной формы (моделирование процесса получения УФ-спектра на космическом спектрографе с МКП+КПА в качестве светоприемника). С месяц, наверное, голову ломал, как это победить. А решение оказалось простым донельзя.

P.S. На самом деле получающиеся при помощи drand48 распределения не совсем случайны. Есть небольшие отклонения в пределах 1..2% от желаемой функции (а все от того, что псевдослучайные числа, генерируемые компьютером, распределены-таки не совсем равномерно). В принципе, если каждые ~1000..10000 значений делать переинициализацию генератора с использованием /dev/random, получается лучше.

From:

Если не секрет как? Ультралюбопытно!

За постскриптум спасибо, учту!

From:

> Если не секрет как?

Довольно грубо строилась зависимость численная F(x), из которой интерполяцией сплайнами и находилась обратная функция x(F). Модель делал в Octave, поэтому считалось очень долго: экспозиция в ~1 секунду для довольно яркой звезды обсчитывалась около суток. Если бы это перенести на CUDA, было бы намного быстрей. Но, к сожалению, я эту тему забросил — пока у меня и других забот хватает.

From:

Сейчас читаю один диссер, там говорится о том, что это очень важная задача. И как я предполагаю наукоёмкая

From:

Ну, обычная обратная задача.
С ними уже много лет борются - и будут бороться. Но, благодаря нарастающему развитию вычислительной техники, подозреваю, что теория решения обратных задач постепенно завянет, переметнувшись на численные методы.

From:

Как раз прочитал эту тему, оказывается что не всё так просто:
При моделировании поведения какого-либо процесса или объекта, находяш;егося под воздействием случайных факторов, возникает задача получения случайных чисел, закон распределения которых совпадает с законом распределения, наблюдаемым в эксперименте
...
Один из подходов к решению указанной задачи заключается в нахождении некоторой аппроксимирующей функции, которая описывает экспериментальный закон распределения с требуемой точностью. На основе этой функции искомые случайные числа могут быть получены из равномерных случайных чисел методом обратной функции [7].
Несмотря на кажущуюся простоту такого подхода, при его практической реализации возникает ряд проблем, связанных, в первую очередь, с ограничениями, которые накладываются на функции,
аппроксимирующие плотность распределения и функцию распределения. К
ЭТИМ ограничениям относятся:. Кроме того,
возникают проблемы, связанные с низкой устойчивостью получаемых
решений.

Далее там рассматриваются решение с помощью полиномов Эрмита.

После чего я себе повскрывал мозг (не очень сложно, но муторно). Если, что, дисер Димаки, Андрей Викторович "Аппаратно-программный комплекс для моделирования и исследования стохастических процессов", 2006 г. . Купил в интернетах за 500 рублей. При большом желании могу поделиться :).

From:

Все зависит от того, какая вам нужна точность. Если погрешности в 0.5..1% будет многовато, то действительно, придется выкручиваться через аппроксимацию полиномами и аналитическое решение.
Кстати, в диссертациях зачастую подборка библиографии бывает куда ценнее самого содержимого работы.

From:

>> Кстати, в диссертациях зачастую подборка библиографии бывает куда ценнее самого содержимого работы.

Ради библиографии и искал :)

From:

Кстати, разве там не 1/λ?
В википедии пишут, что для экспоненциального распределения f(x) = λexp(-&lambda x); а F(x) = 1 - exp(-λx).
Чтобы из равномерного распределения получить распределение с заданной F(x), нам необходимо найти обратную функцию x(F) и вместо F подставлять случайные значения, распределенные равномерно, тогда мы получим x - величину, распределенную как нам нужно.
В данном случае имеем: log(F-1) = -λx → x = -1/λ·F (замена F ←→ [F-1] правомерна, т.к. распределение F - равномерное).

From:

Не совсем верно:
F(x) = 1 - exp(-λx)

Отсюда

exp(-λx)=1-F(x) - здесь был недочёт

после получается

ln(1-F(x))=-λx

И после преобразований получилось

x=-ln(1-F(x))/λ

Согласен, что в формуле ошибка.

From:

Прикольно. Но теорийку надо почитать. Скачайте уж Вентцель, чтоли.
Главное не распределение, а период повторения, его проверить очень легко. Скорее всего на гистограмме получилась пара, а то и тройка периодов. Что в общем сводит оценку гистограммой к смешной картинке. Все бьются за большой период повторения, а распределение как-то само получается.

From:

Вентцель настольная книга (точнее книги), но про период повторения не помню. Если не сложно напомните.

From:

Это не из Вентцель.
Но главное, все функции генерации случайных переодичные, период может быть большим, а может быть и не очень. Все псевдослучайные считаются слычайными только внутри периода. Потому и переходят к супердлинным числам высокой разрядности, чтобы удлинить интервал. Например Майкрософт бейсик лохматого года - период около 32000 (2 в 15 степени - 1). Пример, берем весь период и десяток чисел из второго, очевидно, что распределение нарушается.
Проверить легко, запоминаем n и n+1, крутим числа до повторения пары.
Вообще с псевдослучайными все общаются на ты, что неверно. Достаточно округлить их и получится последовательность с еще более коротким периодом или они перестануь быть псевдослучайными. И другие интересные приколы.

From:

Я понял. Есть Алгоритм Л'Экюера, который обеспечивает длинну последовательности как 10^18: http://algorithm.narod.ru/random/uniform.html

Единственное, что я поленился раскурить как инициализировать разные стартовые значения.

Для использования drand48() товарищ

eddy_em здесь в комментариях советует его реинициализировать каждые 1000-10000 значений.

From:

Любой можно реинициализировать, но будет ли эта штука псевдослучайной последовательностью?
Я еще не критиковал Миллион значений на гистограммк в 10 интервалов? Самое время.

From:

>>Любой можно реинициализировать, но будет ли эта штука псевдослучайной последовательностью?

Если реинициализировать другой псевдослучайной последовательностью (там идёт реинициализация файлов /dev/urandom, который представляет собой энтропию системы), то длинна последовательности увеличивается в разы. Для моих целей длинны последовательности в 10^10 хватит за глаза и за уши.

>>Я еще не критиковал Миллион значений на гистограммк в 10 интервалов? Самое время.

Быть может потыкаете носом, где почитать как выбрать количество интервалов относительно количества значений?

From:

Начните с проверки периода.

From:

Не думаю что это важно.

From:

О чем тогда говорить. Миллион значений генерить не лень для картинки, а проверить саму последовательность нет времени и желания.
Вентцель не только полезная книга, но еще и хорошая подставка под шкаф.

From:

Цитирую: При этом для современных компьютеров период генерируемой последовательности становится недостижимым (длина оценивается по порядку как 10^18).

Зачем проверять, если есть уже проверенное. Меня больше интересует, как выбирать количество интервалов.

Я вам могу хоть миллиард значений сгенерировать :)

From:

Архисильно сомневаюсь, что вы сможете за сознательную жизнь замкнуть последовательность

From: