flying_bear ([info]flying_bear) wrote,
@ 2008-10-10 22:11:00
Previous Entry  Add to memories!  Tell a Friend  Next Entry
Entry tags:наука умеет много гитик 2

Случайность
(в продолжение некоторых обсуждений с [info]kdv2005, процитированных вот здесь: http://vladimirpotapov.livejournal.com/612270.html)

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

Если ужать до карикатуры, здесь описана процедура, позволяющая генерировать случайные числа. В расположении карандашных меток нет никакого порядка, ни сгущений, ни разрежений. Они расположены случайно. Но ничего случайного, в житейском смысле (неопределенного, неконтролируемого, независящего от нас) в описанной процедуре нет. Она строго задана, то есть, является вполне детерминистской. Ее можно объяснить компьютеру. Здесь, правда, сразу возникнет проблема - компьютер не понимает, что такое иррациональное число. Все, что можно реально записать в (цифровом) компьютере с конечной памятью за конечное время, сведется, в конце концов, к целым числам, или к рациональным, как отношению целых. Но, если аппроксимировать два пи, сколь угодно хорошо, отношением рациональных чисел, процедура, рано или поздно, зациклится. Карандашные метки начнут повторяться. Равномерность заполнения нарушится. Реальная процедура никогда не дает нам истинно случайных чисел, но лишь псевдослучайные.

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

Тем самым, если классическая физика верна (и если физическая картина мира является полной), нет никакой случайности, кроме детерминистского хаоса. В квантовой механике, на первый взгляд, ситуация иная, квантовые события можно считать истинно случайными. Однако, не так все просто. Квантовая механика не дает никаких предсказаний о результатах индивидуальных событий, но, строго говоря, оставляет открытым вопрос о возможности таких предсказаний. Это - вопрос о "скрытых параметрах", который долгое время считался решенным однозначно, в отрицательном смысле. Однако, в недавней серии работ Ханса де Радта с сотрудниками (идите вот сюда: http://arxiv.org/find/quant-ph наберите в строчке "автор" De Raedt и тыцните, а дальше выбирайте по названиям) были построены вполне классические, детерминистские алгоритмы (а других не бывает по определению, компьютеру не скажешь "а теперь сделай мне случайно"), позволяющие вопроизводить результаты квантовых экспериментов, включая нарушения так называемых "неравенств Белла" (ух... не все сразу, ладно?). Эти алгоритмы выглядят весьма неестественно как истинная модель физической реальности (они, в частности, предполагают самообучение), но, тем не менее, дают контпример к расхожему утверждению о принципиальной невозможности детерминистской теории, дающей те же статистические предсказания, что и квантовая физика.

[info]shkrobius закончил бы этот пост вопросом - Существуют ли истинно случайные процессы и события? Так и сделаем.




Page 1 of 2
<<[1] [2] >>

(196 comments) - (Post a new comment)


[info]ninazino
2008-10-10 08:53 pm UTC (link)
нет никакой случайности, кроме детерминистского хаоса
И почему это меня нисколько не удивляет? :))

(Reply to this) (Thread)


[info]flying_bear
2008-10-10 09:05 pm UTC (link)
Ммм... Наверно, глубоко постигли суть мироздания?

(Reply to this) (Parent)


[info]vladimirpotapov
2008-10-10 08:53 pm UTC (link)
Спасибо. Но отложу-ка я это дело на утро. :)

(Reply to this) (Thread)


[info]flying_bear
2008-10-10 09:04 pm UTC (link)
Спокойной ночи!

(Reply to this) (Parent)

Естествоиспытатели...
[info]apolitician
2008-10-10 09:03 pm UTC (link)
Тех, кто отрицает за чем-либо сущим случайности, следовало бы пытать до тех пор, пока они не признают, что их можно было и не пытать. (Д. Скотт, via shestov).

(Reply to this) (Thread)

Я Вам говорил, что Шестов мудак? Или нет, не Вам...
[info]flying_bear
2008-10-10 09:08 pm UTC (link)
На лице дона Рэбы появилась приторность.
- Мой дорогой дон Румата, - сказал он. - Простите, пока я буду
называть вас этим именем. Так вот, обыкновенно я никогда ничего не
доказываю. Доказывают там, в Веселой Башне. Для этого я содержу опытных,
хорошо оплачиваемых специалистов, которые с помощью мясокрутки святого
Мики, поножей господа бога, перчаток великомученицы Паты или, скажем,
сиденья... э-э-э... виноват, кресла Тоца-воителя могут доказать все, что
угодно. Что бог есть и бога нет. Что люди ходят на руках и люди ходят на
боках. Вы понимаете меня? Вам, может быть, неизвестно, но существует целая
наука о добывании доказательств.
http://lib.ru/STRUGACKIE/be_god.txt

(Reply to this) (Parent)(Thread)

Re: Я Вам говорил, что Шестов мудак? Или нет, не Вам... - [info]apolitician, 2008-10-10 09:11 pm UTC

