2014 dxdy logo

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

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




 
 Коррелятор для псевдо случайных чисел
Сообщение04.07.2012, 14:47 
Всем привет!

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

 
 
 
 Re: Коррелятор для псевдо случайных чисел
Сообщение04.07.2012, 15:44 
Аватара пользователя
По-моему, там всегда множество разных тестов.
И, как только появляется генератор, успешно проходящий все тесты, вскоре разрабатывается новый тест, который монетка проходит, а этот генератор -- нет. :D

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

 
 
 
 Re: Коррелятор для псевдо случайных чисел
Сообщение04.07.2012, 16:03 
svv в сообщении #592051 писал(а):
Где-то там в бездонной глубине компьютерного железа есть какие-то шумы,

Ну они же наверняка небелые, так что всё равно шило на мыло.

 
 
 
 Re: Коррелятор для псевдо случайных чисел
Сообщение04.07.2012, 16:08 
svv в сообщении #592051 писал(а):
Давно уже читал, что некоторые программы могут выдавать настоящие случайные числа. Где-то там в бездонной глубине компьютерного железа есть какие-то шумы, которые можно регистрировать и превращать в случайную числовую последовательность.


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

 
 
 
 Re: Коррелятор для псевдо случайных чисел
Сообщение04.07.2012, 16:31 
Аватара пользователя
svv в сообщении #592051 писал(а):
Давно уже читал, что некоторые программы могут выдавать настоящие случайные числа.
Не программы, а устройства.
(А если всё-таки программы, то числа не настоящие.)

 
 
 
 Re: Коррелятор для псевдо случайных чисел
Сообщение04.07.2012, 17:08 
Аватара пользователя
Уточняю: железо стандартное.
Во всяком случае, автор той статьи писал так.

 
 
 
 Re: Коррелятор для псевдо случайных чисел
Сообщение04.07.2012, 17:09 
Цитата:
Какую обоснованную корреляционную проверку для такого генератора можно сделать?

У Кнута во 2 томе "Искусство программирования" описано более десятка (по-моему 11 или 12) эмпирических критериев, применяемых для проверки "случайности".

-- Ср июл 04, 2012 18:15:27 --

Имейте только в виду - успешное прохождение одного или двух тестов не является гарантией, что генератор хорош. Для надежности - чем большим количеством тестов проверите - тем лучше.

 
 
 
 Re: Коррелятор для псевдо случайных чисел
Сообщение04.07.2012, 19:43 
Cash в сообщении #592085 писал(а):
Цитата:
Какую обоснованную корреляционную проверку для такого генератора можно сделать?

У Кнута во 2 томе "Искусство программирования" описано более десятка (по-моему 11 или 12) эмпирических критериев, применяемых для проверки "случайности".

-- Ср июл 04, 2012 18:15:27 --
.


Спасибо, большое!!!)))

 
 
 
 Re: Коррелятор для псевдо случайных чисел
Сообщение04.07.2012, 21:25 
Новые процессоры от Intel на архитектуре IvyBridge имеют встроенный аппаратный датчик случайных чисел (не псевдослучайных) на основе теплового шума. Впрочем, подозреваю, его можно скомпрометировать, введя в электропитание хитрые гармоники.

 
 
 
 Re: Коррелятор для псевдо случайных чисел
Сообщение04.07.2012, 22:16 
Аватара пользователя
post243884.html#p243884

 
 
 
 Re: Коррелятор для псевдо случайных чисел
Сообщение05.07.2012, 14:55 
Собираюсь использовать в программе критерий сериальной корреляции, который описан в книге Кнута Искусство программирования том.2.
Не понятна одна вещь, в книге написано, что дисперсия для сериальной корреляции при равномерном распределении ($U_j$ - последовательностей псведослучайных чисел) равна $\frac{24}{5}n^{-2}+O(n^{-7/3}log(n))$
На сколько я понимаю дисперсия должна быть порядка ~ $\frac{1}{n}$

 
 
 [ Сообщений: 11 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group