?

Log in

No account? Create an account
По делам сюда приплыл, а не за этим [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

о случайных последовательностях [окт. 10, 2019|09:04 pm]
Anatoly Vorobey
[Tags|, ]

"Не понимаю я этой вашей теории вероятности.
Вот я, скажем, кидаю монетку. Мильон раз. И получаю на выходе мильон орлов. Это ведь невероятно? Такого не может быть.
ОК. Тогда я кидаю монетку и получаю 1101011110010110100011..., ну, до миллиона сами дополните.
Но ведь это же ровно так же невероятно и не может быть! Если бы я играл в Спортлото и записал бы это число, его выпадение было бы не более вероятным, чем 111111111111..., да?
Чего я не понимаю?" (отсюда)


Некоторые мысли по теме.

1.

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

Давайте проделаем следующий мысленный эксперимент. Будем тысячу раз подряд выбирать одно из двух, но не бросая монетку, а по-другому. Наш первый выбор будет - между 0 и 1. Второй - между орлом и решкой. Третий - между "лево" и "право". Четвертый - между "инь" и "ян". И так далее. Каждый раз мы выбираем один из двух вариантов, но варианты все время из разных категорий, не связанных друг с другом. Реализм или романтизм. Юбка или брюки. "Канон" или "Никон". Порядок категорий фиксированный: первый выбор всегда между 0 и 1, второй между орлом и решкой и так далее. Но внутри каждой категории выбор случайный. Как именно происходит выбор? Это не очень важно для данного мысленного эксперимента, но можно представить, например, что эти два слова быстро сменяют друг друга на экране, много раз в секунду, вы закрываете глаза и нажимаете на кнопку, то, что замерло на экране - и есть выбор. И так тысячу раз. Вы не можете даже сказать "я выберу всегда первый из двух вариантов", потому что они не стоят в каком-то конкретном порядке: я написал "инь и ян" выше, но мог написать "ян и инь", это ничего не значит. В момент выбора на экране у вас нет возможности различить их по принципу "первый-второй".

Итак, мы выбрали тысячу раз. У нас получился например результат: "0, право, ян, реализм, юбка, никон,..." В другой раз может быть "1, право, ян, романтизм, брюки, канон,...". И так далее. Это не очень удобно, нужно заранее придумать тысячу категорий, но предположим мы это сделали. Заменит ли такой "случайный выбор" тысячу бросков монетки? Смотря для чего нам было нужны были эти случайные броски. Если нам нужны были именно нули и единицы, это неудобно. А если нам нужны были эти броски каждый для разных решений, то нет проблем: мы заранее договорились, скажем, что "инь" будет означать поступить так-то, а "ян" иначе, и так для каждой категории.

Теперь главное, для чего это было нужно. Обратите внимание, что в результате такого эксперимента нет аналога "тысячу орлов подряд". Нет аналога "1111111...". Все возможные выборы абсолютно равноправны не только по теории вероятностей, но и по нашей интуиции, той самой, которая нашептывала нам "этот с 111111111.... врет или заблуждается". Если один человек к нам придет и скажет: я получил "0-право-ян-реализм-юбка-никон...", а другой "0-лево-инь-реализм-брюки-никон...", у нас нет никакой причины решить, что один из них меньше заслуживает доверия, чем другой. Почему, в чем разница между этим и бросками монетки?

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

2.

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

Но это как раз то отсутствие корреляции, которое мы видим в "разнородном" эксперименте с 0-лево-инь-реализм итд. Когда мы видим результаты бросков монетки, какие-то из них (например, 11111111....) могут заставить нас заподозрить, что на самом деле она не честная, и что обещанная независимость бросков друг от друга - ложь. Результатами "разнородного" эксперимента тоже могут быть не случайны, конечно (может, кто-то много раз подряд говорит, что у него получилось одна и та же последовательность 0-право-ян-... - вряд ли мы ему поверим), но как минимум один отдельно взятый результат, даже очень длинный (тысяча или миллион бросков) не дает нам больше оснований подозревать такую ложь. У нас нет больше подозрительных результатов. Если мы хотим смоделировать ситуацию, где монетка честная по определению, и нечестной быть просто не может, то "разнородный" эксперимент дает нам это сделать способом, который не подрывает нашу собственную интуицию.

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

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

3.

Нам все еще предстоит разобраться, почему "111111...." подвергает сомнению мета-вопрос, а какое-нибудь "1011010001..." не подвергает. Ясно ведь, что это не только "11111111...". Какое-нибудь "1010101010..." тоже заставит нас сомневаться в честности монетки (или человека), хотя единиц будет столько же, сколько нулей. Но эта закономерность их появления крайне подозрительна - почему, и как эту подозрительность точнее определить?

Можно попробовать ответить так. Поскольку мы понимаем теперь, что имеем дело с мета-вопросом (о честности монетки/человека), то альтернативной гипотезой будет "человек обманывает". Мы спрашиваем себя, как скорее всего поведет себя человек, который обманывает нас и на самом деле не бросал монетку. Может, он запустить алгоритм случайных чисел на компьютере и выдаст 1000 случайных цифр, вместо настоящей монетки? Это выглядит маловероятным. Скорее всего он скажет какую-то простую последовательность, которую легко объяснить на словах, например "одни единицы", или "1010101010...". Вряд ли он будет придумывать из головы 1000 случайно выглядящих цифр.

Поэтому, если последовательность цифр выглядит закономерной, как 111111... или 10101010..., это повышает нашу оценку гипотезы о том, что человек обманывает. А если она выглядит хаотичной, как 1011010001..., то мы не считаем из-за этого его обманщиком. Но что такое "закономерно" и "хаотично"? Можно ли это определить точно, а не на наскольких очевидных примерах? Тут нам может помочь так называемая "колмогоровская сложность", математический способ определить хаотичность-или-закономерность последовательности цифр или других символов. Последовательность можно считать закономерной, если ее колмогоровская сложность - примерно говоря, самый короткий по числу букв способ определить ее словами - мала. Например, "1000 цифр и все единицы" - это мало букв, "1 и 0 друг за другом 500 раз" это мало букв, а какую-то случайную последовательность 10101010... длиной 1000 цифр так просто не описать, поэтому она не закономерна, а хаотична, или "случайна". Но более подробный и точный разговор о колмогоровской сложности быстро уходит в чистую математику.

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

Comments:
Страница 1 из 4
<<[1] [2] [3] [4] >>
[User Picture]From: livelight
2019-10-10 06:20 pm
На самом деле, люди мысленно сравнивают по степени достоверности и вероятности не последовательность 0000000000 с последовательностью 0110100100, а исход "10 нулей из 10" с исходом "6 нулей из 10". Притом вероятность первого (для "правильной" монетки) составляет 1/210, а второго - C610.

Вывод: у каждого в голове зашиты ЗБЧ и ЦПТ, просто мало кто способен их сформулировать :)