[info]apolitician
2008-10-10 09:09 pm UTC (link)
Будучи естественнонаученным программистом, не могу не заметить, что детерминистского хаоса как реализации абстрактного понятия о случайности достоточно как для существования мира самого по себе, так и для нашего понимания о мире и механизмах его существования. Возможны, конечно, и еще какие-нибудь реализации, ну и что? Как, скажем, есть Java, есть C++. Можно и еще чего-нибудь навыдумывать в этом роде, но вроде и так хорошо. Это я размышляю как бы с т.з. того, кто выдумывает этот мир.

(Reply to this) (Thread)


[info]flying_bear
2008-10-10 09:15 pm UTC (link)
Ну и отлично, что все так получается. Достаточно так достаточно.

(Reply to this) (Parent)


[info]dtim
2008-10-10 09:41 pm UTC (link)
А что Вы думаете о работах Пригожина? Насколько я помню, он говорил об истинной, даже не квантовой, случайности и об ее принципиальной роли в ряде процессов (или я что-то путаю?).

(Reply to this) (Thread)


[info]flying_bear
2008-10-10 09:52 pm UTC (link)
Пригожин (в последних работах, уже не столько научных, сколько философско-поэтических) говорил о введении необратимости на фундаментальный уровень. Т.е., не выводить второе начало термодинамики, а просто постулировать. Ну... это он с отчаянья, мне кажется. Вывести-то так и не смогли. Вот и приходится говорить - зелен виноград, не больно-то и хотелось, и все такое. Но пока теорем нет (а их нет) - вопрос веры.

(Reply to this) (Parent)(Thread)

(no subject) - [info]faceted_jacinth, 2008-10-11 08:03 pm UTC
(no subject) - [info]faceted_jacinth, 2008-10-11 08:03 pm UTC
(no subject) - [info]flying_bear, 2008-10-11 08:16 pm UTC
(no subject) - [info]faceted_jacinth, 2008-10-11 08:39 pm UTC
(no subject) - [info]faceted_jacinth, 2008-10-11 08:43 pm UTC
(no subject) - [info]flying_bear, 2008-10-11 08:49 pm UTC
(no subject) - [info]flying_bear, 2008-10-11 08:50 pm UTC
(no subject) - [info]faceted_jacinth, 2008-10-11 08:59 pm UTC
(no subject) - [info]flying_bear, 2008-10-11 09:14 pm UTC
(no subject) - [info]faceted_jacinth, 2008-10-11 09:16 pm UTC
(no subject) - [info]flying_bear, 2008-10-11 09:22 pm UTC
(no subject) - [info]faceted_jacinth, 2008-10-11 09:28 pm UTC
(no subject) - [info]flying_bear, 2008-10-11 09:31 pm UTC
(no subject) - [info]faceted_jacinth, 2008-10-11 09:36 pm UTC
(no subject) - [info]faceted_jacinth, 2008-10-11 09:38 pm UTC
(no subject) - [info]flying_bear, 2008-10-11 09:44 pm UTC
(no subject) - [info]faceted_jacinth, 2008-10-11 09:11 pm UTC
(no subject) - [info]faceted_jacinth, 2008-10-11 09:14 pm UTC
(no subject) - [info]flying_bear, 2008-10-11 09:16 pm UTC
(no subject) - [info]faceted_jacinth, 2008-10-11 09:22 pm UTC
(no subject) - [info]flying_bear, 2008-10-11 09:25 pm UTC

[info]dyak
2008-10-10 10:17 pm UTC (link)
А почему компьютерная программа на абстрактном компьютере названа "реальной процедурой"?

Для меня реальная процедура -- это выбор точек физическим карандашом на физической окружности; и тут зацикливания я не ожидаю. А что абстрактный компьютер зациклится, ну так от умозрительной системы с конечным числом состояний чересчур много ждать не следует (а реальный компьютер может еще и бит флипнуть по квантовой случайности изредка).

(Reply to this) (Thread)


[info]flying_bear
2008-10-10 10:31 pm UTC (link)
Там по ссылкам как раз и обсуждается, какова природа случайности в реальных физических процессах. В частности, случайна ли квантовая случайность.

(Reply to this) (Parent)


[info]yurvor
2008-10-10 10:24 pm UTC (link)
Я прочёл вот это - http://arxiv.org/PS_cache/arxiv/pdf/0712/0712.2574v1.pdf

Собственно, там построен пример, похожий на Ваш с окружностью - мы можем построить детерминистский алгоритм, выдающий похожие результаты, что и квантовая физика.

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

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

___
И в связи с этим возникает такой вопрос - а что, собственно, такое "истинно случайные события"? Какая разница, что именно мешает предсказанию - "принцип истинной случайности" или "принцип невозможности отмотать назад и посмотреть, что там было"? И, быть может, это один и тот же принцип?

(Reply to this) (Thread)


[info]flying_bear
2008-10-10 10:33 pm UTC (link)
> Какая разница, что именно мешает предсказанию

Прагматически, наверно, никакой. А если хочется понимания - вопрос вполне осмысленный.

(Reply to this) (Parent)(Thread)

(no subject) - [info]yurvor, 2008-10-10 10:45 pm UTC
(no subject) - [info]flying_bear, 2008-10-10 10:48 pm UTC
(no subject) - [info]yurvor, 2008-10-10 11:00 pm UTC

