2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7  След.
 
 
Сообщение13.04.2006, 11:55 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
shwedka писал(а):
Таки что называть случайной последовательностью??
Объясните.


Ну есть еще понятие сложности по Колмогорову. Берем достаточно длинную последовательность и рассматриваем все программы в некотором универсальном языке, которые эту последовательность порождают. Среди них берем самую короткую. Ее длина и характеризует сложность последовательности. Самые сложные - такие, что для их воспроизведения нет ничего лучше, чем честно всю последовательность запомнить. Т.е. никаких закономерностей, за счет которых последовательность можно было бы принципиально сжать, нет. Вот эти последовательности и есть "честные" случайные.

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


11/12/05
3542
Швеция
Внушаеть!!
Но это абсолютно непроверяемое определение, да еще от языка зависящее.

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

 Профиль  
                  
 
 
Сообщение13.04.2006, 12:39 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Как уже было сказано, понятие случайности сложное и похоже более философское, чем строго математическое.

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

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


31/12/05
1406
er писал(а):
tolstopuz писал(а):
Тестом он называет алгоритм, выбирающий подпоследовательность данной последовательности, где каждый следующий индекс определяется анализом всей предыдущей последовательности, без заглядывания вперед. Например, "выбирать только те результаты бросаний монеты, которые случились после пяти решек подряд".

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

А про это у него еще целый абзац :)

Тест на равномерное распределение пар выражается через такие "подпоследовательностные" тесты: достаточно проверить равномерную распределенность всей последовательности, подпоследовательности элементов, идущих после нуля, и подпоследовательности элементов, идущих после единицы. Далее, добавляя к тестсьюиту тесты равномерного распределения x в кусках 00x, 01x, 10x и 11x, мы получаем тест на равномерное распределение троек. И так далее.

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

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


11/12/05
3542
Швеция
PAV писал(а):
Как уже было сказано, понятие случайности сложное и похоже более философское, чем строго математическое.

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

Вот я про то и говорю, в отношении к исходному вопросу темы. Поскольку понятие случайности
для одной конкретной последовательнодсти не задать, то всякие вопросы о применении тестов случайности и связанных с нею понятий к ее конечным участкам это не слишком содержательное упражнение по программированию. Скажу строже, вопрос о равномерности распределения цифр в мировых копнстантах не имеет никакого отношения к свойствам этих констант или последовательностей цифр. Разговоры о том, что взяли МНОГО, 15 лимонов цифр и что-то посчитали - несерьезны. В математике, в отличие, скажем, от физики, много или мало не бывает. Разумно говорить о пределах, асимптотике.

 Профиль  
                  
 
 
Сообщение13.04.2006, 13:45 


12/04/06
4
Но е мы же здесь имеем не последовательность случайных величин, а всего одну величину, которая может принимать одно из 10 значений. Как ни будь из того, что случайная величина это измеримая функция, нельзя ли доказать случайность цифр в иррациональном числе?

 Профиль  
                  
 
 
Сообщение13.04.2006, 13:46 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Ну, вопросы о том, что разумно или не разумно изучать в математике - дискуссионные. Я не совсем согласен с тем, что эти вопросы не очень содержательные, равно как и с тем, что это ничего не говорит о свойствах констант или последовательностей. Но это только мое личное мнение.

 Профиль  
                  
 
 
Сообщение13.04.2006, 13:48 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
БесПартийный писал(а):
Но е мы же здесь имеем не последовательность случайных величин, а всего одну величину, которая может принимать одно из 10 значений. Как ни будь из того, что случайная величина это измеримая функция, нельзя ли доказать случайность цифр в иррациональном числе?


Строго говоря, случайности тут таки-нет.

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


11/12/05
3542
Швеция
PAV писал(а):
Ну, вопросы о том, что разумно или не разумно изучать в математике - дискуссионные. Я не совсем согласен с тем, что эти вопросы не очень содержательные, равно как и с тем, что это ничего не говорит о свойствах констант или последовательностей. Но это только мое личное мнение.

Здесь, конечно, у меня подход классовый. У нас департамент математики общий со статистикой, как часто на западе бывает, но кошельки раздельные, так этим статистикам всегда финансирование лучше.
А за что!!!!!

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


09/02/06
4382
Москва
У любого конструктивного числа (куда относятся фактический все употребляемые числа, несмотря на то, что их количество всего счётно) цифры не случайны и находятся по конкретному алгоритму. Поэтому, можно говорить только о прохождении каких то тестов на случайность.

 Профиль  
                  
 
 
Сообщение13.04.2006, 14:32 
Супермодератор
Аватара пользователя


29/07/05
8248
Москва
Руст писал(а):
У любого конструктивного числа (куда относятся фактический все употребляемые числа, несмотря на то, что их количество всего счётно) цифры не случайны и находятся по конкретному алгоритму. Поэтому, можно говорить только о прохождении каких то тестов на случайность.


Да, конечно, в приложении к данной обсуждаемой задаче это так. И Колмогоровская сложность таких последовательностей фактически равна нулю, так как алгоритм фиксирован и не зависит от длины требуемой последовательности. Остаются только тесты.

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


07/03/06
1898
Москва
Решил тоже беллетристикой позаниматься…
Каковы критерии того, что бесконечная последовательность цифр может считаться случайной?
Рассмотрим честную игру СпортЛото, интуиция подсказывает, что распределение равномерно. Я буду играть каждый месяц и ставить на одну и туже последовательность чисел – попадаем под условия повторения эксперимента и вероятность выигрыша растет. После скольких то раз она мало будет отличаться от единицы, т.е. через 60-80 лет я с вероятностью 99% выиграю. Таким образом, исходную последовательность можно считать случайной с заданным законом распределения, если для любой наперед выбранной конечной последовательности через расчетное число раз (исходя из предполагаемого закона распределения) эта конечная последовательность встретится в исходной.

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


31/12/05
1406
Артамонов Ю.Н. писал(а):
Таким образом, исходную последовательность можно считать случайной с заданным законом распределения, если для любой наперед выбранной конечной последовательности через расчетное число раз (исходя из предполагаемого закона распределения) эта конечная последовательность встретится в исходной.

Кнут называет это свойство (для равномерного закона) $\infty$-распределенностью. Но этого недостаточно для случайности - если мы, например, обнулим в $\infty$-распределенной последовательности все члены с индексами - полными квадратами, то последовательность останется $\infty$-распределенной, хотя ее вряд ли можно назвать случайной.

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


31/12/05
1406
А, я понял, как переводится на человеческий язык определение случайности по Кнуту. Рулетка (честная, без зеро) называется случайной, если невозможна система, дающая ненулевое матожидание выигрыша :)

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


07/03/06
1898
Москва
Любая случайность – это сложная закономерность. Если Вы примешиваете в нашу случайную последовательность какую-либо простую закономерность, то лишь искажаете закон распределения – Вы не встретите в исходной последовательности за расчетное число раз (исходя из принятого ранее закона распределения) заданную конечную последовательность.
Вообще, если далее философствовать – то в природе есть случайность лишь от сущности, т.е. того, что внутренне свободно от того, где находится, например, человек – внутренне свободен от внешнего мира и поэтому может диктовать ему свою волю, которая кажется непрогнозируемой закономерностью, т.е. случайностью.

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

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



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

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


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

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