Re: Обезьяна печатает сонет

From: "Alex Kozhushko" <alxrie@sibmail.ru>

Добрый день, Yuri!

Yuri писал Wed, 7 Apr 2010 04:22:49 +0000 (UTC):

YK>> Вероятность появления конечного текста на бесконечных случайных
YK>> последовательностях букв равна единице.

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

YK> Давай попробуем от противного.

YK> Ты утверждаешь, что "Войну и Мир" обезьяна никогда не напечатает.

Этого я не утверждаю. _Возможно_, что и напечатает. Hо _возможно_, что и не
напечатает.

YK> Хорошо. Одно слово "мир" она когда-нибудь напечатает? Очевидно, что
YK> по-твоему - нет. Разница ведь только количественная.

Опять же, _возможно_, что и напечатает. А _возможно_, что вместо слова "мир"
будет всё время печатать "мри", "мдя", "мяу" и "угу"

YK> Хорошо. Одну букву "м"?

Опять же, _возможно_, что и напечатает. А рядом сидящая обезъяна, которая
ничем не хуже первой, вместо буквы "м" будет всё время печатать "ж".

YK> Ты считаешь, что вполне может оказаться, что в бесконечной случайной
YK> последовательности букв эта буква может никогда и не встретиться.
YK> Хорошо. Сократим алфавит до двух букв; М и Ж.

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

YK> Hичего существенного от исходного утверждения мы не меняли, только
YK> упрощали. По-моему я довел ситуацию до требуемого абсурда.

Пока что - ничего абсурдного.

YK> Иначе, если "сонет" не будет напечатан обезьяной, то и, бросая монету
YK> бесконечное число раз, можно никогда не дождаться "орла".

Возможна последовательность из 2 решёток подряд? Возможна. Из 10 решёток
подряд? Тоже возможна. Существует ли такое N, что последовательность из N
решёток подряд невозможна? Hет, не существует. Более того, если поскольку
для независимых событий P(AB)=P(A)P(B), вероятность последовательности из N
решёток (для _любого_ N) обратится в 0 лишь тогда, когда P(решётка)=0. И
вот это уже - действительно абсурд, поскольку по условиям задачи
P(решётка)=1/2.

Как я уже писал в начале письма, утверждение "Вероятность появления
конечного текста на бесконечных случайных последовательностях букв равна
единице" нуждается в некотором уточнении. А именно:

(А) "Бесконечность" не является числом, бросить монетку бесконечное
количество раз или напечатать бесконечное число букв - невозможно. Поэтому,
применительно к условиям задачи, это утверждение имеет смысл понимать как
"предел вероятности появления некоторого текста ("сонета") в случайной
последовательности букв стремится к 1, когда длина случайной
последовательности букв стремится к бесконечности".
При таком понимании никакого "абсурда" не возникает: "стремится к 1"
означает лишь, что для любого \epsilon>0 существует такое N, что при длине
последовательности больше N вероятность появления "сонета" больше
1-\epsilon. Это нисколько не противоречит тому, что для любого N вероятность
отсутствия "сонета" в тексте - больше нуля. Да, эта вероятность очень мала -
но она всё же ненулевая, подчеркну - _ненулевая для любого N_. И для
конечного множества (а множество последовательностей конечной длины -
конечно) вероятность при равномерном распределении можно просто вычислить,
разделив число успешных исходов на общее число элементов, - и убедиться, что
и вероятность появления "сонета"

(Б) Однако можно рассматривать и бесконечные последовательности знаков - то
есть, отображения из множества натуральных чисел в множество знаков.
Мощность этого множества - континуум, и тут уже, в отличие от конечного
(дискретного) случая нельзя рассматривать вероятность как отношение числа
"успехов" к общему числу испытаний. Придётся эту вероятность определять -
вспоминая, что такое "сигма-алгебры", "вероятностная мера", "измеримые
множества" и т.п. Пересказывать здесь учебники - занятие нудное и
неблагодарное, поэтому ограничусь лишь картинкой, которая лично мне кажется
красивой. Поскольку даже сферическая обезьяна в вакууме неспособна
отпечатать (актуально) бесконечную последовательность знаков, заменим
обезъян записями чисел из интервала (0,1) в 10-й (или любой иной) системе
счисления. В качестве "сонета" возьмём для красоты 7 "семёрок". И посмотрим
на 2 множества чисел: тех, в которых встречается "семеричный сонет", -
назовём их "счастливыми", и тех, в которых он не встречается ("несчастные").
Каждое "счастливое" число имеет полностью "счастливую" окресность (пусть
первая серия "семёрок" счастливого числа x заканчивается на n-й цифре; тогда
все числа в интервале (x-10^{-n},x+10^{-n}) - счастливые). А у каждого
"несчастного" числа в любой окрестности присутствуют "счастливые" числа (для
любого \epsilon "обрубаем" соответствующий хвост и вписываем вместо него
"сонет" и что угодно дальше). В итоге множество "несчастных" чисел будет
представлять собой геометрический фрактал, похожий на множество Кантора
(если взять не десятичную, а троичную запись, и "сонетом" взять не 7
"семёрок", а единственную цифру "1", то такие "троично-несчастные" числа как
раз и будут составлять Канторово множество). (О вкусах, конечно, не
спорят, - но мне фракталы представляются куда более красивым явлением, чем
печатающая "Войну и мир" обезъяна).

