Математические байки

Теперь понятно, почему бесконечное слово называют "словом Фибоначчи": последовательность слов, которая к нему приводит, получается как раз из Фибоначчи-подобного соотношения. Но давайте продолжим нашу деятельность по счёту букв. А именно, давайте посмотрим, сколько букв А и Б оказывается среди первых k букв слова Фибоначчи — и отметим соответствующую точку на плоскости (по оси абсцисс отложив буквы А, а по оси ординат буквы Б). Получится этакая "змейка": при добавлении одной буквы мы сдвинемся на расстояние 1.

Невооружённым глазом видно, что остаётся то слово, что было до того. То есть w_{n+1} = w_n w_{n-1}. И когда это написано, доказательство тоже мгновенно проводится по индукции, из базы либо АБА= АБ А, либо даже АБ= А Б с формальным добавлением w_0=Б.

Сразу видны числа Фибоначчи; а как бы это доказать? Мы знаем, что следующее слово продолжает предыдущее, не получится ли что-то увидеть из этого? Давайте посмотрим, что остаётся, если из нового слова убрать идущее перед ним:

Сколько букв в словах w_1, w_2, w_3,...? Посчитав, видимо знакомую нам последовательность 1, 2, 3, 5, 8, ... А сколько по отдельности букв А и Б?

Но это будет итоговая "светлая цель", к которой мы дойдём, а пока давайте начнём с совсем простого: посчитаем буквы. (Почему? Да просто потому, что если вдруг есть непонятный объект, так давайте его измерим, насколько получится, вдруг что интересное найдём.)

Оказывается, очень много — а пройдя по этой дороге чуть-чуть дальше, можно получить вот такую красивую картинку, фрактал Рози (picture credit: А. Я. Канель-Белов, И. В. Митрофанов):

Вот первые несколько образов: w_1=А w_2=АБ w_3=АБА w_4=АБААБ w_5=АБААБАБА Явно видно, что следующее слово продолжает предыдущее — что мгновенно доказывается по индукции. Значит, есть одно бесконечное слово, у которого все эти слова являются началами. Это слово w = АБААБАБААБААБАБААБАБА... называется словом Фибоначчи. А что о нём можно сказать?

Запоздалое — с Новым Годом! Сегодняшняя байка — рассказ о подстановочных словах. Давайте зададим вот такое отображение F на словах из букв А и Б: заменим одновременно каждую букву А на слово АБ, а каждую букву Б на А. Например, F(БАА)=ААБАБ. И будем это отображение итерировать, начав с однобуквенного слова w_1=А: рассмотрим последовательность его образов w_n=F(w_{n-1}). Что у нас получится?

Ну и на этом я на сегодня прекращаю дозволенные речи.

Ну и наконец — отсюда же видно, что условия "разориться" и "когда-нибудь достигнуть $(n-1)" имеют на первый шаг (и вообще на все шаги до достижения $(n-1)) одинаковый эффект: потому что всё, что будет, начиная с $(n-1), от того, что было до, не зависит.

На самом деле это один и тот же вопрос, и на него есть разумный ответ. А именно — с одной стороны, чтобы разориться, Алисе нужно в какой-то момент иметь на руках $(n-1). С другой, после того, как Алиса эту сумму получила, её игра не зависит от того, что было раньше — так что r_n = (вероятность от $n когда-нибудь достигнуть $n-1) * r_{n-1}. И если обозначить эту вероятность "отступить на доллар" через x, то вот мы и получаем геометрическую прогрессию.

И это хорошее место, чтобы чуть-чуть задуматься, "а почему". А есть ли хорошее объяснение, что вероятность разорения оказалась именно геометрической прогрессией? (Так-то мы сослались на рекуррентные уравнения, формально говоря, задействовав линейную алгебру... а проще можно?) И ещё — если Алиса начинает с $n, то процесс её игры при условии достижения $0 (разорения) будет таким же, как и при условии достижения любого фиксированного уровня $k с k

И поэтому эти вероятности равны p*(q/p)=q и q*(p/q)=p соответственно — то есть игра Алисы _при условии разорения_ стала игрой Боба!

Но у нас геометрическая прогрессия — поэтому r_{n+1}/r_n=x=q/p, а r_{n-1}/r_n=p/q.

Осталось понять, как при условии "Алиса разорилась" выглядит процесс её игры. Если в какой-то момент у неё n долларов, то шансы перейти в (n+1) и в (n-1) за один шаг равны соответственно p*r_{n+1}/r_n и q*r_{n-1}/r_n (а то, что их сумма равна 1 — это и было наше уравнение).

Но раз r_n=a*1+b*x^n, то a=0, а из r_0=1 тогда следует b=1. Так что вероятность разорения Алисы — это просто геометрическая прогрессия: r_n=x^n=(q/p)^n.