2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3, 4, 5, 6, 7  След.
 
 
Сообщение13.04.2006, 11:55 
Аватара пользователя
shwedka писал(а):
Таки что называть случайной последовательностью??
Объясните.


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

 
 
 
 
Сообщение13.04.2006, 12:17 
Аватара пользователя
Внушаеть!!
Но это абсолютно непроверяемое определение, да еще от языка зависящее.

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

 
 
 
 
Сообщение13.04.2006, 12:39 
Аватара пользователя
Как уже было сказано, понятие случайности сложное и похоже более философское, чем строго математическое.

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

 
 
 
 
Сообщение13.04.2006, 12:55 
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 
Аватара пользователя
PAV писал(а):
Как уже было сказано, понятие случайности сложное и похоже более философское, чем строго математическое.

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

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

 
 
 
 
Сообщение13.04.2006, 13:45 
Но е мы же здесь имеем не последовательность случайных величин, а всего одну величину, которая может принимать одно из 10 значений. Как ни будь из того, что случайная величина это измеримая функция, нельзя ли доказать случайность цифр в иррациональном числе?

 
 
 
 
Сообщение13.04.2006, 13:46 
Аватара пользователя
Ну, вопросы о том, что разумно или не разумно изучать в математике - дискуссионные. Я не совсем согласен с тем, что эти вопросы не очень содержательные, равно как и с тем, что это ничего не говорит о свойствах констант или последовательностей. Но это только мое личное мнение.

 
 
 
 
Сообщение13.04.2006, 13:48 
Аватара пользователя
БесПартийный писал(а):
Но е мы же здесь имеем не последовательность случайных величин, а всего одну величину, которая может принимать одно из 10 значений. Как ни будь из того, что случайная величина это измеримая функция, нельзя ли доказать случайность цифр в иррациональном числе?


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

 
 
 
 
Сообщение13.04.2006, 13:57 
Аватара пользователя
PAV писал(а):
Ну, вопросы о том, что разумно или не разумно изучать в математике - дискуссионные. Я не совсем согласен с тем, что эти вопросы не очень содержательные, равно как и с тем, что это ничего не говорит о свойствах констант или последовательностей. Но это только мое личное мнение.

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

 
 
 
 
Сообщение13.04.2006, 13:59 
У любого конструктивного числа (куда относятся фактический все употребляемые числа, несмотря на то, что их количество всего счётно) цифры не случайны и находятся по конкретному алгоритму. Поэтому, можно говорить только о прохождении каких то тестов на случайность.

 
 
 
 
Сообщение13.04.2006, 14:32 
Аватара пользователя
Руст писал(а):
У любого конструктивного числа (куда относятся фактический все употребляемые числа, несмотря на то, что их количество всего счётно) цифры не случайны и находятся по конкретному алгоритму. Поэтому, можно говорить только о прохождении каких то тестов на случайность.


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

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

 
 
 
 
Сообщение13.04.2006, 22:32 
Артамонов Ю.Н. писал(а):
Таким образом, исходную последовательность можно считать случайной с заданным законом распределения, если для любой наперед выбранной конечной последовательности через расчетное число раз (исходя из предполагаемого закона распределения) эта конечная последовательность встретится в исходной.

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

 
 
 
 
Сообщение13.04.2006, 22:37 
А, я понял, как переводится на человеческий язык определение случайности по Кнуту. Рулетка (честная, без зеро) называется случайной, если невозможна система, дающая ненулевое матожидание выигрыша :)

 
 
 
 
Сообщение14.04.2006, 09:45 
Аватара пользователя
Любая случайность – это сложная закономерность. Если Вы примешиваете в нашу случайную последовательность какую-либо простую закономерность, то лишь искажаете закон распределения – Вы не встретите в исходной последовательности за расчетное число раз (исходя из принятого ранее закона распределения) заданную конечную последовательность.
Вообще, если далее философствовать – то в природе есть случайность лишь от сущности, т.е. того, что внутренне свободно от того, где находится, например, человек – внутренне свободен от внешнего мира и поэтому может диктовать ему свою волю, которая кажется непрогнозируемой закономерностью, т.е. случайностью.

 
 
 [ Сообщений: 99 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group