Случайная последовательность по Кнуту

[Lesobrod]

В главе 3.5 "ИП" Кнут рассматривает понятие "случайной последовательности"
и приводит эффективные критерии случайности ($\infty$-распределённая, с учетом подпоследовательностей
и т.д.) Но все рассмотрение проводится в предположении равномерного распределения. А если заранее ясно, что случайная величина распределена неравномерно (напр., по Гауссу)? Возможно ли как-то
модифицировать написанное у Кнута для оценки случайности неравноспределённых последовательностей?

[worm2]

Если заранее известно само проверяемое распределение — то можно (алгоритм будет зависеть от этого распределения).

А если нет... знаете, при желании можно ведь и детерминированную величину считать случайной. С функцией Хевисайда в качестве функции распределения.
Или скажем, я могу задумать такое распределение: случайная величина принимает значение 0 с вероятностью $1-10^{-100}$ и 1 с вероятностью $10^{-100}$. Как Вы будете (не зная, что за распределение я задумал) проверять, что это действительно случайная величина?

Лень сейчас тянуться за Кнутом, но я подозреваю, что он проверяет не только случайность, но и независимость, так что приходится идти на упрощения и рассматривать только случай равномерного распределения.

[Lesobrod]

Ну конечно, подбор и проверка гипотез - это тема слишком обширная.
Пусть речь идет о равномерном или Гауссе.
Согласно Кнуту, необходимым условием случайности является 1-, 2-,...,
$\infty$-распределенность, т.е равные вероятности появления
всех возможных исходов, всех попарных сочетаний, троек и т.д.
Я довольно много возился с равнораспределёнными величинами типа
двоичных последовательностей и т.п. и проводил опыты "на людях" .
Интересно, что человек в состоянии имитировать 1-распределённость,
но в сочетаниях пар явно преобладают "10" и "01", т.е. уже нет 2-распределённости.
Если величина гауссова, то она даже не будет 1-распределённой.
Но при этом она может быть случайной или получена искусственным подбором.
Если не секрет, какие алгоритмы возможны для проверки этого?
У меня интерес не коммерческий )))

[worm2]

(Оффтоп)

Всё-таки Вы меня довели до ручки, и ручка потянулась за Кнутом

$\infty$-распределённость можно определить лишь сугубо теоретически, для бесконечных последовательностей (бесконечных двоичных) дробей. Если перейти к неравномерным распределениям, то связь между $k$-распределённостью для таких дробей и $k$-распределённостью для конечных двоичных последовательностей теряется, поэтому наглядно представить себе как будут там вести себя нули и единички, уже невозможно.
Однако исходное определение Кнута (которое не привязано к двоичному способу записи) легко обобщить на случай любой функции распределения $F$:

Цитата:

Говорят, что последовательность (1) будет k-распределённой по отношению к функции распределения $F$, если

$$\mathrm{Pr}(u_1\leq U_n<v_1,\,\dots,\,u_k\leq U_{n+k-1}<v_k)=(F(v_1)-F(u_1))\dots(F(v_k)-F(u_k)),$$

далее по тексту.

-- Сб май 14, 2011 21:21:20 --

Да, упустил одну деталь: равномерное распределение живёт на конечном промежутке (у Кнута $[0, 1)$), а Гауссово — на всей прямой, надо будет тоже этот факт как-то осмыслить и скорректировать определение. Надеюсь, Вы справитесь

[Lesobrod]

Спасибо, определение вполне конструктивное.
Если у Вас еще ру(ч)ки не опустились ,
или кто еще сюда зайдет - как насчет подпоследовательностей?
Вот примитивная гипотеза -
если бесконечная случайная последовательность имеет определённое
распределение ("хорошее" - Гаусс, треугольное, равномерное,..),
то её <????> подпоследовательности будут иметь такое же распределение.
Существуют ли теоремы теорвера для уточнения <????> ?
Похоже, что "каждый четный/третий/... член" подходят

[worm2]

