Отчёт: Эмпирические критерии проверки случайных последовательностей
СОДЕРЖАНИЕ
ЭМПИРИЧЕСКИЕ КРИТЕРИИ ПРОВЕРКИ СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ. КРИТЕРИЙ ЧАСТОТ, СЕРИЙ, ИНТЕРВАЛОВ, РАЗБИЕНИЙ, ПЕРЕСТАНОВОК, МОНОТОННОСТИ, КОНФЛИКТОВ
ЛИНЕЙНЫЙ КОНГРУЭНТНЫЙ МЕТОД
ОСНОВНЫЕ КРИТЕРИИ ПРОВЕРКИ СЛУЧАЙНЫХ НАБЛЮДЕНИЙ
ЭМПИРИЧЕСКИЕ КРИТЕРИИ
КРИТЕРИЙ СЕРИЙ
ПОКЕР-КРИТЕРИЙ (КРИТЕРИЙ РАЗБИЕНИЙ)
КРИТЕРИЙ ПЕРЕСТАНОВОК
КРИТЕРИЙ МОНОТОННОСТИ
КРИТЕРИЙ КОНФЛИКТОВ
Дата добавления на сайт: 02 марта 2025
Федеральное государственное бюджетное образовательное учреждение
Высшего профессионального образования
\"Тольяттинский государственный университет\"
Институт математики, физики и информационных технологий
Кафедра Прикладной математики и информатики
Профиль Математическое моделирование
Отчет по самостоятельной работе
по дисциплине \"Получисленные алгоритмы\"
на тему: Эмпирические критерии проверки случайных последовательностей
Выполнила: Парамонова К.С.
группа ПМИм-1301
Принял: Мельников Б.Ф.
Тольятти 2014 г.
Содержание
Эмпирические критерии проверки случайных последовательностей. Критерий частот, серий, интервалов, разбиений, перестановок, монотонности, конфликтов
Линейный конгруэнтный метод
Основные критерии проверки случайных наблюдений
Эмпирические критерии
Критерий серий
Покер-критерий (критерий разбиений)
Критерий перестановок
Критерий монотонности
Критерий конфликтов
Эмпирические критерии проверки случайных последовательностей. Критерий частот, серий, интервалов, разбиений, перестановок, монотонности, конфликтов
Числа, которые выбираются случайным образом, находят множество полезных применений: моделирование.
Это позволяет сделать модели похожими на реальные явления; выборочный метод. Часто невозможно исследовать все варианты, но случайная выборка обеспечивает понимание того, что можно назвать \"типичным поведением\"; численный анализ.
Для решения сложных задач численного анализа была разработана техника, использующая случайные числа; компьютерное программирование. Случайные числа являются хорошим источником данных для тестирования эффективности компьютерных алгоритмов; принятие решений; эстетика; развлечения.
Равномерным распределением на конечном множестве чисел называется такое распределение, при котором любое из возможных чисел имеет одинаковую вероятность появления. Если не задано определенное распределение на конечном множестве чисел, то принято считать его равномерным [3]. Джон фон Нейман первым предложил в 1946 г. идею возвести в квадрат случайное число и выделить из него средние цифры. Например, необходимо получить новое десятизначное число по числу 5772156649. Возводим имеющееся число в квадрат и выделяем средние 10 цифр:
.
Новым сгенерированным числом будет число 7923805949. Эта последовательность не случайна, она кажется такой. Последовательности, генерируемые детерминистическим путем, таким как этот, называются псевдослучайными или квазислучайными.
Метод середины квадратов фактически является сравнительно бедным источником случайных чисел. Опасность состоит в коротком цикле (периоде) повторяющихся элементов. Рассмотрим методы генерирования последовательности случайных дробей [3], т.е. случайных действительных чисел Un, равномерно распределенных между нулем и единицей. Будем генерировать целое число Хn между нулем и некоторым числом U, тогда дробь при m >= U
Un = Хn / m
будет принадлежать [0,1]. Обычно m выбирают равным размеру компьютерного слова. Обозначим m = be, где b - основание системы счисления, используемой ЭВМ, а e - число разрядов машины. Поэтому Хn можно по традиции рассматривать как целое число, занимающее все компьютерное слово с точкой в правом конце слова, а Un - как содержимое того же слова с точкой в левом конце слова.
Линейный конгруэнтный метод
Выберем четыре числа [3]:
m - модуль, m > 0;
a - множитель, 0 Ј a >k, например n і 5d2.
Покер-критерий (критерий разбиений)
\"Классический\" покер-критерий рассматривает n групп по пять последовательных целых чисел
{Y5j, Y5j+1, Y5j+2, Y5j+3, Y5j+4} для 0 Ј j Xj+i, получим
|12 9 | 8 | 5 | 3 6 7 | 0 4 |. (9)
Таким образом выделяются восходящие серии: сначала - серия длиной 3, затем - две серии длиной 1, затем - снова серия длиной 3 и, наконец, серия длиной 2.
Критерий конфликтов
c2 - критерий можно применять только тогда, когда ненулевое число элементов ожидается в каждой категории. Но существует критерий другого вида, который можно использовать, когда число категорий намного больше числа наблюдений. Этот критерий имеет отношение к рандомизации - важному методу информационного поиска.
Предположим, что имеется т урн, и поместим в них наудачу п шаров, причем т намного больше n. Большинство шаров попадет в пустые урны, но если шар попадет в урну, в которой уже содержится хотя бы один шар, то будем говорить, что произошел \"конфликт”. Критерий конфликтов подсчитывает число конфликтов, и генератор удовлетворяет этому критерию, если не возникает слишком много или слишком мало конфликтов.
Для определенности предположим, что т = 220 и п = 214. Тогда в среднем на 64 урны приходится только один шар. Вероятность того, что в конкретную урну попадет ровно к шаров, равна pk - т~1) п~к, поэтому среднее число конфликтов в урне равно.