Edited at 2019-10-10 18:21 (UTC)
(Ответить) (Thread)
[User Picture]From: avva
2019-10-10 06:22 pm
Если бы это было так, последовательность 1010101010 считалась бы всеми достоверной и вероятной не менее, чем 0110100100, а даже более.
(Ответить) (Parent) (Thread) (Развернуть)
From: definite
2019-10-10 06:23 pm
И после вот всего этого технари запрещают гуманитариям ковыряться в носу. :)
(Ответить) (Thread)
From: (Anonymous)
2019-10-11 03:13 am
Всё нормально у технарей, математики разобрались с этим ещё в 195х:
https://avva.livejournal.com/3232492.html?thread=144336620#t144336620

(Ответить) (Parent) (Thread)
[User Picture]From: prol_prolych
2019-10-10 06:55 pm
У монетки есть жёсткие 0,5 - вероятность одного из двух исходов.
И при попытке выкидывать последовательность монетка пытается удержаться в пределах этих 0,5 +- некоторое отклонение, которое уменьшается с каждым броском.
Поэтому вероятность выкинуть подряд миллион орлов категорически меньше, чем вероятность выкинуть последовательность с примерно одинаковым содержанием орлов и решек.
То есть вероятность выкинуть последовательность из полмиллиона орлов и полмиллиона решек идущих по очереди категорически выше >> чем вероятность выкинуть миллион орлов.

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