[info]urod
2008-10-11 12:54 am UTC (link)
> Однако, в недавней серии работ Ханса де Радта с сотрудниками (идите вот сюда: http://arxiv.org/find/quant-ph наберите в строчке "автор" De Raedt и тыцните, а дальше выбирайте по названиям) были построены вполне классические, детерминистские алгоритмы (а других не бывает по определению, компьютеру не скажешь "а теперь сделай мне случайно"), позволяющие вопроизводить результаты квантовых экспериментов

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

(Reply to this) (Thread)


[info]flying_bear
2008-10-11 10:49 am UTC (link)
Ну и как там, под столом? Не дует?

(Reply to this) (Parent)


[info]marina_p
2008-10-11 03:00 am UTC (link)
"Если ужать до карикатуры, здесь описана процедура, позволяющая генерировать случайные числа. В расположении карандашных меток нет никакого порядка, ни сгущений, ни разрежений. Они расположены случайно."

В каком смысле случайно? Что-то в моё понимание случайности такое не укладывается...

Что именно вы тут считаете случайным:
- последовательность точек (как сопоставление i -> x_i)?
- множество точек окружности, полученное при i=1..n для какого-то фиксированного n?
- бесконечное множество точек, полученное таким образом?

(Reply to this) (Thread)


[info]flying_bear
2008-10-11 10:50 am UTC (link)
Последнее.

(Reply to this) (Parent)(Thread)

(no subject) - [info]marina_p, 2008-10-11 10:51 am UTC
(no subject) - [info]flying_bear, 2008-10-11 11:09 am UTC
(no subject) - [info]marina_p, 2008-10-11 11:52 am UTC
(no subject) - [info]flying_bear, 2008-10-11 12:02 pm UTC
(no subject) - [info]marina_p, 2008-10-11 12:12 pm UTC
(no subject) - [info]flying_bear, 2008-10-11 01:43 pm UTC
(no subject) - [info]flying_bear, 2008-10-11 01:44 pm UTC
(no subject) - [info]marina_p, 2008-10-11 02:02 pm UTC
(no subject) - [info]flying_bear, 2008-10-11 02:11 pm UTC
(no subject) - [info]flying_bear, 2008-10-11 02:16 pm UTC
(no subject) - [info]marina_p, 2008-10-11 02:21 pm UTC
(no subject) - [info]flying_bear, 2008-10-11 02:26 pm UTC
(no subject) - [info]marina_p, 2008-10-11 02:17 pm UTC
(no subject) - [info]flying_bear, 2008-10-11 02:29 pm UTC
(no subject) - [info]marina_p, 2008-10-11 02:24 pm UTC
(no subject) - [info]marina_p, 2008-10-11 02:26 pm UTC
(no subject) - [info]kdv2005, 2008-10-11 02:27 pm UTC
(no subject) - [info]flying_bear, 2008-10-11 03:05 pm UTC
(no subject) - [info]kdv2005, 2008-10-11 03:13 pm UTC
(no subject) - [info]flying_bear, 2008-10-11 02:31 pm UTC

[info]slobin
2008-10-11 05:42 am UTC (link)
Не, фигня какая-то, нельзя такие вещи по ночам читать. Или я от бессонницы чего-то не понял, или по той же схеме, что и у этого де Радта, можно вообще избавиться от корпускулярно-волнового дуализма. А что: берём школьный опыт с двумя щелями, и говорим, что пластинка помнит, в какой фазе к ней пришёл предыдущий фотон. Фотоны, естественно, крутящиеся шарики, никаких волн. Дифракционная картина получается на ура. Правда, нет локальности (помнить должна вся пластинка, а не щели по отдельности), но она и не нужна: чем реже приходят фотоны, тем больше у щелей времени, чтобы обменяться опытом.

А конкретно в де Радтовской модели, если я его правильно понял посреди ночи, поляризаторы с заявленными им свойствами должны неправильно вести себя при освещении пучком с круговой поляризацией. Кажется. По моему. Если не путаю.

... Беспредел Шеннона ...

(Reply to this) (Thread)


[info]flying_bear
2008-10-11 10:51 am UTC (link)
> или по той же схеме, что и у этого де Радта, можно вообще избавиться от корпускулярно-волнового дуализма

Да. Об этом и речь.

(Reply to this) (Parent)(Thread)

(no subject) - [info]slobin, 2008-10-11 08:40 pm UTC
(no subject) - [info]flying_bear, 2008-10-11 08:57 pm UTC

[info]buddha239
2008-10-11 08:14 am UTC (link)
А мне можно?:)

"В расположении карандашных меток нет никакого порядка, ни сгущений, ни разрежений." - картина очень не случайная. Псевдослучайные числа совсем не так получают.:)

Кстати, один из наименее доступных вопросов в математике - что можно сказать про последовательность цифр пи.

(Reply to this) (Thread)


[info]flying_bear
2008-10-11 10:56 am UTC (link)
Что псевдослучайные числа получают совсем не так, я знаю. Но это простейшая известная мне модель, напоминающая случайность в статистической физике. С возможностью замены среднего по времени средним по ансамблю.

(Reply to this) (Parent)(Thread)