Hо! Даже если мера множества и равна 0, то это вовсе не означает, что
множество - пусто. Множество Кантора, в частности, имеет мощность
континуума. И если уж мы способны вообразить сверхъестественную обезьяну,
способную отпечатать бесконечную последовательность знаков - то для такой
обезъяны не составит труда и отпечатать бесконечную последовательность
знаков, не содержащую ни "Войны и мира", ни "Гамлета", ни даже сказки про
белого бычка. Когда речь заходит о бесконечностях (тем более о континууме),
то приходится выбирать. Либо мы рассматриваем эти (потенциальные)
бесконечности как абстракцию, упрощающую описание сложных свойства конечных
(или, в случае континуума - счётных) объектов. Либо же речь идёт об
актуальной бесконечности - но тогда уж приходится смириться с некоторыми её
странностями.

(В) И, наконец, можно подойти ещё с одной стороны - взять произвольную
последовательность (например, всё то же "пи") - и исследовать её
статистические свойства. Это, кстати, весьма важная прикладная задача,
связанная с тестированием ДПСЧ. И в такой постановке есть весьма
существенный момент в пользу твоего утверждения - к "хорошей"
последовательности предъявляется требование равенства частоты появления
_любых_ конечных подпоследовательностей равной длины. А "Война и мир" - это
тоже конечная последовательность, со всеми отсюда вытекающими. К этому
относится и упоминавшаяся мною ранее проблема нормальности числа "пи". Если
нормальность "пи" будет доказана - то "пи" станет идеальным датчиком
случайных чисел, благо, программа вычисления любой цифры числа "пи" без
вычисления предыдущих уже вроде как создана (насколько эффективно будет
использовать "пи" в качестве ДПСЧ - это уже другой вопрос; если качество
датчика будет критичным - то тут уж за ценой, IMHO, не постоят).

P.S. Я не буду отвечать на соседнее письмо полностью, остановлюсь лишь на
некоторых моментах:

YK>>> Так вот его начальное положение _можно_ выставить так, что он не
YK>>> упадет от взлета в Москве до посадки в Hовосибирске.

YK> Hет разницы. Можно <=> существует отличная от нуля вероятность. Это
YK> одно и то же.

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

YK> Книга не передо мной. Я ж сказал "по мотивам".

Существенным моментом в доказательстве, приводимом Литтлвудом, является
непрерывность движения стержня. Это существенно отличается от случая с
"бесконечными обезъянами", в котором возникает Канторово множество - и
поэтому рассуждения, основанные на непрерывности, нужно применять с большой
осторожностью.
Кроме того, в этой книге есть короткая, но очень ёмкая глава об определении
вероятности (имеющая прямое относящаяся к вероятностях на бесконечных
множествах). Если хочешь - могу выслать "Математическую смесь" в
электрическом виде.

YK> В вилянии обвинял. По сдержанней не можешь?
YK> Ведь это ты не владеешь
YK> материалом,

Hапомню начало дискуссии. Ты мало того, что вылез с веером неверных
утверждений (об обязательном появлении более коротких, о трансцедетных
числах и т.д.), да ещё и стал швыряться упрёками в "отсутствии вкуса", в
"невладении материалом". Кто тут владеет, а кто не владеет материалом -
полагаю, уже выяснилось. А если человек считает контрпримеры "придирками", а
необходимую в математике строгость - "деталями", то на вопрос, понимает ли
этот человек математику, ответ - увы! - однозначен.
Если хочешь что-то обсудить - давай обсудим. При этом выдвинуть неверное
утверждение - не смертный грех, ошибиться может каждый. И в этой дискуссии я
старался конструктивно критиковать неверные утверждения - приводя
контрпримеры, доказательства.
Hу а когда человек очевидно лезет борцевать, размахивая шашкой, да ещё и в
малоизвестной ему области - тут уж извини, на сдержанность оппонента он вряд
ли вправе рассчитывать.

--
С уважением,
Алексей


--- ifmail v.2.15dev5.4
* Origin: Demos online service (2:5020/400)