===
Вторая байка — про теорию вероятностей. Вот тут — https://avva.livejournal.com/3242116.html , https://blog.tanyakhovanova.com/2019/11/my-new-favorite-probability-puzzle/ — обсуждается такая задача. Пусть два игрока, Алиса и Боб, одновременно и независимо играют на деньги с одинаковой начальной суммой в $100, каждую минуту ставя по доллару. Но у Алисы вероятность выигрыша 51%, а у Боба 49%. Известно, что в итоге оба разорились (остались без денег и прекратили игру); _при этом условии_ про кого более вероятно, что он разорился первым?

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

Ответ — равновероятно. Более того, оказывается, что процесс игры Алисы _при условии_ того, что она в конце концов разоряется, такой же, как процесс игры Боба. И это, мне кажется, удивительно!

Давайте посмотрим, как этот процесс устроен. Для начала найдём вероятности r_n того, что Алиса разоряется, имея в начале n долларов.

r_0=1 (ибо тут уже всё).
Достаточно естественно (хотя это и надо доказывать — но мы в это поверим), что r_n<1 при всех n>0: шанс не разориться (а получить асимптотически-линейный рост) у Алисы есть, если у неё ещё осталось, на что играть.

Теперь, если Алиса начинает играть с n долларами, её шанс разориться складывается из вероятности выиграть первую ставку и разориться после того, и проиграть и разориться после того:
r_n = p r_{n+1} + q r_{n-1},
где p=0.51 — её вероятность выигрыша.

Это — линейное рекуррентное соотношение, и его решениями оказываются линейные комбинации геометрических прогрессий со знаменателями — корнями характеристического уравнения*; в данном случае — это уравнение px^2-x+q=0.

*) когда кратных корней нет; иначе там (в общей науке линейных рекуррентных соотношений) появляются "квазимногочлены" — произведения многочленов на экспоненты.

Один корень у этого уравнения — 1, отвечающего решению-константе. Собственно, если бы p было меньше 1/2 (а мы ещё нигде p>1/2 не использовали), то мы этот корень и должны увидеть: вероятность разорения в этом случае — тождественная единица.

А второй (например, из теоремы Виета, чтобы долго не считать) x=q/p.

Кстати, в качестве ответвления: случай честной монеты, p=q=1/2, это как раз случай кратного корня, и решения уравнения r_{n+1}-2r_n+r_{n-1}=0 это в точности все арифметические прогрессии. Но поскольку r_n это вероятности, такая арифметическая прогрессия остаётся на [0,1] при всех n>0, а ограниченная арифметическая прогрессия — константа. Значит, r_n=1 — игрок с честной монетой тоже разоряется с вероятностью 1 ("случайное блуждание на прямой возвратно"), и такое рассуждение — один из способов это увидеть.

В нашем случае p>1/2 — не очень сложно поверить, что r_n будет стремиться к 0 с ростом n: чем больше у Алисы начальный запас денег, тем меньше её шанс разориться.

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

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

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

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

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

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

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

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

Запоздалое — с Новым Годом!

Сегодняшняя байка — рассказ о подстановочных словах.
Давайте зададим вот такое отображение F на словах из букв А и Б: заменим одновременно каждую букву А на слово АБ, а каждую букву Б на А.
Например, F(БАА)=ААБАБ.

И будем это отображение итерировать, начав с однобуквенного слова w_1=А: рассмотрим последовательность его образов w_n=F(w_{n-1}).
Что у нас получится?

Вот первые несколько образов:
w_1=А
w_2=АБ
w_3=АБА
w_4=АБААБ
w_5=АБААБАБА

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

Это слово
w = АБААБАБААБААБАБААБАБА...
называется словом Фибоначчи.
А что о нём можно сказать?

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