Edited at 2019-10-10 18:57 (UTC)
(Ответить) (Thread)
[User Picture]From: amigofriend
2019-10-10 07:47 pm
Здравствойте Вам опять. Спешу повториться.

"В общем, дабы поставить точку на этом разговоре, представьте себе следующий мысленный эксперимент: Вася сидит в комнате и бросает монету. Между бросками он засыпает на две минуты (ну, студент, готовился к зачёту всю нощь). За это время в комнату по очереди забегают и подбрасывают ТУ ЖЕ САМУЮ МОНЕТУ Петя, Антонио, Хорхе, Самир, Эбенезер, Франсуа, Ли Чань, Накамура-сан, чемпион Кении по бегу на короткие дистанции Йобес Чепчумба и ещё несколько чуваков, пожелавших остаться неизвестными." Но никто этого не видит. Считаете что действия Пети, Антонио, Хорхе, Самира, Эбенезера, Франсуа, Ли Чаня, Накамуры-сан, чемпиона Кении по бегу на короткие дистанции Йобеса Чепчумбы и ещё нескольких чуваков, пожелавших остаться неизвестными хоть как-то повлияют на вероятности результатов подбросов Васи?

Из предыдущего разговора на эту тему: в вероятностном смысле "подброс монеты" означает её подброс неважно кем плюс отмечание того что выпало. Поэтому если монеты подбрасывают Вася и Петя по очереди и мы каждый раз отмечаем что выпало - это равносильно тому что монету подбрасывает только Петя или только Вася. А если мы отмечаем только то что выбросил Вася, то тот факт что между бросками Васи бросает Петя не имеет ровным счётом никакого значения.

(То есть последнее утверждение просто равнозначно тому что кто-то бросает монетку миллион раз, и каждый второй раз выпадает орёл. И конечно вероятность такого гораздо выше любой фиксированной милионной последовательности.
P.S. Ах, у Вас там написано "полмиллиона"! Тогда не выше, а ровно такая же :) Это очень просто увидеть на случае 4х бросков. Вероятность что все 4 орлы - 1/16. Вероятность что каждый второй орёл - 1/4.
А для половины, 2x бросков - что дв орла подряд - тоже 1/4.)


Edited at 2019-10-10 22:09 (UTC)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: gul_kiev
2019-10-10 07:04 pm
Да, именно колмогоровская сложность. Слишком маленькая заставляет подозревать мошенничество.
Её нельзя точно вычислить, но можно оценить сверху. Для "0000..." и "01010101..." она единицы битов, а при честной монетке должна быть не меньше тысячи.

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

