2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5 ... 7  След.
 
 
Сообщение12.04.2006, 22:40 
Заслуженный участник
Аватара пользователя


07/03/06
1898
Москва
А я наконец-то добрался до источника, из которого выше пытался что-то такое вспомнить. Это оказалась книжка В.И. Арнольда «Жесткие и мягкие математические модели» Вот цитата.
Цитата:
Первая цифра числа 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 шагами, несоизмеримыми с ее длиной, то доля времени, проводимого прыгающей точкой в каждой дуге, пропорциональна длине дуги (и не зависит от расположения дуги на окружности).

 Профиль  
                  
 
 
Сообщение13.04.2006, 00:02 


06/03/06
150
shwedka писал(а):
Цитата:
Не все же самому думать.

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


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

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

 Профиль  
                  
 
 
Сообщение13.04.2006, 00:27 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение13.04.2006, 00:37 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
shwedka писал(а):
Можно ли специально, детерминированно, сочинить последовательность, которую все тесты примут за случайную???

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

 Профиль  
                  
 
 
Сообщение13.04.2006, 00:39 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение13.04.2006, 00:49 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение13.04.2006, 01:11 


06/03/06
150
незванный гость писал(а):
:evil:
shwedka писал(а):
Можно ли специально, детерминированно, сочинить последовательность, которую все тесты примут за случайную???

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


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

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

 Профиль  
                  
 
 
Сообщение13.04.2006, 01:35 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
er писал(а):
Конечные детерминированные системы вещь хорошая, но сочинить детерминированную не периодическую последовательность - без проблем. Те же цифры в десятичном разложении числа $\pi$. :D

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

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

 Профиль  
                  
 
 
Сообщение13.04.2006, 01:43 
Заслуженный участник
Аватара пользователя


11/12/05
3542
Швеция
Меня чуть по-другому интересовало
может ли умный математик обмануть критерии случайности??

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

 Профиль  
                  
 
 
Сообщение13.04.2006, 01:50 
Заслуженный участник


31/12/05
1412
shwedka писал(а):
Можно ли специально, детерминированно, сочинить последовательность, которую все тесты примут за случайную???

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

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

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

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

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

 Профиль  
                  
 
 
Сообщение13.04.2006, 01:59 
Заслуженный участник
Аватара пользователя


11/12/05
3542
Швеция
Таки что называть случайной последовательностью??
Объясните.

 Профиль  
                  
 
 
Сообщение13.04.2006, 06:44 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение13.04.2006, 09:43 


06/03/06
150
shwedka писал(а):
Таки что называть случайной последовательностью??
Объясните.


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

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

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

 Профиль  
                  
 
 
Сообщение13.04.2006, 09:54 


06/03/06
150
tolstopuz писал(а):
shwedka писал(а):
Можно ли специально, детерминированно, сочинить последовательность, которую все тесты примут за случайную???

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

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

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


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

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

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

 Профиль  
                  
 
 
Сообщение13.04.2006, 10:43 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 99 ]  На страницу Пред.  1, 2, 3, 4, 5 ... 7  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group