Критерий интервалов

← →
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]

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

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

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

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