У разнородного эксперимента сложность самого кодирования перевешивает сложность последовательности. Но если есть закономерность в кодировании, опять появляется шанс распознать мошенничество.
(Ответить) (Thread)
[User Picture]From: sorcerer_
2019-10-11 11:01 am
Колмогоровская сложность у утверждения: "случайная последовательность из 0 и 1 миллион раз" какая?
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: warikap
2019-10-10 07:07 pm
Недоверие того же сорта,что и к круглым числам в статистике. Ровное,правильное - всегда кажется чем-то искусственным.
(Ответить) (Thread)
[User Picture]From: vishniakov
2019-10-10 09:37 pm
В статистике еще и закон Бенфорда есть. Для полного счастья. Чтобы совсем все запутать.
И я не удивлюсь, что люди его также интуитивно чувствуют.
(Ответить) (Parent) (Thread)
[User Picture]From: poor_sysadm
2019-10-10 07:14 pm
"Красивых" последовательностей мало. На 111... похожа только одна - 000...
А тех, которые представляют собой мешанину 0 и 1 - хоть каждая из них уникальна, но все они похожи на друг друга.
То есть варианты "выпала красивая последовательность" и "выпала какая-то мешанина цифр" не равновероятны. Поэтому первому и меньше доверия.
(Ответить) (Thread)
From: (Anonymous)
2019-10-10 07:38 pm
Отличить красивую последовательность от некрасивой не очень просто. Вот совершенно хаотическая последовательность нулей и единиц. Может быть, это роман В.Пелевина "Чапаев и Пустота", зашифрованный ключом "мойдядясамыхчестныхправил"? Это ныло бы красиво. Проверили, не работает? Тогда попробуем ключом "бытьилинебытьвотвчемвопрос". Тоже нет? "всесчастливыесемьисчастливыодинаково"? опять нет? Попробуем "каркнулворонникогда"? "каркнулворонникогды"? "каркнулворонникогде"? "4a3933a70828256f0e6c583d4b2ac5f9"? (этот последний ключ сгенерирован случайным образом, но он гораздо короче романа Пелевина).
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: special_linear
2019-10-10 07:23 pm
Первая мысль была про связь с колмогоровской сложностью — именно потому что последовательность "11111..." выглядит как такая, которую можно было бы загадать заранее (потому что ее описание короткое!).
А вообще вопрос о том, как связана колмогоровская сложность и восприятие вероятности, необычайно интересный. Вот, скажем, в последовательность "11111..." сложно поверить, но можно (монетка нечестная/сломалась/кидающий не понимает, что просто класть на стол и подбрасывать это не одно и то же...), а в последовательность "11111...00000..." уже как будто сложнее (что с этой монеткой в процессе приключилось?).
(Ответить) (Thread)
[User Picture]From: yyi
2019-10-10 07:26 pm
есть причина по которой Вы избегаете Колмогоровскую сложность? без нее не разобраться.
в частности, в Вашем подходе 1, если взять, к примеру, хаш (e.g., SHA-1, with padding of all 0s or the first padding that results in different first bit of the hash for the two values in the particular position), и если мы посмотрим на последовательность первых битов хашей элементов последовательности (скажем "0-лево-инь-реализм-брюки-никон..."). и если это будет тот же 11111... то мы так же заподозрим неладное.
(и так для любой функции чья Колмогоровская сложность будет значительно ниже сложности данной последовательности.)
(Ответить) (Thread)
[User Picture]From: newkos
2019-10-10 07:47 pm

Природа монетки не бросает

Природа монетки не бросает
но она создала разум и руки
и этому разуму больше нечем заняться
вот и бросает монетки
и не понимает зачем ему это

а какая вероятность случайного появления разума
для размышления о случайности
и ведь, если природа скажет, бл.... займись делом
разум скажет, а нафига мне это дело
(Ответить) (Thread)
From: neveling
2019-10-10 08:06 pm
Варианты подобные 1010101010, или 000000000, или например олень 10 раз приходил в одно место, очень важны для нас, тк могут иметь скрытые выгоды. Редкие события = вероятная польза. Но алгоритм у среднего человека довольно прост- длина шаблона, как ранее отметили. Из-за этого и ошибки алгоритмически тупые встречаются, редкое = чудо
(Ответить) (Thread)
[User Picture]From: irrelative
2019-10-10 08:14 pm

- Наше сознание настроено на поиск закономерностей (паттернов),
- Случайность и закономерность - антонимы, поэтому последовательность, в которой просматривается паттерн узнается как неслучайная.
- Чем очевиднее закономерность, тем больше подозрений она вызывает, поэтому 11111111 или 10101010 вызовут вопросы у каждого, а ваш пример с простыми числами - только у очень немногих.

