Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2005.06.14;
Скачать: CL | DM;

Вниз

Критерий интервалов - кто знает?   Найти похожие ветки 

 
Vasya.ru ©   (2005-05-24 11:23) [0]

Сижу и пытаюсь осознать критерий интервалов для проверки случайных последовательностей по книге Кнута. Безуспешно. Если кто знает - напишите по человечески - что и как там надо искать?


 
TUser ©   (2005-05-24 11:36) [1]

Есть псевдослучайная последовательность R[0]..R[n-1]. Есть участок [0,1]. Равномерно ли распределены числа на этом участке? Если да, то интервалы будут встречаться с некоторой вероятностью. Возьмем два числа - alpha и beta. Интервал - это последовательность последовательно идущих числе, которые лежат внутри (alpha,beta). Такой интервал имеет длину, причем выбирается он так, чтобы длина была максимальной. Например, для последоватлеьность
2351 1728 2846 6974 7673 7849 6282 8818 2173 7438 1175
и границ (6000,8000) есть интервал длины 4 (6974-6282) и интервал длины 1 (7438).
Т.о. каждая псевдослучайная последовательность и два числа дают некоторое распределение длинн интервалов C[1..max], которые реально встретились. Там вроде бы есть формулы, как вычислить такое распределение для абсолютно случайной величины, если нет, то нетрудно вывести. А имея два распределеение (вычяисленное и измеренное) - их надо сравнить хи-квадратом. Число ст. свободы - на единицу меньше длины самого длинного из найденных интервалов.


 
TUser ©   (2005-05-24 11:48) [2]

Я посмотрел в Кнуте - вроде понятно все изложено. Какие конкретно вопросы были?


 
Vasya.ru ©   (2005-05-24 12:33) [3]

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


 
TUser ©   (2005-05-24 12:40) [4]

Я имел в виду, что в приведенном примере выбирается интервал длины 4, а не его подпоследовательность длины, скажем, 2. Ну это и так понятно.

Мне кажется проблема у тебя с осмыслением термина интервал. Я не зря его курсивом выделили везде - интервал, это не область числового ряда, на которой псевдосл. числа генерятся, а последовательно идущие друг за друга числа из этой последоватлеьонсти, таки, что они лежат целиком внутри отрезка (alpha,beta).



Страницы: 1 вся ветка

Текущий архив: 2005.06.14;
Скачать: CL | DM;

Наверх




Память: 0.48 MB
Время: 0.029 c
14-1116827183
Kerk
2005-05-23 09:46
2005.06.14
С днем рожденья! 23 мая


4-1114528271
Виталик
2005-04-26 19:11
2005.06.14
Проблема с запуском программы от лица другого пользователя


1-1117108540
Артём К.
2005-05-26 15:55
2005.06.14
Выделение и перетаскивание мышью нескольких компонент?


14-1117114879
lookin
2005-05-26 17:41
2005.06.14
Оформление сайта


1-1117283847
illuha
2005-05-28 16:37
2005.06.14
Память