чуть подробнее ответил Марине - [info]flying_bear, 2008-10-11 11:12 am UTC
Re: чуть подробнее ответил Марине - [info]flying_bear, 2008-10-11 01:46 pm UTC
(no subject) - [info]buddha239, 2008-10-11 05:57 pm UTC
Часть 1
[info]kdv2005
2008-10-11 04:04 pm UTC (link)
Интересный разговор получается. Давайте я тут соберу несколько замечаний математического характера, которые, как мне кажется, иллюстрируют математическую сторону этого вопроса. Видимо все из них под одну крышу не поместятся и я заранее разобью свой комментарий на части.

С точки зрения математики вопрос о том, что такое случайность, условно делится на две части: первая посвящена вопросу о том, что такое случайность, как правильно ее понимать и каковы ее свойства, а вторая -- существует ли случайность в мире и каковы ее источники. Первой группой вопросов занимается теория вероятностей (она, конечно и еще много чем занимается, но не будем отвлекаться) и в начале 20-го века ее развитие в ее развитии произошел качественный скачок, связанный с тем что выкристаллизовалось математическое понятие случайности. Результатом этой кристаллизации стало понимание, что математическим содержанием нужно наполнять лишь одно из многих значений житейского, интуитивного понятия "случайный". Часто, говоря о случайном выборе, мы подразумеваем выбор, сделанный наобум, без осознанного, осмысленного усилия. Говоря о случайном исходе эксперимента или о том, что результаты наблюдений случайны, мы нередко пытаемся сказать, что их зависимость от разнообразных параметров настолько сложна и так мало нам известна, что мы признаем практическую невозможность учесть влияние всех факторов и предсказать результат. Иными словами, здесь случайность означает признание неполноты наших знаний, либо о себе, как в первом случае, либо о внешнем мире. И, наконец, иногда мы говорим о случайности когда хотим подчеркнуть, что никакой видимой зависимости между двумя событиями/экспериментами/наблюдениями нет, они никак между собой не связаны, и поэтому их результаты "сочетаются случайно". Таковы, например, исходы одновременного бросания двух монет двумя людьми. (Сторонники детерминизма тут могут придраться, говоря, что принципиально зависимость есть, даже если для этого нужно написать уравнения Гамильтона (или даже Шредингера), описывающиее весь процесс на атомарном уровне. Это важное замечание, я вернусь к нему позже, если не забуду, а пока бы хотел обсуждать вопрос на житейском уровне).

(Reply to this)

Часть 2
[info]kdv2005
2008-10-11 04:04 pm UTC (link)
Рывок, совершенный теорией вероятностей в своем развитии, был связан с осознанием, что математическую теорию случайности следует основывать на последнем смысле слова случайности -- на отсутствии какой-либо зависимости результатов двух экспериментов между собой. Как это часто бывает и в естественных науках, теория вероятностей быстро двинулась вперед только после отказа от попыток ответить на философский вопрос, что есть случайность, какова ее природа, и ограничилась изучением свойств случайности, предварительно дав свое, более узкое и четкое определение этого понятия.

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

Центральным понятием теории вероятностей при таком подходе становится понятие независимости случайных величин (и условного распределения случайной величины), основанное на принципе кореллируемости: если два источника случайности связаны между собой функционально (полностью или частично, например, завися от общего параметра), то такая зависимость может быть выявлена статистически, наблюдениями за парами их значений.
Каноническим примером этого подхода является последовательность испытаний Бернулли: последовательность независимых случайных величин, каждая из которых может принимать значения 0 и 1 с вероятностью 1/2, независимо от того, какие значения были приняты остальными случайными величинами. Последовательность испытаний Бернулли обычно связывают с процессом бросания идеализированной симметричной монетки. В некотором (хорошо определенном смысле), вся философская неоднозначность понятия случайности может быть сведена к этому примеру: имея в распоряжении такую бесконечную последовательность случайных величин средствами обычной, детермистской математики (алгебраическими операциями и переходом к пределу) можно изготовить любой набор случайных величин с нужными статистическими свойствами, как индивидуальными, так и совокупными.

Развитие приведенных выше идей привело в конечном счете к появлению в 20-х-30-х годах XX века нескольких аксиоматических теорий, формализующих понятие вероятности. Наиболее известной и распространенной из них стала аксиоматизация теории вероятностей на базе теории множеств, предложенная Колмогоровым. Я тем не менее хочу подчеркнуть, что ядром теории является не пресловутая тройка множество/σ-алгебра событий/нормированная мера, а понятия независимости и условного распределения, и именно содержательность следствий из определений двух последних понятий оправдывает существование классической теории вероятностей в изложенном виде. Я разумеется, намеренно сузил рамки, поскольку говорил лишь о случайности.

(Reply to this) (Thread)

Re: Часть 2
[info]ayudug
2008-10-13 05:20 pm UTC (link)
А можно поподробней про другие аксиоматические теории. Я что-то слышал про DLR формализм, там кажется в основу условная вероятность кладётся. Но вы что-то другое ввиду имеете? ДЛР это не так давно

(Reply to this) (Parent)(Thread)

