нелинейный рандом

[Smogg]

Есть вот такой примерный график распределения вероятности. Значения по оси игрек - не принципиальны. Важен только икс. То есть надо из линейного рандома (0 - RAND_MAX) сделать нелинейный на участке (0 - 5).


Попытки что-то понять лишь показали насколько я глубоко и надежно забыл школу(

[ИСН]

Линейным рандомом достаём два значения, берём меньшее, другое выкидываем.

-- менее минуты назад --

Возможны и другие варианты.

[Smogg]

ИСН в сообщении #852334 писал(а):

Линейным рандомом достаём два значения, берём меньшее, другое выкидываем.

Что-то я сомневаюсь, что график распределения получится линией, а не параболой... А так интересная идея, может куда-нибудь пригодится потом.

[ИСН]

График распределения не получится ничем, потому что такой штуки нет в природе. Зато есть график функции распределения и график плотности распределения; Вы про какой?

[Smogg]

ИСН в сообщении #852371 писал(а):

График распределения не получится ничем, потому что такой штуки нет в природе. Зато есть график функции распределения и график плотности распределения; Вы про какой?

В терминологии я не силен)

Цитата:

Функция f(x) - производная функции распределения – характеризует как бы плотность, с которой распределяются значения случайной величины в данной точке. Эта функция называется плотностью распределения (иначе – «плотность вероятности») непрерывной случайной величины X.

Немного подредактировал картинку -


Как я пытался изобразить, расстояние до линии по вертикали в точке Х должно показывать, насколько часто рандом попадает в эту точку.
1) Видимо, этот график называется графиком плотности распределения.
2) Площадь закрашенного треугольника должна быть равна 1. (или чему другому?)
3) Учитывая пункт 2 находим функцию линии (если $S == 1$, то линия пересекает ось У в точке 0.4)
4) Интегрируем и получаем функцию распределения(так?) $-x ^ 2/ 25 + 2 x / 5$
// Судя по графику, получилось что-то внятное: http://www.wolframalpha.com/input/?i=-t ... +*+t+%2F+5
...
6) теперь надо как-то пропустить стандартный рандом через подпрограмму GetTriangleRandom(rand()) и на выходе должно получится число от 0 до 5

[Someone]

Вам нужна последовательность (псевдо)случайных чисел $x_1,x_2,x_3,\ldots$, имеющих функцию распределения

$$F(x)=\begin{cases}0\text{ при }x\leqslant 0,\\ \frac{2x}5-\frac{x^2}{25}\text{ при }0<x\leqslant 5,\\ 1\text{ при }x>5.\end{cases}$$

И у Вас есть датчик (генератор) чисел, генерирующий последовательность (псевдо)случайных чисел $u_1,u_2,u_3,\ldots$ с равномерным распределением на полуинтервале $[0,1)$, то есть,

$$F_u(x)=\begin{cases}0\text{ при }x\leqslant 0,\\ x\text{ при }0<x\leqslant 1,\\ 1\text{ при }x>1.\end{cases}$$

Как превратить второе распределение в первое?
Существует много разных способов, эффективность которых зависит от конкретной функции $F$.
В Вашем случае достаточно эффективным будет способ, основанный на том, что если случайная величина $U$ имеет равномерное распределение на промежутке $[0,1)$, то случайная величина $X$, определяемая из уравнения $F(X)=U$, имеет функцию распределения $F_X(x)=F(x)$. Естественно, в вашем случае нужно брать тот корень, который лежит на промежутке $[0,5)$. То есть, вычислив $u_n$, Вы должны найти корень уравнения $\frac{2x}5-\frac{x^2}{25}=u_n$, принадлежащий промежутку $[0,5)$. Это и будет $x_n$.

[ИСН]

Можно так. А можно как я сразу сказал.

[--mS--]

А ещё можно генерировать пару случайных величин $(x,\,y)$ в прямоугольнике $[0,\,5]\times[0,\,0{.}4]$ (т.е. каждую координату независимо), и если $y<0{.}08(5-x)$, то брать $x$, а если больше, генерировать следующую пару.

Хотя совет от ИСН куда изящнее. И не надо много пар перебирать, одной хватит.

