2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 нелинейный рандом
Сообщение20.04.2014, 20:57 


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

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

 Профиль  
                  
 
 Re: нелинейный рандом
Сообщение20.04.2014, 21:53 
Заслуженный участник
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: нелинейный рандом
Сообщение20.04.2014, 22:10 


09/01/12
23
ИСН в сообщении #852334 писал(а):
Линейным рандомом достаём два значения, берём меньшее, другое выкидываем.

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

 Профиль  
                  
 
 Re: нелинейный рандом
Сообщение20.04.2014, 23:14 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: нелинейный рандом
Сообщение21.04.2014, 00:18 


09/01/12
23
ИСН в сообщении #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

 Профиль  
                  
 
 Re: нелинейный рандом
Сообщение21.04.2014, 01:08 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Вам нужна последовательность (псевдо)случайных чисел $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$.

 Профиль  
                  
 
 Re: нелинейный рандом
Сообщение21.04.2014, 01:25 
Заслуженный участник
Аватара пользователя


18/05/06
13435
с Территории
Можно так. А можно как я сразу сказал.

 Профиль  
                  
 
 Re: нелинейный рандом
Сообщение21.04.2014, 06:55 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: нелинейный рандом
Сообщение21.04.2014, 10:11 


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

ИСН, Вы правы, Ваш способ получения нужного варианта рандома работает)
Изображение
По скорости, вариант через интегрирование работает медленнее. Не критично-медленнее, но процентов на 30%.

 Профиль  
                  
 
 Re: нелинейный рандом
Сообщение21.04.2014, 12:26 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
ИСН в сообщении #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$, и он нам совершенно не нужен.

 Профиль  
                  
 
 Re: нелинейный рандом
Сообщение21.04.2014, 22:02 
Заслуженный участник


11/05/08
32166
Someone в сообщении #852532 писал(а):
более универсальный, пригодный в тех случаях, когда можно обратить функцию распределения,

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

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

(Оффтоп)

Someone в сообщении #852532 писал(а):
$U_{2n-1}$ и $U_{2n}$ с хорошей точностью независимы,

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

 Профиль  
                  
 
 Re: нелинейный рандом
Сообщение22.04.2014, 00:15 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва

(ewert)

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

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

 Профиль  
                  
 
 Re: нелинейный рандом
Сообщение22.04.2014, 05:57 
Заслуженный участник
Аватара пользователя


23/11/06
4171

(Оффтоп)

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

 Профиль  
                  
 
 Re: нелинейный рандом
Сообщение22.04.2014, 10:27 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва

(--mS--)

--mS-- в сообщении #852846 писал(а):
тоже очень хотелось наехать
Ну, значит, точно стал писать больше глупостей. Старею, однако.

--mS-- в сообщении #852846 писал(а):
квантильное преобразование принадлежит не Someone
В учебниках можно найти.
Someone в сообщении #852819 писал(а):
метод ИСН
В задачах встречается.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group