Re: Часть 2 - [info]kdv2005, 2008-10-14 12:29 am UTC
Re: Часть 2 - [info]ayudug, 2008-10-15 03:17 pm UTC
Re: Часть 2 - [info]kdv2005, 2008-10-16 12:26 am UTC
(no subject) - [info]e2pii1, 2008-12-11 02:04 pm UTC
(no subject) - [info]kdv2005, 2008-12-11 08:26 pm UTC
Часть 3
[info]kdv2005
2008-10-11 04:43 pm UTC (link)
Вторая группа вопросов оказалась не в пример сложнее.
Одно дело описать свойства имеющейся случайности. И совсем другое дело --- описать, как эту случайность построить.

С одной стороны, задача упрощается тем, что достаточно научиться строить генератор последовательностей Бернулли (или, что эквивалентно, генератор, случайно выбирающий точку на единичном отрезке, не отдавая предпочтения ни одной из ней), после чего генератор любой случайности становится делом техники. С другой стороны, даже в этом, в некотором смысле, самом понятном и самом простом случае, мы должны явным образом описать, что это значит, выбрать число наудачу (неважно, из конечного или бесконечного множества, хоть из {0,1}, хоть из [0,1]). В математической постановке этой задачи требуется привести алгоритм построения такой последовательности выборов.

Задача, несомненно, противоречива. Всякий алгоритм, всякий закон, предсказывающий член последовательности по предыдущему (да хоть по всем предыдущим) немедленно указывает закон зависимости членов последовательности друг от друга, и тем самым, хоронит саму идею случайности на корню. Можно, конечно, сказать, что с точки зрения теории вероятностей нам особого дела нет до того, как одни члены последовательности зависят от других, если произведенная алгоритмом последовательность нулей и единиц (или точек единичного отрезка), обладает правильными статистическими свойствами, то задача решена и генератор построен.

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

(Reply to this)

Часть 4
[info]kdv2005
2008-10-11 05:23 pm UTC (link)
Таким образом, для построения "истинно случайной" последовательности мы должны следить, чтобы в ней не появлялось симметрий ни при разбиении ее на пары, ни на тройки и ни на какие другие группы из k элементов. Разумеется, бывают и другие, более сложные симметрии, и хорошо бы, чтобы искомый алгоритм препятствовал и их возникновению. Но отсюда ясно, что такой алгоритм, следящий за разнообразными корелляциями в нашей последовательности, не может быть слишком простым.

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

(Reply to this)


[info]kdv2005
2008-10-11 05:25 pm UTC (link)
Части 5 и 6 завтра. Я понимаю, что там-то самое интересное и есть, с точки зрения обсуждения здесь, но не успеваю. Извините.

(Reply to this) (Thread)


[info]flying_bear
2008-10-11 05:33 pm UTC (link)
Спасибо огромное! Будем ждать.

(Reply to this) (Parent)(Thread)

(no subject) - [info]kdv2005, 2008-10-12 05:35 am UTC
(no subject) - [info]flying_bear, 2008-10-12 10:42 am UTC
(no subject) - [info]shkrobius, 2008-10-12 12:56 am UTC
(no subject) - [info]kdv2005, 2008-10-12 05:23 am UTC

[info]kobak
2008-10-11 08:17 pm UTC (link)
Это очень интересно. Я давно собираюсь сесть и внимательно прочесть тексты de Raedt'а, которого Вы время от времени упоминаете, и потом написать Вам свои вопросы (если они останутся). Но никак не могу этим заняться: пытался просмотреть эти статьи мельком, но не разобрался тогда толком.

Если я правильно помню, немного мешает то, что он всё время открытым текстом отстраняется от концептуальных рассуждений (мы, мол, описываем нашу модель, а об интерпретации сами думаете). Потому что хочется как раз увидеть его интерпретационные выводы. Вроде бы речь там идет о *локальной* модели (это противоречит тому, что написал [info]slobin выше)... а это вроде бы невозможно.

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

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

(Reply to this) (Thread)


[info]flying_bear
2008-10-11 08:32 pm UTC (link)
Да, отстраняется. Это его принципиальная позиция. Слишком много было болтовни и пускания слюней вместо нормальных научных обсуждений по этим вопросам. Давайте сначала разберемся с математикой. Например, откуда взялись популярные взгляды, что это "вроде бы невозможно", и что это утверждение на самом деле означает (и означает ли вообще хоть что-нибудь).

Это, безусловно, не мейнстрим. Но работы печатаются в нормальных журналах (тоже, не сразу, а после некоторого периода полного отторжения) и постепенно осваиваются в комьюнити. Медленнее, чем хотелось бы. Ну, что я могу поделать с тем, что подавляющее большинство обзоров и книг по концептуальным проблемам квантовой механики пишут балаболы и пустозвоны?

(Чтобы полностью расставить все точки над i - я, конечно, предвзят. Ханс мой друг, постоянный соавтор, и - говорю, опираясь на личные впечателения, - человек, безусловно, исключительно глубокий. В отличие от некоторых, тоже лично знакомых мне, признанных специалистов по quantum computation и т.п. Не будем показывать пальцами).

(Reply to this) (Parent)(Thread)

(no subject) - [info]kobak, 2008-10-13 06:47 pm UTC

