AOP_Tom2 (1021737), страница 46
Текст из файла (страница 46)
(МЯй) (Р. В. Флойд (Н, '77'. Р!оу4().) Докажите, что следующий алгоритм генерирует случайпую выборку 5 из и целых чисел из (1,...,177). Присвойте сначала о 4- й, а затем для 1 4-1эг — п + 1, ж — и+ 2, ..., 137 (в таком порялке) присвойте й 4 — (3Ц + 1 и )'501)7), если )с Ф Я; ~) Я О(1"), если 8 ч Я. «3.5. ЧТО ТАКОЕ СЛУЧАЙНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ А.
Вводные замечания. Выше в данной главе рассказывалось, как генерировать последовательности (Ъв) — Нш ам а2, (1) действительных чисел в области 0 < сг„< 1. Эти последовательности назывались случайными, даже несмотря на то, что они совершенно детерминированные па характеру. Чтобы оправдать использонание этой терминологии, мы утверждали, что числа "ведут себя так, как будто ани действительно случайны". Такое утверждение может быть удовлетворительным для практических целей (в настоящее время), но эта шаг в сторону очень важного методического и теоретического вопроса "Что именно пад!эазумевается под случайным поведением?".
Необходима количественное определение. Нежелательно говорить о понятиях, которых мы на самом деле не понимаем, главным образом потому, чта, по-видимому, можно сделать много парадоксальных утверждений, касающихся случайных чисел. Теория вероятностей и математическая статистика тщательно избегают обсуждения спорных вопросов. Они воздерживаются от безусловных утверждений и вместо этого выражают все в терминах вероятностей, связанных с последователыюстью случайных событий. Аксиомы теории вероятностей установлены так, что теоретические вероятности можно легко вычислит«в но о там, что на самом деле означает "вероятность" или как это понятие можно разумно применить к действительности, ничего не говорится.
В книге РгоЬаЪ!!!гу, Ясаг!вбсв, аль Тгнгй (!лезг Уогйк Маспп!!ап, 1957), Р. фон Мизес (Н, гоп МЬев) подробно обсуждает зту ситуацию и предлагает следующую точку. зрения; определение вероятностей зависит от того, какое используется определение случайных последовательностей. Процитируем здесь несколько утверждений двух авторов, комментировавших эту тему.
Д. Г. Дехмер (П. Н. Еебшег) (1951): "Случайная последовательность является смутным понятием, олицетворяющим идею последовательности, в которой каждый член является непредсказуемым для непосвященных и значения которой проходят определенное количество проверок, традиционных у статистиков и отчасти зависящих от пользователей, которым предложена последовательность". Д. Н. Франклин (Х Х.
г)атй!!и) (1962): "Последовательность (1) случайна, если она обладает любыми свойствами, присущими всем бесчисленным последовательностям независимых выборок случайных равномерно распределенных величин". Утверждение Франклина, по существу, обобщает высказывание Лехмера о том, что последовательность должна удовлетворять всем статистическим критериям. Его определение не вполне точное, и позже мы убедимся, что разумное обьяснение его утверждения приводит к заключению о том, что не существует такого объекта, как случайная последовательность! Так давайте начнем с менее ограничительного утверждения уйехмера и попытаемся сделать вго точным. Что нам действительно необходимо — так это сравнительно короткий перечень математических свойств, каждое из которых удовлетворяет нашим интуитивным представлениям о случайной последовательности.
К тому же этого перечня будет вполне достаточно, чтобы согласиться с тем, что любая последовательность, удовлетворяющая этим свойствам, является "случайной". В данном разделе рассматривается то, что кажется адекватным точному определению случайности согласно этим критериям, хотя много интересных вопросов остается без ответов, Пусть и и и — действительные числа, О < и < и < 1.
Если à — шгучайная величина,, равномерно распределенная между О и 1, вероятность того, что и < У < и, равна о — и. Например, вероятность, что = < П < —, равна —,. Как можно выразить з г зто свойство единственного числа У свойством бесконечной последовательности По, См с'т, ...? Очевидный ответ — подсчитать, сколько раз П„находится между и и о, и сказать, что среднее число попаданий в этот интервал равно и — и. Наше интуитивное понятие вероятности основано, таким образом, на частоте появления события.
Точнее, пусть и(п) — число значений у, О < у < п, таких, что и < 6' < и, и отношением и(п)/и необходимо приблизить значение и — и, когда и стремится к бесконечности: и(п) 1пп — = е — и. (2) о-~со и Если зто условие выполняется для всех вариантов и и и, говорит, что последователыгость раонараспределена. Пусть утверждение Я(п) относится и к целому числу и, и к последовательности По, Г~, ..., например 5(и) может быть приведенным выше утверждением "и < Ва < о".
Можно обобщить понятие, используемое в предыдущем разделе, чтобы определить вероятность того, что 5(п) справедливо по отношению к некоторой бесконечной последовательности. Определение А. Пусть и(п) — число значений /б О < у < п, таких, что Я0) верно. Мы говорим, что Б(п) выполняется с вероятностью Л, если предел и(п)/п, когда т1 стрелагтся к бесконегностп, равен Л.
А именно: Рг(5(п)) = Л, если 1пп„„и(п)/и = Л. В терминах этой записи последовательность По, У,,... равнораспределена тогда, и только тогда, когда Рг(и < Ь'„< о) = и — и для всех действительных чисел и, и приО<и<и<1. Последовательность может быть равнораспределена, даже если она не случайна. Например, если Уо, Ум .,.
и 1ш 'гм... — равнораспределенные последовательности, то нетрудно показать, что последовательность Ио,ИмИ'т,И'з, = -'По, —,+~~1о, —,Пм 1+-,'1м г (3) также равнораспределена,, поскольку подпоследовательность -По, -б'м ... равно- 1 ° 1 распределена между О и -", в то время как промежуточные члены —, + —,1о, —, + э Ъм равнораспределены между -' и 1. Но в последовательности И'„, у = 0,1,2,..., значения, моньшие —, всегда следуют за значениями, ббльшими нли равными — со- 1 1 г ответственно.
Значит, последовательность не случанна согласно любому разумному определению. Необходимы свойства, которые сильнее равнораспределенности. Естественная возможность обобщить свойство равнораспределенности, которое позволяет развеять сомнения предыдущего раздела, -- рассмотреть смежные пары членов нашей последовательности. Можно потребовать, чтобы последовательность удовлетворяла условиям (4) Рг(иг < Сп < иг и из < Ь вас < 1)2) = (01 — иг)(оз — их) для любых членов иы оы игм оз при О < иг < ег < 1, О < и < но < 1. И вообще, для любого положительного целого Ь можно потребовать, чтобы наша последовательность была Ь-распределесснай в смысле определения В.
Определение В. Говорят, что последовательность (1) будет 1с-распределеггног1, если Рг(иг < (/„< оы ..., иь < Ь в+о с < иь) = (ог — иг)... (иь — иь) (5) для всех варпантои действительных чпгел и:, о прн О < и < о < 1 для 1 < / < Ь. Равнораспределенная последовательность является 1-распределенной. Заметим, что, если /с > 1, Ь-распределенная последовательность всегда ягзляется (Й вЂ” 1)- распределенной, так как в (5) можно положить иь = О и еь = 1.
Таким образом, в частности, любая последовательность, о которой известно. что она 4-распределена, должна быть также 3- и 2-распределенной. Можно определить наибольшее Ь, для которого данная последовательность является Й-расгсределенной, что приведет нас к формулировке более сильного свойства.
Определение С. Говорят, что тсгледовательность ос-распределена, если оиа Ь-распределена для всех положительных целых Й, До сих пор мы рассматривали [О .. 1)-последовательности, т, е, последовательности действительных чисел, ленсапсих между О и 1. Такие же понятия применяются к целочисленным последовательностям. Говорят, что последовательность (Х„) = Хо, Хы Ла, ... является Ь-изной паследовательносгпью. если каждый член последовательности Л„является одним из целых чисел О, 1, ..., Ь вЂ” 1. Таким образом, 2-ичная (бинариая) последовательность .
— это последовательность нулей и единиц. Определим также Ь-ичное число, состоищее из Ь цифр, как строку Ь целых чисел хгхо... хь, где О < х < Ь для 1 < / < Ь. Определение В. Говорят, что Ь-пчная последовательность является к-распределенной, если Рг(Х„Х„эг... Х„+ь, = хгхо...
хс) = 1/Ь" (6) для всех Ь-попых чисел хгхт... хь. Из этого опРеделениЯ Ясно, что если (го, ьгы... Явлас тс и Ь-РаспРеделенной последовательностью (О .. 1), то последовательность [»Ь о) . ~,Ь»гг), ... является /ссраспределенной Ь-ичной последовательностью. (Есчн положить и = х /Ь, оу = (ху + 1)/Ь, Л„= [»1с;,), то равенство (5) превратится о равенство (6).) Более того, каждая гс-распределенная Ь-ичная последовательность является также (Ь вЂ” 1)-распределенной, если Ь > 1: мы складываем верояти я то лля Ь-ичных чисел хы хь-г О, хы ..
хы, 1, ..., хы,. хь с (Ь вЂ” 1), чтобы получись Рг(Хл ° Хьэ ь з х! ' ° ° хь — г ) 1/Ь ~Вероятности для несовместных событий вдлитивны: см. упр. 5.) Следовательно, естественно ввести понятие зс-распределенных 5-ичных последовательностей, как в определении С. Представление положительных действительных чисел в системе с основанием 5 можно рассматривать как Ь-ичную последовательность, например г соответствует 10-ичной последовательности 3, 1, 4, 1, 5., 9, 2, 6, 5, 3, 5, 6, 9, Предполагается, что зта последовательность оо-распределенная, но никто, однако, не в состоянии даже доказать, что она является точно 1-распределенной. Проанализируем это понятие более подробно для случая, когда х равно миллиону. Бинарная последовательность, являющаяся 1 000 000-распределенной, может содержать серию из миллиона нулей! Аналогично!0..1)-последовательность, являющаяся 1 000 000-распределенной, может содержать миллион последовательных значений, каждое из которых меньше —,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