<????> = "заранее заданные". В смысле, заранее, до того, как последовательность известна, номера её членов заданы каким-то детерминированным (или даже случайным, но с заранее известным распределением) алгоритмом .
Да, это верная гипотеза.

[Евгений Машеров]

Если известен закон распределения F(x) величины Х, то величина u=F(X) распределена равномерно.

[Lesobrod]

worm2 в сообщении #446330 писал(а):

Да, это верная гипотеза.

(Оффтоп)

Здорово, а жена говорит - все мозги пропил;
видимо, перешел на костный.

Да, увлекся я этой темой...
Существует много критериев случайности/хаотичности ,
конструктивных и не очень )) Вот что у меня получилось на данный момент:
(для простоты вернёмся к равномерному распределению):
1. Выполнение закона больших чисел, $\chi^2$-критерия и т.п.
2. Случайность по Кнуту.
3. Равномерность спектра мощности ( в среднем).
4. Быстрое, без осцилляций, спадание автокорреляционной функции.
5. Максимум энтропии (среди последовательностей данной длины из того же алфавита).
6. Что-то по поводу размерности (информационной или Реньи).
(Насчет размерности фракталов и аттракторов тему понял, а вот для чисто стохастических множеств как-то не очень)

Вот любопытно, как связаны эти критерии? У меня такое ощущение, что из Кнута можно все остальное
вывести.

-- Вт май 17, 2011 20:06:31 --

Евгений Машеров в сообщении #446825 писал(а):

Если известен закон распределения F(x) величины Х, то величина u=F(X) распределена равномерно.

Что-то я туплю Если $x$ - цифры $0..9$, а $F(x)$- Гаусс, то что распределено равномерно?

[worm2]

Цитата:

любопытно, как связаны эти критерии? У меня такое ощущение, что из Кнута можно все остальное вывести.

Думаю, что это так, хотя не со всеми критериями даже знаком

Цитата:

Что-то я туплю Если $x$ - цифры $0..9$, а $F(x)$- Гаусс, то что распределено равномерно?

Если $F(x)$ — Гаусс, то $x$ — принимает область значений Гауссовского распределения, т.е. всё $\mathbb{R}$. Это обыкновенный, стандартный тервер.

Утверждение следует понимать так: если Вам нужно проверить, имеет ли случайная величина $X$ (заранее известное) распределение $F(x)$, то достаточно проверить, что случайная величина $F(X)$ имеет равномерное распределение (а это Вы уже типа умеете). Да, я такое простое рассуждение как-то упустил из виду, а из него, в частности, мгновенно следует формула, которую я выше написал.

[Евгений Машеров]

Тут есть ещё тонкость. Если у нас известно теоретическое распределение - то всё работает. Однако на практике чаще проверяем принадлежность к распределению, параметры которого проверяются по той же выборке. И если мы, скажем, приводя к стандартному нормальному, вычтем их наблюдений среднее и разделим на стандартное отклонение, полученные величины не будут нормальны (и даже независимы не будут - у них будет небольшая отрицательная корреляция; а если параметры оцениваются по выборке, но другой, то независимость сохранится, но распределение всё равно уже не будет нормальным). Поэтому для приведения придётся использовать вместо обычной стандартизации хитрые приёмы типа критерия Саркади.

[Lesobrod]

Насчет $F(X)$ все понял, спасибо!
Вычитание среднего и нормировка это, действительно,
тонкий вопрос.
А что, Вы, Евгений, посоветуете относительно простых чисел?
Ведь в их распределении есть явный тренд - известная зависимость $n / ln(n)$.
и в то же время случайные колебания. Согласно гипотезе Римана,
вопрос сводится к распределению нулей дзета-функции; но и там та же
картина - в их распределении есть явная закономерность (увеличение расстояний
между последовательными нулями и т.д.) и элемент стохастичности
(как мне кажется). Как хотя бы попытаться разделить случайное и
закономерное в такой "простой" (^___^) последовательности, как простые числа? Подчеркну, что не хотелось бы привлекать аналитический аппарат,
а взглянуть на простые числа как на "данные эксперимента".