[info]shkrobius
2008-10-12 01:56 am UTC (link)
I just finished reading De Raedt's papers on DLM's (his 2005 paper on Mach-Zehnder is the most lucid, in my opinion), and it is amazing how far one can go with this approach. I read a few papers a while ago in which Clifford and Grassmann hidden variables seemed to reproduce a lot of correlations and even violated Bell's inequality. I wonder if the DLM is doing something similar because it is non-commutativity of the operations in the algorithm that does the trick. My problem with the toy models has always been that I would like to see all of the QM coming out rather than very schematic trial schemes. I understand that these are very important, but so are atoms. It boild down to whether it is possiblt to find, say, a universal DLM or whatever nontrivial hidden variables that ALWAYS do the job. Only then would it be possible to banish chance.

As for the question itself, I do not have a clue. My intuition tells me that randomness is lack of knowledge and/or inability to predict. I regard it as the property of models. In this sense, DLM is not changing much. The lack of insight whether QM is truly random is replaced with the lack of insight whether the randomness is due to QM or due to DLM. On the other hand you ask whether it exists. So it boils down what it means to exist. We once discussed whether electrons exist and did not find common ground. Randomness is harder. The only definition of existence that appeals to me is by Leibnitz as maximum compossibility. By this definition true randomness cannot exist.

(Reply to this) (Thread)

(Deleted post)
(no subject) - [info]shkrobius, 2008-10-12 03:14 am UTC
(no subject) - [info]flying_bear, 2008-10-12 10:37 am UTC
(no subject) - [info]flying_bear, 2008-10-12 02:19 am UTC

[info]meshulash
2008-10-12 11:35 am UTC (link)
Последовательность цифр в числе Пи случайна в смысле колмогоровской сложности: что-то случайно если длина описания этого чего-то совпадает с самим этим чем-то. Как я понял, kdv2005 ниже начал подробно говорить об этом. Но, как я понимаю, для физики, где формально речь всегда идет о рациональных числах и конечных последовательностях (других результатов при измерении, насколько я понимаю, не бывает), это не имеет особого смысла. Если я не ошибаюсь, Вы когда-то подчеркивали в связи с этим разницу между частотами по фон Мизесу и вероятностями по Колмогорову.

(Reply to this) (Thread)


[info]flying_bear
2008-10-12 07:32 pm UTC (link)
Пусть допишет. С нетерпением жду. Потом обсудим.

(Reply to this) (Parent)

(no subject) - [info]spamsink, 2008-10-13 05:59 pm UTC
(no subject) - [info]meshulash, 2008-10-14 04:55 pm UTC
Часть 5
[info]kdv2005
2008-10-12 05:16 pm UTC (link)
Содержание предыдущих четырех частей можно резюмировать так: математическая случайность, изучаемая теорией вероятностей, основана на идее независимости. Если эксперименты X и Y со случайными исходами независимы, то знание результата эксперимента X никак не позволяет уточнить прогноз исхода эксперимента Y. Пространства исходов этих экспериментов "ортогональны" и прогноз исхода Y, построенный с учетом информации об X, всегда будет совпадать с прогнозом Y, построенный в отсутствие информации об X.

Математик бы сказал (с небольшой натяжкой), что теория вероятностей изучает меры на бесконечных произведениях множеств.

Такая случайность имеет сильные свойства непредсказуемости, что с одной стороны, позволяет получать содержательные математические утверждения о ней, а с другой стороны делает задачу о построении такой случайности на практике бесконечно сложной. С общефилософской точки зрения, это, конечно, не противопоставление, а два проявления одного и того же качества --- сложности: чем сложнее описание математического объекта, тем меньше произвола в его устройстве и тем богаче, как правило, его свойства. Вероятностная случайность, в этом смысле, конечно же, сложна. Даже в простейшем случае последовательности испытаний Бернулли (которая, как мы помним, всего-навсего моделирует бросания монетки) генератор такой случайности должен удовлетворять бесконечному (более точно счетному) числу условий. Именно поэтому комбинаторные и арифметические методы построения случайности обречены на провал --- степеней свободы не хватает для того, чтобы удовлетворить всем требованиям.

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

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

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

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

(Reply to this)

Часть 6
[info]kdv2005
2008-10-12 05:16 pm UTC (link)

Кстати, прошу иметь в виду, что развитие ни теории вероятностей, ни теории динамических систем, ни эргодической теории исторически не следовало ибранной мной логике изложения. Все обсуждаемые мною вопросы поднимались в этих разделах математики и предпринимались попытки их осмысления, но не в таком порядке, и помимо них была масса других не менее важных и интересных вопросов. В любом случае, я не пытаюсь дать ни очерк истории, ни математический обзор, тем более, что это в формате комментариев к неформальной дискуссии в ЖЖ, это просто неосуществимо. Я лишь описываю свою интерпретацию вопроса, которая, разумеется, может оказаться недостаточно глубокой для проникновения в суть проблемы.

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

Таким образом, дальнейшее продвижение в изучении случайных последовательностей должно сопровождаться изменением его постановки.
Эргодическая теория ставит проблему следующим образом: так же, как мы не можем многое сказать об индивидуальной истинно случайной последовательности из нулей и единиц, мы не можем много сказать и о хаотических свойствах индивидуальной траектории. Для того, чтобы данная система могла претендовать на титул хаотической, хаотическое поведение должно быть не свойством отдельных, специально избранных или построенных, траекторий, оно должно быть коллективным свойством всех траекторий, которым обладает каждый типичный представитель семейства всех траекторий. Поэтому нужно изучать вопрос не о том, что мы можем сказать о каждой отдельной траектории, а о том, что мы можем сказать о поведении всех траекторий в целом и о поведении каждой типичной траектории.

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

