Иррациональные числа и их свойства

[juna]

А я наконец-то добрался до источника, из которого выше пытался что-то такое вспомнить. Это оказалась книжка В.И. Арнольда «Жесткие и мягкие математические модели» Вот цитата.

Цитата:

Первая цифра числа 2^n бывает единицей примерно в 6 раз чаще, чем девяткой. Так же распределены первые цифры населения и площади стран мира.
Последовательность первых цифр первых чисел 2^n (n = 0,1,2,...):
1,2,4,8,1,3,6,1,2,5,1,...
содержит очень много единиц. Можно проверить, продолжив вычисление, что единицы составляют асимптотически около 30% членов этой последовательности. Этот результат следует из теоремы Г. Вейля (доказанной около ста лет назад), согласно которой последовательность дробных долей {nх} чисел nх, где х иррационально, равномерно распределена на отрезке от 0 до 1.
Теорема Вейля означает, что если точка прыгает по окружности длины 1 шагами, несоизмеримыми с ее длиной, то доля времени, проводимого прыгающей точкой в каждой дуге, пропорциональна длине дуги (и не зависит от расположения дуги на окружности).

[er]

shwedka писал(а):

Цитата:

Не все же самому думать.

Думать полезно. От этого становится умное лицо
(Акутагава Рюноске)

Во всем надо знать меру. Зачем слишком умное лицо? А численные эксперементы могут быть и интересны. Арнольд, вот придумал что..

Вообще то, кому что интересно, а это дело личное.

[shwedka]

Конечно, можно численно экспериментировать. Но при этом нужно все время помнить, что результаты экспериментов ничего не говорят о свойствах самого числа $\pi$
Вопрос (по части Котофеича ??)
Можно ли специально, детерминированно, сочинить последовательность, которую все тесты примут за случайную???

[незваный гость]

shwedka писал(а):

Можно ли специально, детерминированно, сочинить последовательность, которую все тесты примут за случайную???

Не думаю. Тут много деталей, но в целом идея примерно такая -- у конечной детерминированной системы конечное количество состояний, а значит, генерируемая ей последовательность будет необходимо переодической.

[shwedka]

Разумно, а если система бесконечная, с бесконечным числом состояний?
Но тут я немного тону, я больше про производные понимаю.

[незваный гость]

Мне кажется, тут наступают трудности с описанием бесконечной системы. Оно-то вынужденно конечное? Но я тоже не авторитет.

[er]

незванный гость писал(а):

:evil:

shwedka писал(а):

Можно ли специально, детерминированно, сочинить последовательность, которую все тесты примут за случайную???

Не думаю. Тут много деталей, но в целом идея примерно такая -- у конечной детерминированной системы конечное количество состояний, а значит, генерируемая ей последовательность будет необходимо переодической.

Конечные детерминированные системы вещь хорошая, но сочинить детерминированную не периодическую последовательность - без проблем. Те же цифры в десятичном разложении числа $\pi$.

2 shwedka. Построение хороших генераторов псевдосслучайных чисел - важная и давно разрабатываемая тема. Что то читал про это, но щас не помню подробностей. Где то здесь на форуме про Монте-Карло эта проблема упоминалась.

[незваный гость]

er писал(а):

Конечные детерминированные системы вещь хорошая, но сочинить детерминированную не периодическую последовательность - без проблем. Те же цифры в десятичном разложении числа $\pi$.

Осталось дело за малым -- за конечным представлением $\pi$. Вопрос, однако -- что такое конечная система.

Если же мы умеем представлять бесконечные числа -- нет проблем -- берем монетку, кидаем ее бесконечное число раз, и записываем ответ -- .010011101010.... Одно число, однако, разряды которого неотличимы, и не могут быть отличимы от случайной величины.

[shwedka]

Меня чуть по-другому интересовало
может ли умный математик обмануть критерии случайности??

Для этого, конечно, нужно договориться, какую последовательность случайной называть. Пусть даже цифр.
это, видимо, чуть больше, чем просто равномерное распределение. Может, что-то вроде стремления к нулю корреляции.
Кто в етом деле понимает,
может, подскажет??

[tolstopuz]

shwedka писал(а):

Можно ли специально, детерминированно, сочинить последовательность, которую все тесты примут за случайную???

Кнут в разделе 3.5 долго рассуждает об этом.

Тестом он называет алгоритм, выбирающий подпоследовательность данной последовательности, где каждый следующий индекс определяется анализом всей предыдущей последовательности, без заглядывания вперед. Например, "выбирать только те результаты бросаний монеты, которые случились после пяти решек подряд".

"Последовательность удовлетворяет тесту" означает, что выбранная в соответствии с тестом подпоследовательность равномерно распределена.

Далее Кнут приводит алгоритм W, выдающий последовательность, удовлетворяющую данному счетному семейству "тестов на случайность".

После этого остается только занумеровать все алгоритмы выбора подпоследовательностей (что, естественно, невозможно сделать конструктивно) и подать их на вход алгоритма W, и мы получаем последовательность, проходящую любой тест.

[shwedka]

Таки что называть случайной последовательностью??
Объясните.

[Руст]

Артамонову.
То, что рассматривал Арнольд распределение первых цифр, то они во первых не равномерно распределены. Причём распределение первой цифры k, пропорциональной $lg(\frac{k+1}{k})$ легко доказуема, в отличии от обсуждаемого случая.

[er]

shwedka писал(а):

Таки что называть случайной последовательностью??
Объясните.

Темный это вопрос, философских баталий не меньше чем в основаниях математики. Есть случайная величина, мы ее последовательно независимо начинаем испытывать и получаем случайную последовательность.

"Настоящию" случайную последовательность построить нельзя, это как бы по определению.

Псевдослучайная - удовлетворяющая каким то статистическим тестам.. Как в мат статистике. Доверительные интервалы и т.п.

[er]

tolstopuz писал(а):

shwedka писал(а):

Можно ли специально, детерминированно, сочинить последовательность, которую все тесты примут за случайную???

Кнут в разделе 3.5 долго рассуждает об этом.

Тестом он называет алгоритм, выбирающий подпоследовательность данной последовательности, где каждый следующий индекс определяется анализом всей предыдущей последовательности, без заглядывания вперед. Например, "выбирать только те результаты бросаний монеты, которые случились после пяти решек подряд".

"Последовательность удовлетворяет тесту" означает, что выбранная в соответствии с тестом подпоследовательность равномерно распределена.
...

Програмер Кнут, а не вероятностник. Сомневаюсь, что данные тесты удовлетворительны, с точки зрения статистики.

Например, если $(\xi_i$)$ случайная бинарная последовательность, то
$((\xi_i,\xi_{i+1},\xi_{i+2},\xi_{i+3},\cdots,\xi_{i+k}))$ тоже и равномерно должна быть распределена в
$\{0,1\}^k$

Псевдослучайные последовательности для чего то применяются, шифрования, Монте Карло и т.п. К ним есть какие то требования.

[Руст]

Лучшей "случайной" последовательностью является дробная часть {xn}, для некоторого иррационального х (желательно, чтобы неполные частные при разложении в непрерывную дробь не росли очень быстро), например х число в золотом сечении. Равномерность и разные бескорреляционности доказуемы.