(Ответить) (Thread)
[User Picture]From: irrelative
2019-10-10 08:16 pm

Ну и да, забыл: у закономерности всегда есть причина, будь то "закон природы" или обыкновенное жульничество.

(Ответить) (Parent) (Thread)
[User Picture]From: m_gurlukovich
2019-10-10 08:16 pm
Я скорее всего не прав, но в понятии "честная монетка" есть какое-то внутреннее противоречие.
То есть.
У каждого выпавшего варианта 1 или 0 есть множество объективных причин, включая плотность воздуха, неровность поверхности и т.д.
Если монетка бросается человеческой рукой, с разным усилием и точкой приложения, то очевидно, что совокупность всех причин приведет к визуально хаотичныму общему результату – у каждого выпавшего варианта будет свой, отличный от других, набор причин.
Если монетку будет однообразно выбрасывать робот в вакууме, то результат, очевидно, должен быть вида 111111.
Монетка в обоих случая, пользуясь терминологией, "нечестная" – но в обоих случаях по-своему. В одном мы знаем, почему так получилось, в другом не знаем – но в обоих случаях дело не в вероятности, а в совокупности причин.
(Ответить) (Thread)
[User Picture]From: oude_rus
2019-10-11 06:21 am
Хехе, очень верное замечание.
Было бы забавно построить такого робота, надо в Бостон Дайнамикс написать.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: danechka
2019-10-10 08:40 pm
Как то длинно получилось... у меня вот версия по короче:
Красивых вариантов несравненно меньше чем некрасивых.
Поэтому и верится с трудом что кому-то попался именно красивый вариант.
(Ответить) (Thread)
From: alexreinard
2019-10-10 09:00 pm
первый комент - лучший!

но для слепых и тупых можно и разжевать!

для двух подбрасываний монеты возможны четыре равновероятных исхода
1)00
2)01
3)10
4)11

для трех
000
001
010
100
011
110
101
111

что, и теперь ничего не видно?

чел, для миллиона подбрасываний вариант миллион орлов ОДИН. а всего вариантов 2 в степени 10000000. То есть херова туча. И в этой херовой туче, "серединных" вариантов (где частота орлов приблизительно равна частоте решек) число НЕМНОГО меньше этой херовой тучи. Почему так - показал выше.
Но еще раз - первый комент абсолютно достаточен.

(Ответить) (Thread)
[User Picture]From: iigogosha
2019-10-10 10:25 pm
спасибо добрый человек. объяснили мне гуманитарию понятно. из того что в посте - ничего не понял.
(Ответить) (Parent) (Thread)
[User Picture]From: ny_quant
2019-10-10 09:15 pm
А мне недавно банк прислал одноразовый пароль 966666.

Любители комбинаторики могут посчитать время ожидания такого события (пять одинаковых цифр подряд в шестициферной случайной последовательности), сопоставить результат с тем фактом, что я использовал этот сервис в общей сложности меньше 1000 раз и сделать какие-нибудь нетривиальные выводы.
(Ответить) (Thread)
[User Picture]From: vishniakov
2019-10-10 09:35 pm
Вы будете смеятся, но существует специальный алгоритм генерации легко запоминаемых буквенных паролей (они абсолютно бессмыслены, но "легко читаются" по правилам английского языка, при этом их стойкость хотя и меньше, чем у чисто случайного набора букв, но тоже весьма неплоха).

Почти каждый раз, как я получаю пароль от банка, у меня возникает ощущение, что задолбавшись восстанавливать пароли банки соорудили что-то типа алгоритма генерации легкозапоминаемых цифровых паролей (особено ржачно было, когда в качестве восстановления забытого пароля был прислан пароль две одинаковые цифры - две одинаковые цифры. Ну типа подавись ты, склеротик :-) ).
(Ответить) (Parent) (Thread)
Страница 1 из 4
<<[1] [2] [3] [4] >>