(Reply to this)

Часть 7
[info]kdv2005
2008-10-12 06:08 pm UTC (link)
В качестве иллюстрации этого подхода и чтобы стало яснее, какие трудности нас ждут в дальнейшем, рассмотрим простой математический пример. Он недостаточно содержателен, чтобы иметь самостоятельный физический смысл, но, несмотря на простоту, содержит в себе многое из того, о чем я буду говорить в дальнейшем, в том числе в нем мы уже сталкиваемся со многими характерными трудностями, связанными с хаотичностью.

Рассмотрим преобразование T, задаваемое формулой
x->2x (mod 1)
Это преобразование отображает единичный отрезок [0,1] в себя по очень простому правилу. Всякое число x удваивается, после чего от 2x оставляется лишь его дробная часть.

Взяв в качестве начальной некоторую точку x_0 и применяя к ней последовательно наше преобразование, получаем последовательность точек (x_n):
x_{n+1}= Tx_n, n≥0
которая называется траекторией точки x_0.

Я утверждаю, что преобразование T является генератором математической случайности в самом строгом, вероятностном смысле. Для этого с траекторией каждой точки свяжем последовательность нулей и единиц a_0 a_1 ... a_n ... следующим образом. Пользуясь введенными обозначениями положим
a_n=0, если x_n лежит между 0 и 1/2,
и a_n=1, если x_n лежит между 1/2 и 1.
Чтобы избежать придирок к неоднозначности описания, условимся, что в случае, когда x_n=1/2, в качестве a_n всегда берется 1. К этому соглашению тоже можно придраться, но к концу обсуждения станет ясно (я на это надеюсь), что все эти придирки не по существу и какое именно принято соглашение --- в этом случае неважно.

Преобразование T имеет неподвижную точку x=0, которой отвечает символическая последовательность из одних нулей. Точке x=1/2 соответствует последовательность 10000..., а точке x=1/3 --- символическая последовательность 0101010101... периода 2.

Ясно, что при таком сопоставлении всякому числу x ставится в соответствие двоичная последовательность, являющаяся его разложением в двоичную дробь. (Несложно построить аналогичное преобразование единичного отрезка, при котором аналогичное соответствие устанавливается между числами и их представлениями в виде десятичных дробей. Но двоичные проще, ими мы и ограничимся.) В частности, вопрос о построении истинно случайной последовательности нулей и единиц сводится в нашем генераторе к подбору подходящего стартового значения для траектории. Рациональные числа в качестве стартовых точек не годятся, им соответствуют периодические, начиная с некоторого места (ах, как не хватает в русском языке слова eventually!), последовательности. Поэтому исключим из дальнейшего рассмотрения все рациональные числа. Оставшееся множество начальных условий по-прежнему имеет длину 1 и содержит достаточный материал для построения случайности.

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

(Reply to this)

Часть 8
[info]kdv2005
2008-10-12 06:55 pm UTC (link)
Чтобы два раза не вставать, добавлю, что действия отображения T в символическом представлении описывается очень просто: переходу от x к Tx соответствует стирание первого элемента в двоичном разложении числа x. Можно представить, что вся двоичная дробь, представляющая число x сдвигается на один разряд влево, при этом, разумеется, знак, стоящий в первом разряде после запятой безвозвратно теряется. В этом случае говорят, что в символическом представлении преобразование T действует как левый сдвиг в пространстве двоичных последовательностей.

Мы не можем описать выбор начальной точки траектории x_0, породившей бы истинно случайную последовательность нулей и единиц. На это накладывает запрет теория сложности: перечисление всех знаков истинно случайной двоичной последовательности означает явное задание числа x_0 в виде двоичной дроби.

Теперь сменим точку зрения и зададимся вопросом, много ли среди на единичном отрезке точек, траекториям которых соответствуют истинно случайные последовательности. Нетрудно описать множество всех точек отрезка, символическое представление которых начинается с 0: это отрезок [0,1/2] (еще раз, последний, напоминаю, что двоично-рациональные точки исключены из рассмотрения), его длина равна 1/2. Аналогично, множество всех точек отрезка, второй элемент символического представления которых есть 0, представляет собой объединение двух отрезков [0,1/4] и [1/2,3/4], суммарная длина которых равна 1/2. Первый из них образован точками, символическое представление которых начинается с 00, а второй -- точками, символическое представление которых начинается с 10. Заметим, что длина каждого из этих двух отрезков равна 1/4. Аналогично, задание n-того символа в двоичном представлении числа x выделяет на единичном отрезке множество, представляющее собой объединение 2^n непересекающихся отрезков длины 1/2^{n+1}. Суммарная длина этих отрезков равна 1/2, и каждый из этих отрезков образован точками (теми и только теми), у которых первые n знаков при разложении в двоичную дробь совпадают.

(Reply to this) (Thread)