[Smogg]

Someone, Большое Спасибо за подробное объяснение! Про обработку случаев попадания в 0 и 5 я и не думал.

ИСН, Вы правы, Ваш способ получения нужного варианта рандома работает)

По скорости, вариант через интегрирование работает медленнее. Не критично-медленнее, но процентов на 30%.

[Someone]

ИСН в сообщении #852425 писал(а):

Можно так. А можно как я сразу сказал.

Конечно. можно: если датчик хороший, то $U_{2n-1}$ и $U_{2n}$ с хорошей точностью независимы, и для величины $Y_n=\min\{U_{2n-1},U_{2n}\}$ получаем

$$F_{Y_n}(y)=P(\{X_{2n-1}<y\}+\{X_{2n-1}<y\})=P(X_{2n-1}<y)+P(X_{2n}<y)-P(X_{2n-1}<y)\cdot P(X_{2n}<y)=$$

$$=F_u(y)+F_u(y)-F_u(y)\cdot F_u(y)=2F_u(y)-F_u^2(y)=\text{ (при $0\leqslant y\leqslant 1$) }=2y-y^2,$$

и плотность вероятности $Y$ равна $f_Y(y)=F'_Y(y)=2(1-y)$. Осталось только умножить на $5$:

$$x_n=5\min\{u_{2n-1},u_{2n}\}.$$

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

-- Пн апр 21, 2014 13:33:08 --

Smogg в сообщении #852503 писал(а):

Про обработку случаев попадания в 0 и 5 я и не думал.

Ну, обычно про эту "обработку" можно не думать, но иногда бывает полезно точно знать, что, например, значение $0$ может встретиться, а значение $1$ совершенно точно нет. Однако здесь дело не в обработке граничных значений, а в том, что указанное квадратное уравнение (с учётом неравенства $0\leqslant u<1$) имеет два корня, один из которых больше $5$, и он нам совершенно не нужен.

[ewert]

Someone в сообщении #852532 писал(а):

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

Это как раз менее универсальный. Наиболее универсальный напомнила --mS--
(метод "приём-отклонение"); он работает практически всегда, разве что иногда лишь после некоторых извивов.
Наименее универсальный -- метод ИСН, но он и наиболее эффективный; он эффективнее метода --mS-- даже страшно сказать -- в целых два раза.

-- Пн апр 21, 2014 23:16:08 --

(Оффтоп)

Someone в сообщении #852532 писал(а):

$U_{2n-1}$ и $U_{2n}$ с хорошей точностью независимы,

Мне всегда казалось, что эти страшилки (а когда-то они были реальны, помню) -- уже очень давно остались в прошлом.

[Someone]

(ewert)

ewert в сообщении #852758 писал(а):

Это как раз менее универсальный. Наиболее универсальный напомнила --mS--

Несколько загадочное для меня замечание, никак не вытекающее из того, что писал я. Я обсуждал изящный метод ИСН и сказал о своём предложении, что это более универсальный метод (чем метод ИСН), но не утверждал, что он наиболее универсальный. Метода, предложенного --mS--, я никаким боком не касался.

P.S. Я что-то не пойму. В последнее время я стал время от времени подвергаться каким-то наездам со стороны некоторых участников форума. Что, я стал писать больше глупостей?

[--mS--]

(Оффтоп)

Не ссорьтесь, девочки! (с)
И что-то меня коробит от фраз "метод --mS--" и т.д. Я ни разу не претендую на то, чтобы метод acceptance-rejection назывался моим. Полагаю, и квантильное преобразование принадлежит не Someone. Что до наездов - то тоже очень хотелось наехать после пассажа в стиле КО о распределении минимума, да ещё и зачем-то для равномерного на $[0,\,1]$. Подставляетесь

[Someone]

(--mS--)

--mS-- в сообщении #852846 писал(а):

тоже очень хотелось наехать

Ну, значит, точно стал писать больше глупостей. Старею, однако.

--mS-- в сообщении #852846 писал(а):

квантильное преобразование принадлежит не Someone

В учебниках можно найти.

Someone в сообщении #852819 писал(а):

метод ИСН

В задачах встречается.