Re: Часть 8
[info]_glav_
2008-10-20 09:40 pm UTC (link)
прежде всего хочу поблагодарить за весь текст: прочитал на одном дыхании, - и попросить прощения у хозяина журнала за вторжение.
У меня возник, что называется, "уточняющий вопрос" (скорее всего, это просто проговаривание моими словами ровно того же, что Вы написали, но тем не менее).

правильно ли я понимаю, что получаемая таким образом последовательность нулей и единиц есть ни что иное, как двоичное представление изначально выбранной точки x_0 (так что любая случайная последовательность может быть отображена в какое-то одно единственное иррациональное число единичного отрезка)?
Ведь при сдвиге влево ("стирании" первого элемента) (происходящем, как Вы отметили, при переходе от х к Тх) мы "переходим" на следующую цифру исходного числа, которая и есть 0, если новое число последовательности лежит между [0, 1/2], и 1, если оно между [1/2, 1].

(Reply to this) (Parent)(Thread)

Re: Часть 8 - [info]kdv2005, 2008-10-20 10:06 pm UTC
Часть 9
[info]kdv2005
2008-10-12 07:29 pm UTC (link)
Тут, конечно, впору остановиться, и завопить, что ведь если в нашем примере всюду заменить слово "длина" словом "вероятность", то наша последовательность символов превращается в последовательность независимых испытаний Бернулли. Ну да, так и есть, мы построили генератор случайных двоичных последовательностей из нулей и единиц. Если дать ему в качестве начального значения некоторое число (программисты бы назвали его seed, физики в аналогичной ситуации нередко используют слово Ansatz), и начать последовательно применять преобразование T, то первые знаки у чисел из построенной траектории (в двоичном разложении) и дадут некоторую реализацию последовательности испытаний Бернулли.

Несмотря на то, что мы, неосторожно выбрав начальное условие, можем получить периодическую последовательность, вероятность того, что это произойдет равна нулю, поскольку множество рациональных чисел, будучи счетным, имеет нулевую длину. Более того, согласно закону больших чисел, с вероятностью 1 в построенной нами последовательности единицы и нули будут встречаться с одинаковой частотой -- 1/2, пары 00, 01, 10 и 11 -- с частотой 1/4, и вообще, всякая фиксированная последовательность нулей и единиц длины n будет встречаться с частотой 1/2^n. Таким образом, с вероятностью 1 построенная нами реализация испытаний Бернулли будет истинно случайной последовательностью. Иными словами, множество начальных значений x, на отрезке [0,1], хоть и не состоит из всех точек, но все равно имеет длину 1. Элементы этого множества называются типичными точками. Таким образом, типичное начальное условие порождает истинно случайную последовательность нулей и единиц, то есть последовательность, свободную от всех корелляций.

(Reply to this) (Thread)

Поправка
[info]kdv2005
2008-10-12 09:55 pm UTC (link)
Иными словами, множество начальных значений x, на отрезке [0,1], порождающих истинно случайные двоичные последовательности, хоть и не состоит из всех точек, но все равно имеет длину 1.

(Reply to this) (Parent)

Тайм-аут
[info]kdv2005
2008-10-12 07:30 pm UTC (link)
Уф. Продолжение следует, но несколько позже.

(Reply to this) (Thread)

огласите пжлссста <i>весь</i> список...
[info]flying_bear
2008-10-12 07:33 pm UTC (link)
Огромное спасибо!!! Обсуждать, наверно, имеет смысл, когда закончите.

(Reply to this) (Parent)

Re: Тайм-аут - [info]shkrobius, 2008-10-13 01:42 am UTC
Re: Тайм-аут - [info]a_shen, 2008-10-13 08:01 pm UTC
Re: Тайм-аут - [info]kdv2005, 2008-10-14 12:23 am UTC
Re: Тайм-аут - [info]kdv2005, 2008-10-14 12:24 am UTC
попробовал написать - [info]a_shen, 2008-10-18 11:45 am UTC
(no subject) - [info]e2pii1, 2008-12-12 11:52 am UTC
это объяснение переносит - [info]a_shen, 2008-12-12 06:41 pm UTC
Re: это объяснение переносит - [info]e2pii1, 2008-12-12 07:25 pm UTC
ну да, - [info]a_shen, 2008-12-12 08:05 pm UTC
Re: ну да, - [info]e2pii1, 2008-12-12 08:29 pm UTC
Re: Тайм-аут - [info]a_shen, 2008-10-18 11:46 am UTC
Re: Тайм-аут - [info]a_shen, 2008-10-18 11:48 am UTC
Re: Тайм-аут - [info]a_shen, 2008-10-18 11:49 am UTC
PS - [info]a_shen, 2008-10-18 11:50 am UTC
Re: PS - [info]flying_bear, 2008-10-18 01:09 pm UTC
боюсь, что - [info]a_shen, 2008-10-18 03:20 pm UTC
Re: боюсь, что - [info]flying_bear, 2008-10-18 03:30 pm UTC
Re: PS - [info]kdv2005, 2008-10-18 04:31 pm UTC

(196 comments) - (Post a new comment)

Page 1 of 2
<<[1] [2] >>

Create an Account
Forgot your login or password?
Login w/ OpenID
English • Español • Deutsch • Русский…