Как стать автором
Поиск
Написать публикацию
Обновить

Применимы ли индуктивные рассуждения к предсказанию символов в неслучайных последовательностях?

Время на прочтение51 мин
Количество просмотров4.7K
Алгоритмы*Занимательные задачкиМатематика*Машинное обучение*
image
(Этот кашалот парит в воздухе целых 5 минут и поэтому решил, что его полет будет продолжаться вечно. рисунок: Tim Zarechny)

Философский вопрос с прикладными последствиями

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

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

Должно ли это наблюдение заставить вас в будущем в качестве прогноза чаще называть «единицу»?

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

Комфортное чтение статьи займет у Вас вечер или два, в процессе придется кое-что
вспомнить из университетской математикой 1-го года обучения. По всем непонятным вопросам Вы можете писать мне на почту или в комментарии.

Адаптация к случайным последовательностям


Случай, когда вероятность известна

Это исследование будет проще понять, если начать с задачи предсказания последовательностей, символы которых генерируются случайно. Пусть, имеется урна и вам известно, что в ней находятся $N$ одинаковых на ощупь шаров, причем $Np$ из них черные, а оставшиеся $Nq = N(1-p)$ — белые. Пусть некто раз за разом повторяет такую процедуру: он достает из урны случайный шар, а затем печатает на ленте еще один символ. Если шар черный, то печатается «ноль», а если белый, то — «единица». После того, как символ напечатан, шар возвращается в урну. На все эти действия вы можете смотреть как на некую игру, состоящую из множества повторяющихся туров. Пусть ваша цель в игре — суметь как можно большее число раз угадать, какой появится на ленте следующим. Почти очевидно, что в описанных условиях наилучшей для вас стратегией будет все время называть одну и туже цифру: а именно ту, которая соответствует цвету большинства шаров в урне.

Действительно, угадать следующий символ на ленте $"="$ угадать цвет следующего шара. Математическое ожидание числа правильных предсказаний цвета за всю игру будет равно сумме математических ожиданий числа правильных предсказаний в каждом ее отдельном туре. Все туры проходят независимо друг от друга. Если перед тем, как будет вынут очередной шар, вы назовете «ноль», то по сути предскажите «черный» и математическое ожидание числа правильных предсказаний в этом туре окажется равным $1\cdot p+0\cdot q=p$, если отдадите предпочтение «единице», то ожидаемое число правильных предсказаний будет равно $0\cdot p+1\cdot q=q$. Таким образом, когда $p>q$, «выгоднее» голосовать за «ноль», а когда $q>p$, то — за «единицу».

При описанном только что алгоритме поведения математическое ожидание числа правильно предсказанных за всю игру символов будет равно $N\cdot max(p,q) = N\cdot(1/2 + \Delta)$, где $\Delta=|p - 1/2|=|q - 1/2|=|p - q|/2$ выражает собой дисбаланс вероятности появления «нуля» и «единицы».

Обобщение на случай с неизвестной вероятностью

Пусть снова вы имеете дело с той же самой игрой, но теперь информация о том, каково число черных и белых шаров в урне держится от вас в секрете. Как и в прошлый раз нас будет интересовать вопрос: «Какова средняя доля шаров, окраску которых можно предугадать, если действовать оптимально?»

Перво-наперво здесь нужно сказать об одной крайне простой, но замечательной стратегии (я назову ее $S_{Coin}$), позволяющей «в среднем» угадывать ровно половину символов вообще в любой бинарной последовательности, не важно: случайной, или нет. По правилам $S_{Coin}$ перед тем как сделать очередной прогноз вы должны бросить монетку и, если выпала решка, предсказать «единицу», а если орел — то «ноль». Если действовать таким образом, то математическое ожидание числа угаданных символов будет ровно $1/2\cdot N$ вне зависимости от того, какая именно последовательность окажется в итоге напечатанной на ленте.

Хорошо, предсказывать $1/2$ всех символов мы способны с помощью $S_{Coin}$, а можно ли предсказывать больше?
Если бы мы знали наперед, какое из неравенств верно: $p>q$, или $q>p$, то с легкостью воспользовались бы результатами предыдущей задачи и угадали бы $1/2$ плюс $\Delta$ от всех символов, однако по условию мы не можем получить такую информацию извне. С другой стороны, если в игре уже минуло какое-то количество туров, то соотношении между $p$ и $q$ можно попробовать оценить из наблюдений. Понятно, что при $p>q$ среди первых $k$ напечатанных символов с большей вероятностью будут преобладать «нули», а при $q>p$ — с большей вероятностью будут преобладать «единицы».

Пожалуй, самую простую стратегию, основанную на статистической оценке $p$ и $q$, можно описать следующим планом действий:
в первом туре с помощью монетки выбрать случайный символ,
в начале каждого следующего тура сосчитать, сколько раз среди уже напечатанных символов встречается «единица», сколько раз встречается «ноль», и в качестве прогноза назвать тот символ, который на момент наблюдений встречается чаще.
Если вдруг «ноль» и единица" в минувших турах успели появится одинаковое число раз, то в качестве прогноза следует назвать тот же символ, что предсказывался в предыдущем туре. По причинам, которые станут очевидными позже, мы будем называть эту стратегию $S_{Hard}$.

Насколько эффективна $S_{Hard}$ по сравнению с другими возможными стратегиями, насколько математическое ожидание доли правильно предсказанных ею символов больше $1/2\cdot N$? Чуть позже мы дадим на эти эти вопросы исчерпывающий ответ, а сейчас ограничимся поверхностными оценками.

Сперва отметим, что для любой стратегии, действующей в условиях, когда $p$ и $q$ неизвестны, математическое ожидание количества правильно предсказанных ею символов не может превзойти результата лучшей стратегии для ситуации с известными $p$ и $q$ (дополнительная информация никогда не бывает лишней). Лучшая из стратегий последнего типа была найдена нами выше и ее результат: $N\cdot(1/2 + \Delta)$, откуда мы получаем верхнюю оценка для $S_{Hard}$.

Итак, эффективность применения $S_{Hard}$ заключена где-то между $1/2$ и $1/2 + \Delta$, и в действительности возможны случаи, когда достигается каждая из границ. Например, если последовательность состоит ровно из одного элемента, то согласно правилам $S_{Hard}$, шансы угадать этот элемент составят ровно $1/2$ (прогноз определяется с помощью монетки). С другой стороны, когда $p$ не равно $q$ и при этом в последовательности уже напечатано $k$ элементов, вероятность того, что в этот момент или когда-либо позже количество вхождений в нее менее вероятного символа превысит число вхождений более вероятного, с ростом $k$ очень быстро стремиться к нулю (см. несимметричное броуновское движение). Таким образом, если случайная последовательность достаточно длинная, то только для относительно небольшой доли ее элементов в качестве прогноза $S_{Hard}$ выдаст менее вероятный символ, а значит эффективность $S_{Hard}$ в такой ситуации окажется близкой к $1/2 + \Delta$. Кстати, последнее свойство $S_{Hard}$ позволяет нам говорить о ней как об асимптотически оптимальной стратегии угадывания вероятностных последовательностей.


Адаптация к не(обязательно)случайным последовательностям. Поверхностный анализ


Неочевидность подхода

Давайте подумаем, почему адаптивные стратегии угадывания символов сработали на случайных последовательностях?

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

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

Разумеется для отгадывания неслучайных последовательностей по прежнему работает «трюк с монеткой»: делая предсказания «нуля» на «орел» и «единицы» на «решку», вы гарантируете себе математическое ожидание величиною в $N/2$ угаданных символов. Можно ли угадать больше?

Частотный дисбаланс

По отношению к неслучайным последовательностям тоже можно ввести понятие дисбаланса, но только не вероятностного, а частотного. Если некоторая последовательность состоит из $N$ символов: $PN$ «нулей» и $QN$ «единиц», то по определению ее частотный дисбаланс $\delta$ есть $|P-Q|/2$. Новое определение дисбаланса в некотором смысле даже «обратно совместимо» со старым, так как для длинных случайных последовательностей с большой вероятностью $P\approx p$, $Q\approx q$, а значит $\delta\approx\Delta$.

Как вы уже знаете, наличие дисбаланса между вероятностями появления «нуля» и «единицы» в случайной последовательности позволяет правильно угадать в среднем больше половины ее элементов. Раз мы ввели понятие частотного дисбаланса, то совершенно естественно теперь задать вопрос:
«Позволяет ли наличие частотного дисбаланса угадать в среднем больше половины элементов в неизвестной, но не обязательно случайной последовательности, если к тому же заранее не известно, каких символов в ней больше: „нулей“ или „единиц“?»

Насколько хороша $S_{Hard}$?

Поиски ответа мы начнем с того, что попробуем испытать уже использовавшуюся нами раннее стратегию $S_{Hard}$. Эта стратегия неплохо себя показала на случайных последовательностях и даже оказалась на них асимптотически оптимальной.

Итак, предположим, что на ленте печатается длинная последовательность ноликов и единичек с частотным дисбалансом $\delta=|P-Q|/2$.

Как много ее элементов удастся предугадать с помощью $S_{Hard}$?

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

image

рис 1.

В первом примере $P>Q$ и все $NP$ «нулей» последовательности стоят строго перед ее $NQ$ «единицами» (рис1). Для такой последовательности $S_{Hard}$ правильно предскажет все «нули», кроме быть может первого (вероятность предсказать правильно первый «ноль» равна 50%-там), и даст ошибочный прогноз для каждой «единицы». Таким образом, математическое ожидание доли правильно предсказанных символов составит $P - 1/(2N) = 1/2 + \delta - 1/(2N)\approx 1/2 + \delta$.

Что ж, это весьма неплохой результат. Я предлагаю вам самостоятельно проверьте, что ровно с таким же результатом $S_{Hard}$ угадает и «перевернутую» последовательность, у которой $NQ<NP$ «единиц» стоят в начале, а $NP$ «нулей» — за «единицами» в конце.

image

рис 2.

Рассмотрим теперь куда более интересный пример «парно-пульсирующей» последовательности (рис 2). Первый ее элемент — «единица», далее следует «пульсирующий» отрезок, на котором $NP$ нулей парами чередуются с $NQ$ единицами, а вслед за ним — «гомогенный» отрезок, стоящий из идущих друг за дружкой $N(Q-P)-1$ единиц. Давайте проследим, какие прогнозы для элементов этой последовательности будет делать $S_{Hard}$.

  • Первый прогноз будет не то нулем, не то единицей — в общем, он нам не особо интересен.
  • Далее $S_{Hard}$ наблюдает, что единственный напечатанный символ — это «единица», следовательно прогноз второго элемента — это «единица», тем самым $S_{Hard}$ ошибется в своем втором предсказании.
  • Смотрим на третий прогноз: в этот момент на ленте напечатаны один «ноль» и одна «единица» — между числом употребления двух символов наблюдается паритет, а значит $S_{Hard}$ должна повторить свой предыдущий прогноз, то есть назвать «единицу» и ошибиться еще раз.
  • На момент четвертого прогноза уже больше напечатано «нулей», поэтому $S_{Hard}$ предскажет «ноль» и снова ошибется.

Легко видеть, что кроме быть может только первого элемента, все предсказания $S_{Hard}$ на «пульсирующем» участке будут ошибочными. К моменту, когда этот участок закончится, на ленте будет напечатано $NP$ «нулей» и $NP+1$ «единица», поэтому оставшиеся $N(Q - P)-1$ единицу $S_{Hard}$ предскажет правильно. Объединяя эти факты вместе, мы находим, что доля символов последовательности, которые угадает $S_{Hard}$, будет равна $1/(2N)+Q-P-(1/N) \approx Q - P = 2\delta$

Конечно, когда дисбаланс парно-пульсирующей последовательности близок к $1/2$ (то есть, когда ее «гомогенный» участок занимает почти всю ее длину), $2\delta$ близко к единице и предсказания $S_{Hard}$ работают просто великолепно. Однако в случае, когда дисбаланс подобных последовательностей близок к нулю, результаты предсказаний $S_{Hard}$ оказывается даже хуже, чем у стратегии с монеткой. Более того, если вся последовательность состоит из попарно чередующихся «нулей» и «единиц», то $S_{Hard}$ вообще не угадывает ни одного символа, за исключением быть может первого.

Итак, на неслучайных последовательностях $S_{Hard}$ способна работать очень плохо, настолько плохо, что возможны ситуации, когда математическое ожидание доли правильно угаданных символов будет практически равно нулю. Приведенный выше пример с пульсирующей последовательностью во многом объясняет, почему так может происходить.

Все дело в том, что $S_{Hard}$ слишком резко реагирует на любые изменения частот напечатанных на ленте символов, когда эти частоты колеблются вокруг $1/2$. Чрезмерная реакция на изменения позволила нам с помощью специального вида последовательности манипулировать предсказаниями $S_{Hard}$ и в конце концов легко ее «обмануть». Можно ли как-то исправить $S_{Hard}$, сделав эту стратегию более устойчивой к манипуляциям и «обману»?


Суперпозиция предположений

Когда среди напечатанных символов вы наблюдаете одни «единицы», совершенно «логично» предположить, что следующий символ тоже должен быть «единицей», когда на ленте сплошь одни «нули» — «нулем». Однако как подсказывает нам неудача со стратегией $S_{Hard}$, если и тех, и других символов обоюдно много, то что в качестве предсказания стоило бы выбрать что-то «посередине». Но как это сделать, ведь по условию наше предсказание обязательно быть чем-то одним: либо нулем, либо единицей?

Эта задача похожа на выбор смешанной стратегии в теории игр и решается она следующим образом: для заданных весов $\alpha$ и $\beta=(1-\alpha)$ нужно поставить любой случайный эксперимент, о котором известно, что он завершается событием $A$ с вероятностью $\alpha$ и противоположным событием $B$ с вероятностью $\beta$. Если в результате произошло событие $A$, то в качестве предсказания выбирается «ноль», а если $B$ — то «единица». Я не владею квантовой механикой, но предполагаю, что физики назвали бы такое предсказание взвешенной суперпозицией «нуля» с весом $\alpha$ и «единицы» с весом $\beta$.

Суперпозиция предсказаний на самом деле уже использовалась нами в стратегии $S_{Coin}$: там «ноль» и «единица» входили в суперпозицию с весами равными $1/2$. Более того, даже на детерминистические предсказания стратегии $S_{Hard}$ можно смотреть как на взвешенные. В такой интерпретации каждый из двух возможных символов $S_{Hard}$ предсказывает с вероятностью ноль, когда его частота в уже напечатанной части последовательности меньше $1/2$ и с вероятностью единица, когда эта частота превышает $1/2$.
image

рис 3

Если вероятностный вес символа в предсказаниях, даваемых $S_{Hard}$, рассматривать как функцию его наблюдаемой частоты, то эта функция будет изменяется не непрерывно. Как видно из рисунка 3, она испытывает резкий скачок в точке $1/2$. Наличие этого скачка как раз-таки и заставляет $S_{Hard}$ менять свои предсказания на диаметрально противоположные каждый раз, когда частота символов меняет свое положение относительно $1/2$.

А что будет, если для предсказания мы воспользуемся стратегией, у которой вероятностные веса обоих символов являются непрерывными функциями от их наблюдаемых частот?


Непрерывная стратегия $S_{Soft}$

Пожалуй, самый простой способ заставить вероятностный вес символа непрерывно зависеть от его наблюдаемой частоты — это положить их равными друг другу. Стратегию, которая при наблюдаемых частотах «нуля» — $P$ и единицы — $Q$, предсказывает «ноль» с вероятностью $\alpha = P$ и «единицу» с вероятностью $\beta = Q$, договоримся называть $S_{Soft}$. Такое название выбрано по аналогии с названием популярной в машинном обучении функцией $Softmax$, которая, также как и $S_{Soft}$, в своей области применения является «гладким» аналогом операции взятия максимума.

В чем заключается смысл стратегии $S_{Soft}$? Если вы видите, что в напечатанной последовательности 10% «нулей» и 90% единиц, то ваше предсказание должно с вероятностью 10% стать «нулем» и с вероятностью 90% — оказаться единицей. Если «нулей» на ленте 90%, а единиц 10%, то все должно быть ровно наоборот. Если же единиц и нулей напечатано оказалось примерно поровну, то и предсказаны они должны быть примерно с одинаковыми вероятностями. Функции зависимости вероятностного веса символа от его наблюдаемой частоты у $S_{Soft}$ линейны, вы их можете рассмотреть на рисунке 4.
image

рис 4

Насколько хорошо $S_{Soft}$ приспосабливается к дисбалансу, насколько удачно у нее получается угадывать символы? Чтобы «прощупать» эти вопросы, давайте возьмем несколько простых последовательностей и попробуем запустить алгоритм $S_{Soft}$ на них.


Эффективность $S_{Soft}$ в простейших случаях

В качестве первого примера рассмотрим цепочку, составленную из двух гомогенных отрезков: последовательно расположенных $NP$ нулей и $NQ$ единиц (рис 5). Я буду предполагать, что эта цепочка достаточно длинная, чтобы была возможность пренебречь «особенностью» угадывания первого символа.
image

рис 5

Все время, пока на ленте печататься только нули, их частота остается равной $1$, поэтому $S_{Soft}$ угадает их все (за исключением быть может первого). Затем начнут появляться единицы. Поначалу доля «единиц» среди присутствующих на ленте символов будет мала, поэтому и предсказывать «единицу» $S_{Soft}$ будет редко. Однако в месте с тем, как число напечатанных «единиц» будет расти, будет расти и вероятность следующую из них предсказать правильно.

Чтобы провести количественные оценки, рассмотрим две альтернативы:

  1. в итоговой последовательности больше нулей
  2. в итоговой последовательности количество единиц больше или равно количеству нулей

Если верна первая альтернатива, то уже только успешное предсказание всех (за исключением
может быть первого) нулей позволяет $S_{Soft}$ правильно угадать больше половины всех символов.

Предположим теперь, что верна вторая альтернатива. Сможет ли в этой ситуации $S_{Soft}$ превзойти стратегию угадывания при помощи монетки?
Чтобы ответить на этот вопрос, мысленно разобьем последовательность на два отрезка: первый из них должен включать в себя $NP$ нулей и $NP$ единиц, а второй — все оставшиеся $N(Q-P)$ единицы (рис 6).

image

рис 6

На первом отрезке $S_{Soft}$ угадает все нули и еще какое-то число единиц, таким образом предсказанными правильно «в среднем» окажутся больше половины его символов. К моменту когда начнет печататься второй отрезок, количество единиц на ленте уже успеет сравняться с количеством нулей, а значит каждый следующий прогноз с вероятностью не меньшей 50% будет правильно предсказывать единицу. Математическое ожидание числа угаданных символов на втором отрезке также оказывается не меньше половины его длинны. Объединяя результата по двум отрезкам, мы можем заключит, что «в среднем» на подобных последовательностях у $S_{Soft}$ в любом случае получится угадать не меньше половины их элементов.


Эффективность $S_{Soft}$ на пульсирующих последовательностях. Формулы

Как вы помните, стратегия $S_{Hard}$ перестала хорошо работать, когда мы применили ее к последовательности, у которой которой роль наиболее распространённого символа в процессе печатанья то и дело переходила от «единицы» к «нулю» и обратно. Давайте посмотрим, каким образом теперь уже $S_{Soft}$ будет вести себя в подобной ситуации.

Для эксперимента возьмем последовательность, составленную из двух участков: стоящего спереди участка «пульсации», где все $NP$ «нулей» последовательности строго чередуются с ее первыми $NP$ «единицами», и идущего за ним «гомогенного» отрезка, заполненного оставшимися $N(Q-P)$ «единицами» (рис 7). Похожие последовательности мы будем называть пульсирующим префиксного типа (в то время как последовательности, у которых участок чередования символов стоит в конце — именовать пульсирующими суфиксного типа).

image

рис 7

Предсказания $S_{Soft}$ будут следующими:

  • Первый элемент будет угадываться с помощью монетки и поэтому он нам не особо интересен.
  • В момент предсказания второго элемента среди напечатанных на ленте символов будет 100% нулей, поэтому $S_{Soft}$ даст прогноз нуля и 100% ошибется.
  • На момент предсказания третьего символа нулей и единиц на ленте поровну, значит с вероятностью 50% сделанный прогноз окажется верным
  • Пусть уже напечатано $k$ «нулей» и $k$ «единиц» (рис 8), посмотрим с какой вероятностью алгоритм угадает очередной «ноль» и очередную «единицу».

    image

    рис 8

    В момент, когда должен появится «ноль» символов обоих типов на ленте поровну, значит $S_{Soft}$ угадает его с вероятностью $1/2$. На следующем шаге «нулей» на ленте станет на один больше и вероятность угадать «единицу» будет равна

    $(1)\ \ \ \ \frac{k}{2k+1}=\ \frac{(k+1/2)-1/2}{2k+1}=\ \frac{1}{2}\cdot\left(1-\frac{1}{2k+1}\right)$


    Отсюда следует, что математическое ожидание числа угаданных символов последовательности на участке их чередования есть:

    $(2)\ \ \ \ \frac{NP}{2}+\frac{NP}{2}\ -\ \frac{1}{2}\cdot\sum_{k=1}^{NP}\frac{1}{2k+1}$


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

    $(3)\ \ \ \ \sum_{k=1}^{NP}\frac{1}{2k+1}\approx1/2\cdot\int_{1/2}^{NP+1/2}{\frac{1}{x+1/2}dx}=\frac{1}{2}\cdot ln{\left(NP+1\right)}\approx\frac{1}{2}\cdot ln{\left(NP\right)}$


    Таким образом среднее число символов, угаданных $S_{Soft}$ на отрезке «пульсации», составит:

    $\left(4\right)\ \ \ \ NP-\frac{1}{4}\cdot ln\left(NP\right)$


    , заменив одно из вхождений $P$ на $1/2 - \delta$, то же самое можно выразить и в другой форме:

    $\left(4'\right)\ \ \ \ \frac{N}{2}-N\delta-\frac{1}{4}\cdot ln(NP)$


  • Пусть уже напечатан весь отрезок «пульсации» и еще $m$ следующих за ним «единиц» «гомогенного» участка (рис 9).

    image

    рис 9

    В этот самый момент на ленте будут находятся $NP$ «нулей» и $NP+m$ «единица», а значит вероятность того, что предсказание, сделанное $S_{Soft}$, окажется единицей, есть

    $(5)\ \ \ \ \frac{m+NP}{m+2NP}=\frac{\left(m+2NP\right)-NP}{m+2NP}=1-NP\cdot\frac{1}{m+2NP}$


    Отсюда находим, что из $N(Q-P)$ «единиц» «гомогенного» участка в среднем правильно предсказанными окажутся:

    $(6)\ \ \ \ \ N\left(Q-P\right)-NP\sum_{m=0}^{N\left(Q-P\right)-1}\frac{1}{m+2NP}$


    Чтобы дать асимптотическую оценку этой формуле, рассмотрим два случая:

    $a)$ $N(Q-P)$ мало по сравнению с $NP$, что по сути эквивалентно условию $\delta \ll1$ или тому, что $P \approx Q \approx 1/2$

    $b)$ $N(Q-P)$ и $NP$ являются величинами одного порядка или даже $N(Q-P)$ много больше $NP$. То же самое может быть выражено требованием, чтобы дисбаланс $\delta$ был соизмерим с единицей.

    Если верно $a)$, то мы можем переписать:

    $(7)\ \ \ \ \sum_{m=0}^{N\left(Q-P\right)-1}\frac{1}{m+2NP}=\frac{1}{2NP}\cdot\sum_{m=0}^{N\left(Q-P\right)-1}\frac{1}{1+m/(2NP)}$


    далее:

    $(8)\ \ \ \ \sum_{m=0}^{N\left(Q-P\right)-1}\frac{1}{1+m/(2NP)}\approx\sum_{m=0}^{N\left(Q-P\right)-1}\left(1-\frac{m}{2NP}\right)$


    в свою очередь стоящее справа в $(8)$ выражение является суммой арифметической прогрессии, вычислить которую не составит большого труда:

    $(9)\ \ \ \ \sum_{m=0}^{N\left(Q-P\right)-1}\left(1-\frac{m}{2NP}\right)\ =N\left(Q-P\right)-\frac{N\left(Q-P\right)\cdot(N\left(Q-P\right)-1)}{4NP}\approx\\\approx N\left(Q-P\right)-\frac{{N(Q-P)}^2}{4P}\ $


    Подставив найденное нами выражения для суммы в $(6)$ и используя тот факт, что $Q-P=2\delta$, мы получим:

    $(10)\ \ \ \ N\left(Q-P\right)-\frac{1}{2}\left(N\left(Q-P\right)-\frac{{N\left(Q-P\right)}^2}{4P}\right)=\ N\cdot\left(\delta\ +\ \frac{\delta^2}{P}\right)$


    Таким образом, при больших $N$ и малых значениях $\delta$ среди $N(Q-P)$ «единиц» «гомогенного» участка правильно предсказанными в среднем окажутся примерно:

    $(6a)\ \ \ \ N\cdot\left(\delta\ +\ \frac{\delta^2}{P}\right) \approx N\cdot\left(\delta\ +\ 2 \delta^2\right)$


    Перейдем теперь к случаю $b)$. Поскольку теперь предполагается, что диапазон изменения $m$ велик, то входящую в $(6)$ сумму с хорошей точностью можно заменить интегралом:

    $(11)\ \ \ \ \sum_{m=0}^{N\left(Q-P\right)-1}{\frac{1}{m+2NP}\approx\ }\int_{-1/2}^{N\left(Q-P\right)-1/2}{\frac{1}{x+2NP}dx}$


    В свою очередь:

    $(12)\ \ \ \ \int_{-1/2}^{N\left(Q-P\right)-1/2}{\frac{1}{x+2NP}dx}=ln\left(N\left(P+Q\right)-\frac{1}{2}\right)-ln\left(2NP-\frac{1}{2}\right)\approx-ln(2P)$


    Подставив найденное выражение в $(6)$, мы получаем, что когда $\delta$ соизмерима с единицей, число угаданных символов «гомогенного» отрезка асимптотически может быть представлено как:

    $(6b)\ \ \ \ \ N(Q-P) + NP\cdot ln(2P)$


    или в эквивалентной форме:

    $(6b')\ \ \ \ \ 2N\delta+\frac{N}{2}(1-2\delta)\cdot ln(1-2\delta)$




Эффективность $S_{Soft}$ на пульсирующих последовательностях. Выводы

После того, как мы нашли среднюю результативность $S_{Soft}$ на отдельных участках, давайте подсчитаем, сколько символов будет ею угадано во всей последовательности.
Если $\delta \ll1$, то нам необходимо сложить $(4')$ и $(6а)$:

$(13)\ \ \ \ \frac{N}{2}-N\delta-\frac{1}{4}\cdot ln\left(NP\right)+N\left(\delta\ +\ 2\delta^2\right)$


а если $\delta$ соизмерима с единицей, — то $(4')$ и $(6b')$:

$(14)\ \ \ \ \frac{N}{2}-N\delta-\frac{1}{4}\cdot ln{\left(NP\right)}+2N\delta+\frac{N}{2}(1-2\delta) \cdot ln(1-2\delta)$


Таким образом для малых $\delta$ средняя доля угаданных символов выражается формулой $15a$:

$(15a)\ \ \ \ \frac{1}{2}+2 \delta^2-\frac{ln\left(NP\right)}{4N}$


а если $\delta$ соизмерима с единицей, то формулой $15b$:

$(15b)\ \ \ \ \frac{1}{2}+\delta+\frac{(1-2\delta)\cdot ln(1-2\delta)}{2}-\frac{ln{\left(NP\right)}}{4N}$


Какие мы можем сделать выводы, глядя на эти формулы?
Во первых стоит обратить внимание на присутствующее в обеих формулах слагаемое

$(16)\ \ \ \ -\frac{ln\left(NP\right)}{4N}$


Как вы уже наверное догадались, с ростом $N$ его значение довольно быстро сходится к нулю и применительно к длинным последовательностям этим членом можно пренебречь. Если так, то формула $15a$ показывает, что даже при небольшой величине дисбаланса между «нулями» и «единицами» $S_{Soft}$ угадывает в среднем примерно на $N\delta^2$ больше символов, чем если бы эти символы предсказывались с помощью бросания монетки. В свою очередь, если дисбаланс велик, то из формулы $15b$ следует, что асимптотически доля угаданных символов задается функцией

$(17)\ \ \ \ \rho_{success}(\delta)=\frac{1}{2}+\delta+\frac{(1-2\delta)\cdot ln(1-2\delta)}{2}$


На на рисунке 10 изображен график этой функции, из которого видно, что и при соизмеримых с единицей $\delta$ в пульсирующих последовательностях $S_{Soft}$ в среднем угадывает все равно больше символов, чем делает это стратегия с подбрасыванием монетки.


рис 10

Хорошо, похоже нам удалось показать, что $S_{Soft}$ угадывает в среднем больше половины символов, если последовательность имеет по ним дисбаланс и относится к одному из двух специальных типов. Однако в рамках настоящего исследования куда более важным является другой вопрос: способна ли $S_{Soft}$ угадывать в среднем больше половины символов в любой последовательности при том единственном условии, что эта последовательность составлена из значимо различного количества «нулей» и «единиц». Мы сможем дать на него ответ, если для любых $N$, $P$ и $Q$ среди всех последовательностей с $NP$ «нулями» $NQ$ «единицами» найдем те, которые $S_{Soft}$ получается предсказывать хуже всего.


Эффективность $S_{Soft}$ в наихудшем для нее сценарии
Пусть у нас имеются $NP$ «нулей» и $NQ$ «единиц». В каком порядке их нужно расставить на ленте, чтобы в получившейся последовательности математическое ожидание числа угаданных $S_{Soft}$ элементов оказалось наименьшим?

Как вы наверное догадались, эту задачу было бы трудно решить прямым перебором, ведь даже для конкретных $NP$ и $NQ$, когда те одновременно велики, возможных способов расставить символы будет попросту астрономически много. Вместо метода грубой силы попробуем пойти другим путем и попытаемся понять, какими свойствами должна обладать последовательность, чтобы ее предсказуемость по отношению к $S_{Soft}$ уже нельзя было ухудшить.

Собственно идея нашего подхода будет следующей: пусть имеется некоторая последовательность с характерным для нее порядком «нулей» и «единиц», выберем в этом порядке какой-нибудь «ноль», какую-нибудь «единицу», а затем поменяем их местами. Если предсказуемость изначальной последовательности по отношению к $S_{Soft}$ уже была минимальной, то произведенная нами транспозиция не сможет сделать ее меньше.
Обратное утверждение, вообще говоря, не верно, однако если среди всех последовательностей, составленных из $NP$ «нулей» и $NQ$ «единиц», подобным свойством будет обладать всего одна, то именно она и будет решением нашей задачи.

Предположим, что $P>Q$ и наша последовательность оканчивается парой: $...01$. В каком из случаев $S_{Soft}$ угадает больше элементов: если мы оставим все как есть, или поменяем два последних символа местами?

image

рис 11

Очевидно, что предполагаемая перестановка никак не повлияет на среднее число символов, которые $S_{Soft}$ угадает среди первых $N-2$ элементов, и нам остается только посчитать, как будет различается эффективность предсказаний двух последних символов до и после их перестановки.

В изначальном порядке стоящий на предпоследнем месте «ноль» $S_{Soft}$ правильно предскажет с вероятностью $(NP-1)/(N-2)$, а стоящую последнем месте единицу — с вероятностью $(NQ-1)/(N-1)$, таким образом среднее число угаданных символов на этих двух позициях будет равно:

$(18)\ \ \ \ \frac{NP-1}{N-2}+\frac{NQ-1}{N-1}=\frac{\left(N^2-3N+3\right)-NQ}{(N-1)(N-2)}$


Если выполнить транспозицию, то шансы угадать ноль станут равными $(NP-1)/(N-1)$, а шансы угадать единицу — $(NQ-1)/(N-2)$, поэтому формула для среднего числа правильно предсказанных символов примет вид:

$(19)\ \ \ \ \frac{NP-1}{N-1}+\frac{NQ-1}{N-2}=\frac{\left(N^2-3N+3\right)-NP}{(N-1)(N-2)}$


Из этих двух формул видно, что $S_{Soft}$ предсказывает хуже тот вариант последовательности, в конце которой стоит более распространенный в ней символ. Согласно нашим допущениям $P>Q$, а значит этим символом должен быть «ноль».

Итак, если предсказуемость последовательности по отношению к $S_{Soft}$ минимальна и $P>Q$, то она не может оканчиваться единственной «единицей», перед которой стоит «ноль». Давайте проверим, может ли она заканчиваться несколькими единицами, стоящими подряд.

image

рис 12

Пусть дана последовательность (рис 12), у которой на $(k-1)$-ой позиции стоит «ноль», на $k$-ой и последующих позициях — «единицы» и соответственно на первых $(k-2)$-ух позиция в ее начале как-то размещены остальные $(NP-1)$ «нулей» и $NQ-(N-k+1)$ «единиц». Если мы стремимся к тому, чтобы $S_{Soft}$ в среднем угадала как можно меньше элементов, должны ли мы оставить в этой последовательности все как есть, или нам следует самый правый «ноль», находящийся на $(k-1)$-ой позиции, и соседнюю с ним «единицу» на $k$-ой поменять местами?

Здесь стоит сделать маленькое отступление и указать на одну важную особенность в алгоритме работы $S_{Soft}$: вероятностные веса, с которыми выбираются «ноль» и «единица» для предсказания $i$-го элемента, зависят только от соотношения между их числом среди первых $(i-1)$-го символов последовательности (на ее начальном отрезке длины $(i-1)$), и совершенно не зависят от того порядка, в котором эти символы там расположены. Если в конкретной последовательности поменять местами произвольное количество символов среди первых ее $L$ элементов, то такая перестановка никак не скажется на эффективности, с которой $S_{Soft}$ будет угадывать элементы с номерами от $L+1$ (включительно) до $N$ (включительно). Отсюда, кстати, следует простая, но замечательная

Лемма 1: Если какая-то последовательность обладает минимальной по отношению к $S_{Soft}$ предсказуемостью, то и любой ее начальный отрезок также является последовательностью, наименее предсказуемой для $S_{Soft}$.

(Действительно, пусть $\alpha$ — бинарная последовательность длины $N$, обладающая минимальной по отношению к $S_{Soft}$ предсказуемостью, а $L$ — какое-нибудь число, меньшее $N$. Если бы предсказуемость последовательности первых $L$ элементов $\alpha$ по отношению к $S_{Soft}$ не была минимальной, то их можно было бы расставить в другом порядке, сделав ее (предсказуемость) таковой. С другой стороны произведенная перестановка нисколько бы не повлияла на величину математического ожидания числа тех элементов, которые $S_{Soft}$ должна угадать на отрезке $[L+1, N]$, а значит предсказуемость всей видоизмененной последовательности оказалась бы меньше, чем у $\alpha$. Полученное противоречие как раз и доказывает Лемму $1$.)

Вернемся однако к вопросу, который был задан выше: пусть в бинарной последовательности
количество «нулей» в целом больше числа «единиц», уменьшится ли ее предсказуемость, если самый правый «ноль» в ней поменять местами со состоящей справа от него «единицей»?

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

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

Лемма 2: Если последовательность обладает наименьшей по отношению к $S_{Soft}$ предсказуемостью, то она не может заканчиваться менее распространенным в ней символом.

Имея в своем распоряжении леммы $1$ и $2$, уже совсем не трудно выяснить, в каким видом должна обладать бинарная последовательность $\alpha$, чтобы ее предсказуемость относительно $S_{Soft}$ была минимальной.
Пусть буква $A$ — обозначает число «нулей», которые включает в себя $\alpha$, а буква $B$ — число содержащихся в ней «единиц». Поскольку относительно «единиц» и «нулей» задача полностью симметрична, то без ограничения общности мы можем предполагать, что $A\geq B$.

Разберем сначала случай, когда неравенство между $A$ и $B$ является строгим. Поскольку при этом «нулей» в $\alpha$ будет строго больше, чем единиц, то согласно лемме $2$ на ее конце должен стоять «ноль» (рис 13a). Мысленно вычеркнем этот ноль. Оставшаяся последовательность является начальным отрезком $\alpha$ длины $(A + B - 1)$, соответственно, в ней должны содержаться теперь уже $(A-1)$ «ноль» и все прежние $B$ единиц. Согласно лемме $1$ эта последовательность также обладает наименьшей предсказуемостью относительно $S_{Soft}$, поэтому если вдруг окажется, что число «нулей» в ней по прежнему строго больше числа «единиц», то все наши рассуждения вместе с мысленным вычеркиванием последнего «нуля» мы можем повторить снова (рис 13b).

image

рис 13

Действуя таким образом, в конце концов мы вычеркнем из $\alpha$ в точности $(A - B)$ стоящих на ее конце «нулей». В результате останется последовательность, состоящая из $2B$ элементов, назовем ее $\beta$, в которой количество «нулей» и «единиц» будет равным (рис 13с). По лемме $1$ последовательность $\beta$ также должна обладать минимальной предсказуемостью относительно $S_{Soft}$, однако на этот раз мы уже не можем однозначно сказать, какой именно символ будет стоять у нее на конце!

Предположим сначала, что на конце стоит «ноль» (рис 14а). Мысленно вычеркнем этот «ноль» из последовательности. Оставшаяся часть $\beta$ будет включает в себя $(B-1)$ «ноль», $B$ «единиц», а еще будет обладать, согласно лемме $1$, минимальной предсказуемостью относительно $S_{Soft}$. Все эти факты позволяют нам утверждать, что последний символ урезанной версии $\beta$, то есть предпоследний символ самой $\beta$, уж точно должен быть единицей.

image

рис 14

Если бы мы предположили, что на конце $\beta$ стоит не «ноль», а «единица», то из симметричных соображений необходимо бы пришли к тому выводу, что ее предпоследний элемент должен быть «нулем» (рис 14b). На самом деле, разница между этими двумя версиями $\beta$ для нас не столь существенна, поскольку они обе совершенно одинаково непредсказуемы относительно $S_{Soft}$. Действительно, так как в обоих случаях двум последним элементам предшествует равное число «нулей» и «единиц», то перестановка их (двух последних элементов) местами на предсказуемость $\beta$ повлиять никак не может. По сути, только что нами были доказаны следующая

Теорема 1: Последовательность, составленная из $A$ «нулей» и $B$, не превосходящего $A$, числа «единиц», будет обладать минимальной относительно $S_{Soft}$ предсказуемостью в точности тогда, когда:
$a)$ последние ее $(A-B)$ позиций будут заняты «нулями»;
$b)$ первые ее $2B$ элементов будут представлять из себя $B$ последовательно расположенных пар «нуля» и «единицы», порядок символов в каждой паре может быт выбран произвольным (рис 15).

image

рис 15

Наверное, читатель уже обратил внимание на то замечательное совпадение, что под требования теоремы $1$ как раз-таки подходят уже хорошо знакомые нам пульсирующие последовательности префиксного типа. Параграфом раннее мы получили формулу для математического ожидания доли тех элементов в пульсирующих последовательностях, которые стратегия $S_{Soft}$ по итогу сможет предсказать правильно. Теперь этот результат приобретает новый смысл и достоин быть выделен в отдельную

Теорема 2: Какова бы ни была бинарная последовательность $\alpha$, математическое ожидание доли тех из ее элементов, которые стратегия $S_{Soft}$ по итогу сможет предсказать правильно, никак не меньше чем

$(20)\ \ \ \ \rho_{success}(\delta)=\frac{1}{2}+\delta+\frac{(1-2\delta)\cdot ln(1-2\delta)}{2} - O\left(\frac{ln(N)}{N}\right)$

, где $N$ — это длина $\alpha$, $\delta$ — дисбаланс между количествами содержащихся в ней «нулей» и «единиц», а оценка $O\left(\frac{ln(N)}{N}\right)$ не зависит от $\delta$


Промежуточные итоги


Интригующий ответ
В начале статьи был задан вопрос:
«Если количество „единиц“, которое присутствует на распечатанном участке последовательности, существенно превышает число имеющихся там „нулей“, разумно ли тогда в качестве предсказаний ее новых элементов „единицы“ называть чаще „нулей“?»

Теперь уже хорошо изученный нами пример стратегии $S_{Soft}$ склоняет нас к тому, чтобы ответить на этот вопрос положительно, правда грань между истиной и заблуждением здесь куда тоньше, чем может показаться на первый взгляд. Если вы не хотите перейти этой грани, то каждый раз обязательно должны уточнять: «в каком смысле», «при каких условиях» и что значит «разумно». Давайте рассмотрим две существенно различные ситуации.

Ⅰ. Сначала предположим, что в момент, когда на ленте еще не напечатан ни один символ, вы почему-то решили прибегнуть к стратегии $S_{Soft}$. Такое решение, например, будет вполне оправданным, если вы хотите у будущей последовательности, имей она значимый дисбаланс и достаточно большую длину, угадать в среднем больше половины ее элементов, в противном же случае — не слишком сильно проиграть по количеству угаданных символов стратегии с монеткой.

Пусть прошло некоторое время, часть последовательности была напечатана, какая-то часть ваших прогнозов успела оправдаться, другая часть — нет, и в этот момент вдруг оказалось, что «единиц» на ленте больше имеющегося там количества «нулей». В данной ситуации и при данных предположениях для вас будет абсолютно разумно подчиниться инструкциям $S_{Soft}$ и в своем предсказании следующего элемента установить для «единицы» больший вероятностный вес, чем для «нуля».

Почему разумно? Потому что придерживаясь изначально выбранной стратегии, вы действительно достигните желаемого результата. Если напечатанная в итоге последовательность окажется достаточно длинной и будет иметь существенный дисбаланс, то «в среднем» вы предскажите больше половины ее элементов, а если — нет, то по количеству угаданных символов не сильно проиграете стратегии $S_{Coin}$

Неужели наш мир устроен так, что будущее в нем способно как-то влиять на прошлое?
Может быть и да, но как вы увидите чуть позже, эта потенциально экстравагантная черта Вселенной к рассматриваемой здесь проблеме не имеет ровно никакого отношения. Чтобы во всем разобраться…

Ⅱ. Давайте слегка поменяем условия прошлого примера. Ваша цель остается прежней: суметь угадать в неизвестной последовательности как можно больше ее элементов. Прежней остается и стратегия, которой вы должны придерживаться, — это $S_{Soft}$. Однако на этот раз вы стартуете с момента, когда на ленте уже напечатано какое-то фиксированное и заранее известное вам число символов.

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

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


Пессимисты не приспосабливаются
Пришло время объяснить ту особую роль, которую в нашем повествовании играет стратегия угадывания символов при помощи монетки. Дело в том что среди вообще всех возможных стратегий $S_{Coin}$ позволяет получить «гарантированный средний выигрыш» максимального размера. Смысл здесь таков: если взять каждую стратегию и найти, каково будет математического ожидания доли угаданных ею символов в наименее предсказуемой для нее последовательности, то именно у стратегии $S_{Coin}$ эта величина окажется самой большой. Получается, что если вы — абсолютный и рациональный пессимист, то наилучшая для вас стратегия одна — это $S_{Coin}$.

Строгое доказательство, только что сделанных утверждений будет дано ниже (см лемма 3), а сейчас я бы хотел, чтобы вы акцентировали свое внимание вот на какой идее. Попытка адаптации, вообще говоря, не дается бесплатно: если алгоритм рассчитан искать и приспосабливаться к эмпирическим закономерностям, то скорее всего его наихудший результат будет меньше, чем результат, который в наихудшем для себя сценарии покажет стратегия абсолютно пессимиста (Более подробно о концепции «крайнего математического пессимизма» вы можете прочитать в предыдущей статье: habr.com/ru/post/517070). Что касается стратегии $S_{Soft}$, то, как было показано, ее наихудший результат проигрывает наихудшему результату $S_{Coin}$ на величину

$-\frac{ln\left(N/2\right)}{4N}$

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

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

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

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


Добавление: Общая теория отгадывания дисбалансных последовательностей


Формальности
В предыдущих параграфах объектом нашего исследования были лишь несколько специально подобранных стратегий. В этом же разделе мы будем говорить вообще обо всех возможных стратегиях. Ну, или почти обо всех, а значит с самого начало важно уточнить, какой смысл вкладывается в понятие «стратегия». Под словом «стратегия» обычно понимается: «некий план действий для каждой конкретной ситуации». В нашем случае «действием» является предсказание следующего элемента последовательности, точнее, — назначение «нулю» и «единице» вероятностных весов, с которыми они в этом предсказании будут участвовать. Что касается обстоятельств, то мы не будем включать сюда мнение вашего соседа или состояние погоды над вашей головой, хотя и такие теории тоже могут быть построены. Единственное обстоятельство, котором мы действительно будем интересоваться — это то, какая последовательность символов уже присутствует на ленте в момент предсказания.

При заявленном подходе любая стратегия $S$ есть функция, которая каждой возможной бинарной конечной последовательности $\alpha$ ставит в соответствие пару весов: вес «нуля» $p = S^0(\alpha)$ и вес «единицы» $q=S^1(\alpha)$, где $p+q=1$.

Математическое ожидание числа символов, которые стратегия $S$ угадает в последовательности $\alpha$, договоримся обозначать как $Success(S,\ \alpha)$, а математическое ожидание доли таких символов — как $\rho_{success}(S, \alpha)$.


Кто лучше?
Стремление к совершенству — одна из черт человеческой культуры, которая, понятное дело, переносится и на математику. Пусть имеются сразу две стратеги для угадывания элементов в неизвестных последовательностях: №1 и №2, как понять, какая из них лучше? Нетривиальным этот вопрос делает гипотетическая ситуация, при которой результаты первой стратегии оказываются лучше на одних последовательностях, а результаты второй — на других. Примером здесь могут служить способы угадывания, согласно первому из которых всегда называется «ноль», а согласно второму — «единица». Если на ленте в итоге будет напечатано больше «нулей», то лучший результат покажет первый способ, а если — «единиц», то — второй.

От подобной неоднозначности можно избавиться, если стратегии сравнивать по величине ожидаемого от них результата в наименее предсказуемых для них последовательностях. Обозначим как $Inf(S)$ наименьшее (точную нижнюю грань) математическое ожидание доли угаданных символов, которое стратегия $S$ позволяет получить среди вообще всех бинарных последовательностях, через ${Inf}_n(S)$ — ту же самую величину, но вычисленную только среди последовательностей длины $n$, а через ${Inf}_{A,B}(S)$ — ее же, но среди последовательностей, составленных ровно из $A$ «нулей» и $B$ «единиц».

Эти три оператора порождаю на множестве стратегий три различных (частичных) порядка сравнения:
«глобального»- $\preccurlyeq$,
«с варьируемой длинной» — $\preccurlyeq_N$ и
«с варьируемым составом» — $\preccurlyeq_{Comp}$.
Соответственно отношение $S^\prime\preccurlyeq\ S^{\prime\prime}$ означает просто, что $Inf(S^\prime)\le Inf(S^{\prime\prime})$,
далее $S^\prime\preccurlyeq_N\ S^{\prime\prime}$ — что при всех значениях длин $n$: ${Inf}_n(S^\prime)\le{Inf}_n(S^{\prime\prime})$,
и наконец $S^\prime\preccurlyeq_{Comp}\ S^{\prime\prime}$ выполняется тогда и только тогда, когда для любых возможных $A$ и $B$ справедливо неравенство ${Inf}_{A,B}(S^\prime)\le{Inf}_{A,B}(S^{\prime\prime})$.

Разумеется, если стратегия $S^{\prime\prime}$ нестрого превосходит стратегию $S^\prime$ в порядке «с варьируемым составом», то есть $S^{\prime\prime}\preccurlyeq_{Comp}\ S^{\prime\prime}$, то $S^{\prime\prime}$ нестрого превосходит $S^\prime$ и в порядке «с варьируемой длиной»: $S^\prime\preccurlyeq_N\ S^{\prime\prime}$. Аналогично: если $S^{\prime\prime}$ нестрого превосходит стратегию $S^\prime$ в порядке «с варьируемой длиной»: $S^\prime\preccurlyeq_N\ S^{\prime\prime}$, то обязательно $S^{\prime\prime}$ нестрого превосходит $S^\prime$ и в «глобальном» порядке: $S^\prime\preccurlyeq\ S^{\prime\prime}$. А вот обратные утверждения не верны.

Так, если под $S^\prime$ и $S^{\prime\prime}$ подразумевать соответственно стратегию всегда называть «ноль» и стратегию всегда называть «единицу», то при всех $n$: ${Inf}_n(S^\prime) = {Inf}_n(S^{\prime\prime}) = 0$ (первая из них не отгадает ни одного символа в последовательности из $n$ «единиц», а вторая — ни одного символа в последовательности из $n$ «нулей»), поэтому в порядке $\preccurlyeq_N$ эти стратегии в некотором смысле «равны», то есть одновременно и $S^\prime\preccurlyeq_N S^{\prime\prime}$ и $S^{\prime\prime}\preccurlyeq_N\ S^\prime$. С другой стороны в порядке $\preccurlyeq_{Comp}$ эти стратегии оказываются несравнимыми (как пианист и шеф повар ресторана), поскольку последовательности, состоящие из одних «нулей», лучше угадывает первая, а последовательности, составленные из одних «единиц» — вторая.

Чтобы получить пример, когда превосходство в «глобальном» порядке не влечет превосходства в порядке с «варьируемой длиной», в качестве $S^{\prime\prime}$ возьмем стратегию, которая угадывает символы с помощью «кривой» монетки («ноль» = $1/3$, «единица» = $2/3$), а в качестве $S^\prime$ — нашу обычную «симметричную» $S_{Coin}$, правда с той оговоркой, что первое предсказание теперь всегда будет «нулем». При любых значениях длины, наименее предсказуемыми для $S^{\prime\prime}$ будут последовательности, состоящие из одних нулей: ожидаемый на них результат — $1/3$ угаданных символов. Таким образом ${Inf}_n(S^{\prime\prime}) = {Inf}(S^{\prime\prime}) = 1/3$. Стратегия $S^\prime$ в очень длинных последовательностях будет угадывать почти половину их элементов, поэтому не верно, что $S^\prime\preccurlyeq_N\ S^{\prime\prime}$. В тоже время, в наихудшем для $S^\prime$ сценарии, когда последовательность состоит из единственной «единицы», математическое ожидание угаданных ею символов будет равно нулю, это меньше, чем ${Inf}(S^{\prime\prime})$, поэтому $S^\prime\preccurlyeq\ S^{\prime\prime}$.

Какой смысл во всех этих порядках сравнения?

Предположим, вам на выбор даны две стратегии: $S^\prime$ и $S^{\prime\prime}$, а сами вы заинтересованы в том, чтобы «средняя» доля угаданных символов в наихудшем возможном сценарии была максимальна.

$a)$ Пусть вам известно, что на ленте могут быть напечатана только последовательность из $A$ «нулей» и $B$ «единиц», хотя сами величины $A$ и $B$ остается для вас в тайне. Пусть вам также известно, что потенциально на ленте может быть напечатана любая такая последовательность. Если при этом $S^\prime\preccurlyeq_{Comp}\ S^{\prime\prime}$, то стратегию $S^\prime$можно исключить из рассмотрения.

$b)$ Пусть вам известно, что на ленте могут быть напечатаны только последовательности некоторой определенной, хотя и неизвестной вам длины $n$. Вам также известно, что потенциально может быть напечатана любая такая последовательность. Если при этом $S^\prime\preccurlyeq_N\ S^{\prime\prime}$, то стратегию $S^\prime$ можно исключить из рассмотрения.

$c)$ Пусть вам известно, что на ленте может быть напечатана вообще любая последовательность и при этом $S^\prime\preccurlyeq\ S^{\prime\prime}$, тогда стратегию $S^\prime$ можно исключить из рассмотрения.


Идеальный объект
Если вы — ортодоксальный пессимист, у которого нет каких-либо предположений о длине и составе будущей последовательности, то вас должна интересовать исключительно та стратегия, которая дает наибольший $Inf(S)$. Все необходимые сведения о подобных стратегиях содержаться в следующей

Лемма 3: Пусть $n$ — произвольное натуральное число и на ленте может быть напечатана любая бинарная последовательность длинны $n$. В этих предположениях наибольшее математическое ожидание доли символов, которые стратегия угадает в наихудшем для себя сценарии, среди всех возможных стратегий обеспечивает $S_{Coin}$. Коротко то же самое утверждение можно записать так:
Какова бы ни была стратегия $S$, обязательно $S \preccurlyeq_N\ S_{Coin}$.

Следствие: Предположим, что на ленте может быть напечатана вообще любая бинарная последовательность, тогда наибольшее математическое ожидание доли символов, которые стратегия угадает в наихудшем для себя сценарии, среди всех возможных стратегий обеспечивает $S_{Coin}$. Другими словами,
Какова бы ни была стратегия $S$, обязательно $S \preccurlyeq\ S_{Coin}$.

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

Возьмем произвольную стратегию $S$. В самом начале на ленте еще ничего не напечатано, но формально — на ней уже присутствует последовательность из ноль символов, обозначим ее как $\alpha_0$. Стратегия $S$ должна принять $\alpha_0$ как аргумент, а в ответ выдать вероятностные веса «нуля» и «единицы». Если веса обоих символов не равны $1/2$ напечатаем на ленте тот символ, для которого установлен меньший вес, в противном случае — напечатаем любой из них. Получившуюся последовательность из одного элемента обозначим как $\alpha_1$. Какая бы из вышеуказанных альтернатив не реализовалась, математическое ожидание числа символов, которые $S$ угадает в $\alpha_1$ не превышает $1/2$. Дальше будем рассуждатьть по индукции. Пусть, действуя описанным выше способом, мы уже напечатали $k$ символов, составляющих вместе последовательность $\alpha_k$. Посмотрим, имеется ли перекос между вероятностными весами «нуля» и «единицы», которые стратегия $S$ назначит на аргументе $\alpha_k$. Если да, то напечатаем символ, которому соответствует меньший вес, иначе — напечатаем любой из них. Получившуюся последовательность назовем $\alpha_{k+1}$.

По индукционному предположению математическое ожидание числа символов, которые $S$ угадает в $\alpha_k$ не превышает $k/2$. Более того оно может быть равно $k/2$ только тогда, когда на всех предыдущих шагах индукции вероятностные веса «нуля» и «единицы» были раны друг другу. Следовательно все символы, из которых состоит $\alpha_k$ оказались выбранными произвольно. Чтобы результат не зависел от произвола под $\alpha_k$ в этом случае должна подразумеваться вообще любая бинарная последовательность длинны $k$. Понятное дело, что все вышесказанное распространяется теперь и на $\alpha_{k+1}$, а значит индукционный шаг сделан и тем самым доказательство завершено.


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

Сперва заметим, что кой бы ни была бинарная последовательность $\alpha$ у нее есть «негативный» брат-близнец — ее (знаковая)инверсия $\widetilde{\alpha}$ (тильда -«альфа»). Чтобы получит $\widetilde{\alpha}$, нужно в $\alpha$ каждую «единицу» заменить на «ноль», а каждый «ноль» — на «единицу». При повторном действии оператор «тильда» возвращает последовательность к ее исходному виду: $\widetilde{\widetilde{\alpha}}=\alpha$.

Понятие инверсии бинарных последовательностей порождает понятие инверсии на множестве их классов. Пусть $K$ — произвольный класс, тогда $\widetilde{K}$ — это класс, образованный инверсиями последовательностей из $K$. Как и в предыдущем случае, легко проверяется, что $\widetilde{\widetilde{K}}=K$.

Похожим образом можно инвертировать не только последовательности и их классы, но и стратегии. Пусть $S$ — произвольная стратегия. Если заменим в ее определении каждое упоминания о символе «нуля» словом «единица», а каждое упоминание о символе «единица», словом «ноль», то в итоге мы как раз и получим инверсию $S$, обозначаемую как $\widetilde{S}$. На языке алгебры инвертированная стратегия определяется так:

$(1) \ \ \ \ \left\{\begin{matrix}{\widetilde{S}}^0(\alpha)=S^1(\widetilde{\alpha})\\{\widetilde{S}}^1(\alpha)=S^0(\widetilde{\alpha})\\\end{matrix}\right\}$


Как и в случае последовательностей, всегда выполняется тождество: $\widetilde{\widetilde{S\ }}=\ S$.

Если у нас есть преобразование, то значит должна быть и симметрия! Симметричными мы будем называть такие объекты, которые совпадают со своими инверсиями.

Бинарная последовательность совпадает со своей инверсией тогда и только тогда, когда она пуста (не содержит ни одного символа). Класс $K$ бинарных последовательностей симметричен тогда и только тогда, когда вместе со всякой принадлежащей ему последовательностью в него входит и ее инверсия.

Симметричные стратегии — это в точности те стратегии, которые не испытывают смысловых изменений, когда в их определениях слова «ноль» и «единица» меняются местами. На любой последовательности $\alpha$ симметричные стратегии должны предсказывать «ноль» с той же вероятностью, что и «единицу» на последовательности $\widetilde{\alpha}$. Для примера, стратегии: $S_{Coin}$, $S_{Hard}$ и $S_{Soft}$ — симметричные, а вот стратегия всегда называть «ноль» — нет.

В математике имеется весьма общий способ, позволяющий из несимметричных алгебраических объектов получать симметричные. Скажем, если вы имеете дело с матрицами, то симметричными среди них считаются те, которые не меняются при транспонировании: $A^T=A$. Чтобы из произвольной матрицы $B$ получить симметричную достаточно взять полусумму самой $B$ и $B^T$: $Simm\left(B\right)=\ \frac{1}{2} \cdot (B+\ B^T)$. В том случае, когда $B$ уже является симметричной, оператор $Simm()$ оставит ее вид неизменным: $Simm(B) = B$.
Другой пример: действительнозначную функцию $f(x)$ принято называть «нечетной», если ее график симметричен относительно начала координат, то есть, при всех допустимых $x$ справедливо тождество $f(x) = -f(-x)$. Любую действительнозначную функцию $g(x)$ можно симметризовать, положив $Simm(g)(x) =\ \frac{1}{2} \cdot (g(x) + (- g(-x))$, причем, если $g(x)$ уже была симметричной (нечетной), то $Simm(g)(x)=g(x)$.

По аналогии с предыдущими примерами можно ввести оператор симметризации и для стратегий. Определим его по формуле $Simm\left(S\right)=\ \frac{1}{2}(S+\widetilde{S}\ )$, или в более подробной записи:

$(2) \ \ \ \ \left\{\begin{matrix}{Simm(S)}^0(\alpha)={\frac{1}{2}(S}^0(\alpha)+{\widetilde{S}}^0(\alpha))\\{Simm(S)}^1(\alpha)={\frac{1}{2}(S}^1(\alpha)+{\widetilde{S}}^1(\alpha))\\\end{matrix}\right\}$


Разумеется, если стратегия $S$ уже была симметричной, то действие оператора $Simm()$ на ней никак не скажется.

Конечно, не всегда симметричные стратегии столь хороши, как некоторые несимметричные. Например, ни одна симметричная стратегия не предсказывает состоящие преимущественно из «нулей» последовательности так же хорошо, как это делает $S_{NULL}$ — несимметричная стратегия, суть которой состоит в том, чтобы всегда называть «ноль». Более лаконично последнюю мысль можно записать так:
Какова бы ни была $S$ и каковы бы ни были $A$ и $B$, если $S$ симметрична и при этом $A>B$, то ${Inf}_{A,B}(S)\le{Inf}_{A,B}(S_{NULL})$. В то же время, если искать инфинум в симметричных классах, то будет справедлива

Теорема 3:Обозначим как ${Inf}_K(S)$ наименьшее (точную нижнюю грань) математическое ожидание доли тех символов, которые стратегия $S$ позволяет угадать в последовательностях из класса $K$. Какова бы ни была стратегия $S$ и класс последовательностей $K$, если $K$ симметричен, то:

$(3) \ \ \ \ {Inf}_K(S)\le{Inf}_K(Simm(S))$



Чтобы доказать лемму, нам достаточно показать, что для любой последовательности $\alpha$

$(4)\ \ \ \ \ \ min\left[Success(S,\alpha),\ Success(S,\widetilde{\alpha})\right] \le Success(Simm(S),\ \alpha)$


Выведем сперва одно простенькое, но полезное тождество. Пусть $\gamma$ — произвольная последовательность, а $k$ — не менее произвольная в ней позиция. Вероятность, с которой стратегия $Simm(S)$ угадает символ в позиции $k$, равно среднему арифметическому между вероятностями, с которыми его угадают $S$ и $\widetilde{S}$. В тоже время вероятность $\widetilde{S}$ угадать $k$-тый символ $\gamma$ в точности равна вероятности $S$ угадать $k$-ый символ в последовательности $\widetilde{\gamma}$. Суммируя результат по всем позициям, мы получаем, что:

$(5)\ \ \ \ \ \ Success(Simm\left(S\right), \gamma)=\frac{1}{2}(Success(S,\gamma)\ +Success(S,\widetilde{\gamma}))$


Выберем $\gamma = \alpha$, тогда:

$(6)\ \ \ \ \ \ Success(Simm\left(S\right), \alpha)=\frac{1}{2}(Success(S,\alpha)\ +Success(S,\widetilde{\alpha})) \geq \\ \geq min\left[Success(S,\alpha),\ Success(S,\widetilde{\alpha})\right]$


Таким образом соотношение $(4)$ установлено и доказательство теоремы можно считать завершенным.

Когда порядок не имеет значения
Все конкретные стратегии, которые мы рассмотрели до этого: $S_{Hard}$, $S_{Soft}$, $S_{NULL}$, имеют одну общую черту. Все они проявляют сходство в том, что при вычислении вероятностных весов «нуля» и «единицы» ими никак не учитывается, в каком именно порядке расположены присутствующие в этот момент на ленте символы. На языке математики сказанное означает, что ассоциированные с этими стратегиями функций $p = S^0(\alpha)$ и $q = S^1(\alpha)$ зависят только от $ {|\alpha|}_0 $ — количества «нулей» и $ {|\alpha|}_1 $ — количества «единиц», содержащихся в последовательности $\alpha$:

$S^0(\alpha) = S^0({|\alpha|}_0,\ {|\alpha|}_1)$ и

$S^1(\alpha) = S^1({|\alpha|}_0,\ {|\alpha|}_1)$,

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

Вполне естественно задать вопрос: насколько беспорядковые стратегии «хуже» стратегий общего вида, насколько для предсказания следующего элемента последовательности важен порядок среди ее уже напечатанных символов?

Чтобы дать этому вопросу интуитивное понимание, выберем какую-нибудь произвольную (не обязательно беспорядковую) стратегию $S$ и две последовательности $\gamma$ и $\gamma^\prime$ длины $n$, отличающиеся друг от друга только порядком первых $k$ символов. Пусть то, насколько «хороша» $S$, мы измеряем по среднему числу угаданных ею символов в наименее предсказуемой для нее последовательности с таким же составом, как и у $\gamma$.

Насколько тогда существенно, что «среднее» число символов, которое $S$ сумеет угадать среди элементов с $(k+1)$-вый по $n$-тый, может быть не одинаковым для $\gamma$ и $\gamma^\prime$? Насколько для нас важно, что среди первых $k$ элементов этих последовательностей «среднее» количество угаданных стратегией $S$ символов тоже, вообще говоря, различно?
Можем ли мы переопределить $S$ так, чтобы она не «ухудшилась», но при этом стала беспорядковой?

Ответом на эти вопросы будет следующая действительно сильная теорема.

Теорема 4: Какова бы ни была стратегия $S$, стандартным образом по ней можно построить такую беспорядковую стратегию $\hat{S}$, которая окажется не только сравнимой с $S$ в порядке «с варьируемым составом», но даже будет ее в нем нестрого превосходить: ${S\preccurlyeq}_{Comp}\ \hat{S}$.


Следствие: Между стратегиями $S$ и $ \hat{S}$ также будут выполнятся «неравенства»:
$S\preccurlyeq_N\ \hat{S}$
$S\preccurlyeq\ \hat{S}$

Нам придется отложить доказательство теоремы 4 и прежде несколько подробнее исследовать «экстремальные» свойства последовательностей, наименее предсказуемых последовательностей. Именно этому и посвящен следующий параграф.


Критические последовательности и критические стратегии
Множество всех бинарных последовательностей, состоящих из $A$ «нулей» $B$ «единиц», будем называть композиционным классом этих последовательностей и обозначать его как $\Omega_{A,B}$.

Пусть $S$ — какая-то произвольная стратегия, $\alpha$ — какая-то произвольная последовательность из композиционного класса $\Omega_{A,B}$. Мы будем говорить, что последовательность $\alpha$, является (одной из) наименее предсказуемых относительно относительно $S$ в своем композиционном классе, если (и только если) для любой последовательности $\beta$ из $\Omega_{A,B}$ выполняется неравенство:

$(7)\ \ \ \ \ \ Success(S, \gamma) \le Success(S, \beta)$


Свойство последовательностей: «быть наименее предсказуемыми относительно $S$ в своем композиционном классе», кажется похожим на свойство кривых: «иметь минимальную длину среди кривых с теми же самыми концами». Насколько эта аналогия полна?

Как известно, любой неразрывный участок наикратчайшей кривой сам является наикратчайшим путем между своими концами. Если последовательность $\gamma$ является наименее предсказуемой относительно $S$, должны ли этим свойством обладать и все ее начальные отрезки? Сформулируем вопрос строго.

Для произвольной последовательности $\alpha$ ее $k$-префикс, то есть последовательность, образованную первыми $k$ символами $\alpha$, договоримся обозначать как $\lnot^k(\alpha)$. Пусть $S$ — произвольная стратегия, $\gamma$ — любая последовательность, являющаяся по отношению к $S$ одной из наименее предсказуемых в своем композиционном классе, $k$ — произвольное натуральное число, по величине не превосходящее длину $\gamma$. Будет ли последовательность $\lnot^k(\gamma)$ являться в своем композиционном классе одной из наименее предсказуемых относительно $S$?

Если стратегия $S$ — беспорядковая, то в своем композиционном классе $\lnot^{k}(\gamma)$ обязана быть наименее предсказуемой для $S$ последовательностью. В противном случае мы можем выполнить подходящую перестановку между первыми $k$ символами $\gamma$ и сделать предсказуемость $\lnot^{k}(\gamma)$ строго хуже. Поскольку стратегия $S$ — беспорядковя, то такая перестановка никак не повлияет на вероятности угадывания $S$ элементов $\gamma$, номера которых больше $k$. Отсюда следует, что предсказуемость всей $\gamma$ строго ухудшиться, однако это противоречит предположению, что $\gamma$ относительно $S$ и так была наименее предсказуемой в своем композиционном классе.

В общем случае, когда величины весов «нуля» и «единицы» в предсказаниях $S$ существенно зависят от порядка напечатанных на ленте символов, последнее утверждение, вообще говоря, не верно (Приведите пример). В своем композиционном классе наименее предсказуемые для $S$ последовательности, любой префикс которых в своем композиционном классе также наименее предсказуем для $S$, договоримся называть критическими (для $S$). Если некоторая стратегия такова, что относительно нее любая наименее предсказуемая в своем композиционном классе последовательность является критической, то критической мы также назовем и саму эту стратегию.

Почему вообще может так случится, что имея не самый непредсказуемый префикс, целиком некоторая последовательность $\gamma$ в собственном композиционном классе оказывается наименее предсказуемой для $S$?

Символом $|\gamma|$ в дальнейшем договоримся обозначает длину последовательности $\gamma$. Ситуация, когда $\gamma$ в своем композиционном классе является одной из наименее предсказуемых для $S$, но при этом последовательность $\lnot^{|\gamma|-1}(\gamma)$ таким свойством не обладает, может возникнуть только если стратегия $S$ на аргументе $\lnot^{|\gamma|-1}(\gamma)$ придает уж слишком малый вес тому символу, который стоит в конце $\gamma$.
Ага, кажется есть идея, как это можно было бы исправить!

Для определенности будем считать, что на конце $\gamma$ стоит «ноль». Число «нулей» в $\gamma$ обозначим буквой $A$, а число единиц — буквой $B$. Переберем все наименее предсказуемые для $S$ последовательности, обладающие тем же составов, что и $\lnot^{|\gamma|-1}(\gamma)$, и найдем среди них ту (назовем ее $\eta$), на которой $S$ придаст «нулю» наименьший вероятностный вес, а также ту (назовем ее $\zeta$), на которой $S$ придаст наименьший вероятностный вес «единице». Величину $S^0(\eta)$ обозначим как $p_{A-1,B}$, а величину $S^1(\zeta)$ как $q_{A-1,B}$. Как изменится предсказуемость $\gamma$, если мы переопределим значение $S^0(\lnot^{|\gamma|-1}(\gamma))$ и положим его равным $p_{A-1,B}$?

Среднее количество символов, которые $S$ угадает в $\gamma$ и в $\lnot^{|\gamma|-1}(\gamma)$ связаны между собой отношением:

$(8)\ \ \ \ Success(S,\ \gamma)\ =\ Success(S,\lnot^{|\gamma|-1}(\gamma))\ +S^0(\lnot^{|\gamma|-1}(\gamma))\ $


До переопределения величины $S^0(\lnot^{|\gamma|-1}(\gamma))$ последовательность $\gamma$ имела наименьшую в своем классе предсказуемостью относительно $S$. Может ли тогда $p_{A-1,B}$ быть меньше изначальной величины $S^0(\lnot^{|\gamma|-1}(\gamma))$?

Предположим, что может, то есть, выполняется неравенство:

$ (9)\ \ \ \ p_{A-1,B}< S^0(\lnot^{|\gamma|-1}(\gamma))$


В таком случае припишем к концу последовательности $\eta$ дополнительный «ноль». В результате у нас получится последовательность, которую мы обозначим как $\eta \cdot 0$. Последовательность $\eta \cdot 0$ принадлежит тому же композиционному классу, что и $\gamma$ и отличающаяся от $\gamma$ только, быть может, порядком своих первых $|\gamma|-1=(A+B-1)$ символов. Математическое ожидание количества символов, которые $S$ угадает в $\eta \cdot 0$, задается формулой:

$ (10)\ \ Success(S,\eta \cdot 0) =\ Success(S,\lnot^{A+B-1}(\eta \cdot 0))\ +S^0(\lnot^{A+B-1}(\eta \cdot 0)) = Success(S,\eta)\ + p_{A-1,B}$


Поскольку $\eta$ — одна из наименее предсказуемых для $S$ последовательностей в композиционном классе, которому принадлежит \lnot^{|\gamma|-1}(\gamma), то:

$ (11)\ \ \ \ Success(S,\eta) \le Success(S,\lnot^{|\gamma|-1}(\gamma))$


Объединяя выражения $(8)$ — $(11)$, мы получаем неравенство:

$ (12)\ \ \ \ Success(S,\ \eta \cdot 0)<\ Success(S,\ \gamma)$


однако это неравенство напрямую противоречит изначальному предположению о том, что в своем композиционном классе $\gamma$ является одной из наименее предсказуемых для $S$ последовательностью. Мы пришли к противоречию, а значит доказано, что после переопределения $S^0(\lnot^{A+B-1}(\gamma))$ на $p_{A-1,B}$, предсказуемость $\gamma$ не ухудшиться.

Если бы мы предположили, что $\gamma$ заканчивается «единицей», все наши рассуждения и выводы повторились бы почти дословно. Похоже, что у нас появляется интересный претендент на способ, как как улучшить стратегию $S$. Давайте попробуем его доработать.

Как и прежде $\Omega_{A,B}$ — это множество бинарных последовательностей, составленных из $A$ «нулей» и $B$ «единиц». Через $\Omega_{A,B}^S$ договоримся обозначать множество тех последовательностей в $\Omega_{A,B}$, которые для стратегии $S$ являются наименее предсказуемыми в этом классе. Формально последнее определение означает, что $\Omega_{A,B}^S \subset \Omega_{A,B}$ и для любых $\alpha$ из $\Omega_{A,B}^S$ и $\beta$ из $\Omega_{A,B}$ выполняется неравенство

$(13)\ \ \ \ Success(S, \alpha) \le Success(S,\beta)$


Пусть $\eta_{A,B}$ — это одна из таких последовательностей множества $\Omega_{A,B}^S$, наблюдая которую $S$ назначит «нулю» самый маленький вероятностный вес, то есть:
$\eta_{A,B} \in \Omega_{A,B}^S$ и для любой последовательности $\alpha$ из $\Omega_{A,B}^S$:

$(14a)\ \ \ \ S^0(\eta_{A,B}) \le S^0(\alpha)$


Аналогично, пусть $\zeta_{A,B}$ — это одна из таких последовательностей множества $\Omega_{A,B}^S$, наблюдая которую $S$ назначит «единице» самый маленький вероятностный вес, то есть:
$\zeta_{A,B} \in \Omega_{A,B}^S$ и для любой последовательности $\beta$ из $\Omega_{A,B}^S$ выполняется неравенство

$(14b)\ \ \ \ S^1(\zeta_{A,B}) \le S^1(\alpha)$


Сумма $S^0(\eta_{A,B})$ и $S^1(\zeta_{A,B})$ никогда не превосходит $1$, но и не обязательно ей равна. Если хотя бы одно из этих чисел не ноль, положим

$(15a)\ \ \ \ p_{A,B}=\frac{S^0(\eta_{A,B})}{S^0(\eta_{A,B})+S^1(\zeta_{A,B})}$


$(15b)\ \ \ \ q_{A,B}=\frac{S^1(\zeta_{A,B})}{S^0(\eta_{A,B})+S^1(\zeta_{A,B})}$

в противном случае примем $p_{A,B}=q_{A,B}=1/2$.

Наиболее прямой и напрашивающийся способ улучшить $S$ состоит в следующем.
Пусть $\alpha$ — произвольная последовательность и в ней ровно $A$ «нулей» и $B$ «единиц». Определим стратегию $Improved(S)$ согласно формулам:

$(16)\ \ \ \ \left\{\begin{matrix}{(Improved(S))^0\left(\alpha\right)=p}_{A,B}\ \\{(Improved(S))^1\left(\alpha\right)=q}_{A,B}\\\end{matrix}\right\}$



Теорема 5: Какова бы ни была стратегия $S$, стандартным образом по ней можно построить такую критическую стратегию $\hat{S}$, которая окажется не только сравнимой с $S$ в порядке «с варьируемым составом», но даже будет ее в нем нестрого превосходить: ${S\preccurlyeq}_{Comp} \ \hat{S}$.


Индукцией по длине последовательностей проверим, что в качестве стратегии $\hat{S}$ мы можем взять $Improved(S)$.

Итак нам нужно показать, что:
$1)$ любой префикс всякой наименее предсказуемой для
$Improved(S)$ в своем композиционном классе последовательности — сам является
наименее предсказуемой для $Improved(S)$ в своем композиционном классе
последовательностью;
$2)$ для любых $A$ и $B$ выполняется неравенство
$Inf_{A,B}(S) \le Inf_{A,B}(Improved(S))$

$1)$ доказывается тривиально: стратегия $Improved(S)$ по самому своему определению — беспорядковая, выше мы показали, что все беспорядковые стратегии — критические, значит $Improved(S)$ — критическая.

Пусть $k = A + B$, индукцией по $k$ докажем, что выполняется $2)$.
Когда $k=0$ утверждение $2)$ выполняется тривиальным образом.
Предположим, мы уже доказали, что для всех $l$ и $m$, сумма которых меньше $k$, выполняется неравенство

$Inf_{l,m}(S) \le Inf_{l,m}(Improved(S))$

Пусть $A$ и $B$ — любая пара натуральных чисел (ноль мы тоже считаем натуральным числом), сумма которых равна $k$, проверим, что:

$Inf_{A,B}(S) \le Inf_{A,B}(Improved(S))$



Рассмотрим любую последовательность $\gamma$, которая состоит в точности из $A$ «нулей», $B$ «единиц» и среди таковых является наименее предсказуемой для $S$. Предположим, что $\gamma$ заканчивается «нулем» (Случай, когда на конце $\gamma$ стоит «единица», разбирается точно так же). При сделанном предположении префикс $\lnot^{A+B-1}(\gamma)$ состоит из $(A-1)$-го «нуля» и $B$ «единиц».

Пусть, как и прежде, $\eta$ — это та наименее предсказуемая для $S$ последовательность в классе $\Omega_{A-1,B}$, наблюдая которую $S$ придает нулю наименьший вероятностный вес. Раз так, то последовательность $\eta \cdot 0$ имеет тот же состав, что и $\gamma$, и при этом:

$(17a)\ \ \ \ \ Success(S, \gamma) \le Success(S,\eta \cdot 0)$



Пусть, как и прежде, $\zeta$ — это та наименее наименее предсказуемая для $S$ последовательность $\Omega_{A,B-1}$, наблюдая которую $S$ придает наименьший вероятностный вес «единице». Последовательность $\zeta \cdot 1$ имеет тот же состав, что и $\gamma$, и при этом:

$(17a)\ \ \ \ \ Success(S, \gamma) \le Success(S,\zeta \cdot 1)$



В то же время:

$(18a) \ \ \ \ \ Success(S,\eta \cdot 0) = Success(S,\eta) + S^0(\eta) \le Success(S,\eta) + p_{A-1,B}$


$(18b) \ \ \ \ \ Success(S,\zeta \cdot 1) = Success(S,\zeta) + S^1(\zeta) \le Success(S,\zeta) + q_{A,B-1}$



Пусть $\tau$ — любая последовательность, которая состоит в точности из $A$ «нулей», $B$ «единиц» и среди таковых является наименее предсказуемой уже для $Improved(S)$. Нам придется рассмотреть две альтернативные возможности: либо на конце $\tau$ стоит «ноль», либо ее последний символ — это «единица».

Предположим сначала, что $\tau$ заканчивается нулем. В таком случае ее префикс $\lnot^{A+B-1}(\tau)$ имеет такой же состав как и $\eta$. Более того, стратегия $Improved(S)$ — критическая, поэтому $\lnot^{A+B-1}(\tau)$ является наименее предсказуемой относительно нее последовательностью. По индуктивному предположению:

$(19a) \ \ \ \ \ Success(S, \eta) \le Success(Improved(S), \lnot^{A+B-1}(\tau))$

Согласно определению оператора $Improved()$:

$(20a)\ \ \ \ Success(Improved(S), \tau) = Success(Improved(S), \lnot^{A+B-1}(\tau)) \ +\ p_{A-1,B} $


Объединяя $(17a)$, $(18a)$, $(19a)$ и $(20a)$, получаем требуемое неравенство:

$Success(S, \gamma) \le Success(Improved(S), \tau)$



Пусть теперь $\tau$ заканчивается «единицей». На этот раз префикс $\lnot^{A+B-1}(\tau)$ по составу будет идентичен $\zeta$. Поскольку сам $\lnot^{A+B-1}(\tau)$ снова является наименее предсказуемой относительно $Improved(S)$ последовательностью, то, еще раз воспользовавшись индуктивным предположением, имеем:

$(19b) \ \ \ \ \ Success(S, \zeta) \le Success(Improved(S), \lnot^{A+B-1}(\tau))$

Опять же, по определению оператора $Improved()$:

$(20b)\ \ \ \ Success(Improved(S), \tau) = Success(Improved(S), \lnot^{A+B-1}(\tau)) \ +\ q_{A,B-1} $


Объединяя $(17b)$, $(18b)$, $(19b)$ и $(20b)$, снова получаем, что:

$Success(S, \gamma) \le Success(Improved(S), \tau)$

Индукционный шаг успешно сделан, а значит доказательство теоремы $5$, а заодно и теоремы $4$ ($Improved(S)$ — не только критическая, но еще и беспорядковая) можно считать завершенным.


Выпуклые однородные стратегии и те последовательности, которые им труднее всего предугадать
Если вы ищите стратегию, которая при любом $\delta$ в наименее предсказуемой для нее последовательности с дисбалансом $\delta$ угадывает в среднем как можно большую долю символов, то согласно теоремам 3 и 4 в качестве кандидатов вам достаточно рассмотреть только симметричные и беспорядковые стратегии. Последним объясняется то особое внимание, которое мы в оставшейся части статьи будем уделять классу беспорядковых стратегий. Конкретно в этом параграфе мы займемся изучением таких беспорядковых стратегий, предсказания которых полностью определяются долями «нулей» и «единиц» в уже напечатанной части последовательности. Подобные стратегии договоримся называть однородными.

Итак, если $S$ — однородная страегия, то:

$(21)\ \ \ \begin{matrix}S^0\left(\alpha\right)=S^0(\frac{\left|\alpha\right|_0}{\left|\alpha\right|},\ \frac{\left|\alpha\right|_1}{\left|\alpha\right|})\\S^1\left(\alpha\right)=S^1(\frac{\left|\alpha\right|_0}{\left|\alpha\right|},\ \frac{\left|\alpha\right|_1}{\left|\alpha\right|})\\\end{matrix}$


Последнюю запись можно сделать чуть более удобочитаемой. Для этого договоримся долю «нулей», находящихся на ленте в момент очередного предсказания, обозначать как $P^*$, а «единиц» — как $Q^*$. Теперь условие того, что стратегия $S$ однородна, можно записать так:

$(22)\ \ \ \ \begin{matrix}S^0\left(\alpha\right)=S^0(P^*,Q^*)\\S^1\left(\alpha\right)=S^1(P^*,Q^*)\\\end{matrix}$


Все рассмотренные нами раннее конкретные стратегии: $S_{Coin}$, $S_{Hard}$ и $S_{Soft}$ и $S_{NULL}$ — были однородными.

Чтобы задать конкретную однородную стратегию, вместо двух функции от двух переменных можно использовать всего одну функцию от одной переменной. Действительно:

$(23)\ \ \ \ S^0(P^*,Q^*) + S^1(P^*,Q^*) = 1$


поэтому достаточно задать $S^0(P^*,Q^*)$, далее:

$(24)\ \ \ \ P^*+Q^* = 1$


откуда следует, что фактически $S^0(P^*,Q^*) = S^0(P^*)$. На рисунке 16 показаны графики $S^0(P^*)$ уже хорошо на знакомых стратегий $S_{Coin}$, $S_{Hard}$, $S_{Soft}$ и $S_{NULL}$.

image

рис 16.

Однородную стратегию $S$, совсем не обязательно задавать именно через $S^0(P^*)$: с тем же успехом можно использовать форму представления через $S^0(Q^*)$, $S^1(Q^*)$, или $S^1(P^*)$. Так как весь этот произвол не совсем удобен в нашем стратегическом анализе, попробуем изобрести способ поуниверсальнее. Введем два вспомогательных понятия. Первое из них — это текущий частотный дисбаланс «со знаком»:

$(25)\ \ \ \ {\delta}^* = P^* - 1/2 = - (Q^* - 1/2)$


второе — это дисбаланс «со знаком» между весами «нуля» и «единицы» в очередном предсказании:

$(26)\ \ \ \ {\Delta}^*(\alpha) = S^0(\alpha) - 1/2 = - (S^1(\alpha) - 1/2)$


При заданных $S^0(\alpha) = S^0(P^*,Q^*)$ и $S^1(\alpha) = S^1(P^*,Q^*)$ величина ${\Delta}^*$ оказывается связанной с ${\delta}^*$ строгой функциональной зависимостью:

$(27) \ \ \ \ \ \Delta^\ast({\ \delta}^\ast)=S^0\left(\frac{1}{2}\ +{\ \delta}^\ast,\frac{1}{2}\ {-\ \delta}^\ast\right)-\frac{1}{2}$


С другой стороны, если задана функция зависимости $\Delta^\ast({\ \delta}^\ast)$, то тем самым полностью определены и функции $S^0(P^*,Q^*)$ и $S^1(P^*,Q^*)$:

$(28) \ \ \ \ \begin{matrix}S^0\left(P^*,Q^*\right)=\frac{1}{2}+\Delta^\ast(P^*-\frac{1}{2})\\S^1\left(P^*,Q^*\right)=\frac{1}{2}-\Delta^\ast(P^*-\frac{1}{2})\\\end{matrix}$


Таким образом, если стратегия однородная, то она полностью описываются своей «дельта»-функцией $\Delta^\ast({\ \delta}^\ast)$. Однородная стратегия $S$ будет симметричной тогда (и только тогда), когда ее «дельта»-функция является нечетной: $\Delta^\ast({\ \delta}^\ast)= - \Delta^\ast({ - \ \delta}^\ast)$ (проведите рассуждения строго). На рисунке 17 приведены графики $\Delta^\ast({\ \delta}^\ast)$ все тех же $S_{Coin}$, $S_{Hard}$, $S_{Soft}$ и $S_{NULL}$.

image

рис 17

Перейдем теперь к действительно интересному вопросу. В первой части статьи было доказано, что в достаточно длинной последовательности с относительно небольшим дисбалансом $\delta$ однородная стратегия $S_{Soft}$ даже в худшем для себя сценарии должна отгадать примерно на $N \cdot 2\delta^2$ символов больше ($N$ — длина последовательности), чем стратегия $S_{Coin}$ (смотрите формулу $(15a)$ основного раздела и график на рисунке $10$).
Нельзя ли улучшить этот результат?

Давайте попробуем дать простое объяснение, почему вообще некоторым стратегиям удается угадывать больше, чем предсказанию с помощью монетки? Пусть $\alpha$ — это любая последовательность, в которой число «нулей» значимо превосходит число «единиц». Если так, то число «нулей» должно быть больше числа «единиц» также и во всех префиксах $\lnot^k {\alpha}$ начиная с некоторого значения $k=k_0$. Отслеживая частоту употребления «нулей» и «единиц» в префиксах, мы можем надеяться понять, который из символов будет преобладать в итоговой последовательности и тем самым суметь вовремя скорректировать свои прогнозы на более удачные.

Из такого объяснения следует, что чем чаще встречается символ в уже напечатанной части последовательности, тем больший вероятностный вес стоит ему придать в следующем предсказании. Другими словами величина дисбаланса между весами «нуля» и «единицы» ${\Delta}^*$ в очередном предсказании должна быть тем больше, чем больший дисбаланс ${\delta}^*$ наблюдается между их частотами в уже напечатанном фрагменте угадываемой последовательности.

Интуитивно должно быть понятно, что чем активнее реагирует ${\Delta}^*$ на изменения ${\delta}^*$, тем большую выгоду должна извлечь стратегия из дисбаланса итоговой последовательности. Если на протяжении всего процесса печатанья наблюдаемый частотный дисбаланс ${\delta}^*$ остается все время мал, то вполне очевидно, что в этом эксперименте чувствительность стратегии к изменениям ${\delta}^*$ главным образом определяется значением производной ${d\Delta^\ast}/{d\delta^\ast}$ при $\delta^\ast = 0$

Вернемся к стратегии $S_{Soft}$. Производная ее «дельта»-функции в нуле (смотри рис 17) равна $1$. Мы знаем, что наихудшие свои результаты $S_{Soft}$ показывает на пульсирующих последовательностях префиксного типа. Если дисбаланс пульсирующей последовательности мал, то мал также будет дисбаланс и любого ее префикса. Предположим, что мы хотим научится угадывать больше символов в пульсирующих последовательностях с малым дисбалансом. В таком случае сама собой возникает идея:
" А нельзя ли переопределить «дельта»-функицию стратегии $S_{Soft}$ так, чтобы ее производная в нуле возросла?"

Прежде чем брать в руки карандаш и начинать чертить графики давайте перечислим некоторые самые простые ограничениях на вид ${\Delta^\ast}({\delta^\ast})$.
$a)$ Мы знаем, что нет смыла рассматривать несимметричные стратегии, поэтому после переопределения ${\Delta^\ast}({\delta^\ast})$ — должна остаться нечетной функцией равной $0$ в нуле;
$b)$ Разумно рассматривать только строгомонотонные зависимости $\Delta^\ast$ от $\delta^\ast$
$c)$ Область определения ${\Delta^\ast}({\delta^\ast})$ является отрезком $[ -1/2 , \ 1/2]$. Поскольку ее значения — это дисбаланс вероятностных весов, то они не могут быть больше $1/2$ или меньше $-1/2$;
$d)$Если до настоящего момента на ленте печатались символы только одного типа (например, только «единицы»), то вполне разумно предположить, что следующий элемент последовательности будет символом того же типа. Как следствие, мы можем рассматривать лишь такие функции, для которых ${\Delta^\ast}(-1/2) = -1/2$ и ${\Delta^\ast}(1/2) = 1/2$.

При попытке удовлетворить всем перечисленным условиям я попробовал нарисовать график и то, что у меня вышло, вы видите на рисунке 18.

image

рис 18

Упражнение 1: Пусть однородная стратегия $S$ такова, что производнаяs ${\Delta^\ast}({\delta^\ast})$ в точке $0$ равна $\lambda$. Пусть, также, $\alpha$ — это любая пульсирующая последовательность префиксного типа, дисбаланс $\delta$ которой мал по сравнению с единицей. Покажите, что с точностью до членов малости более высокого порядка

$(29)\ \ \ \ Success\left(S,\ \alpha\right)\approx\ \frac{1}{2}\ +\ \lambda\cdot2\delta^2\ -\ \lambda\cdot\frac{\ln(N/2)}{4N}$


Упрощенно можно сказать так: вместе с увеличением производной ${\Delta^\ast}({\delta^\ast})$ в точке $\delta^\ast=0$ способность однородных стратегий предугадывать пульсирующие последовательности и «штраф», который они получают за адаптацию, — растут пропорционально друг другу.

Глядя на рисунок 19 трудно не заметить, что правая часть графика почти естественно получается выпуклой вверх, а левая не менее естественно — выпуклой в низ. Однородные стратегии, у которых «дельта»-функции обладают описанным свойством, договоримся называть выпуклыми. Для однородной стратегии совсем не обязательно, чтобы ее функция ${\Delta^\ast}({\delta^\ast})$ правей нуля была выпуклой вверх, а левее — выпуклой вниз. Если постараться, можно начертить и по-другому (рис 19):

image

рис 19

Тем не менее, выпуклые стратегии «естественны» и к тому же легко поддаются анализу, поэтому оставшуюся часть параграфа мы посвятим именно им.

Как было сказано выше (упражнение 1), однородные стратегии (в частности выпуклые однородные стратегии) тем лучше отгадывают малодисбалансные пульсирующие последовательности, чем больше у этих стратегий производная их «дельта»-функции в нуле. Однако в рамках нашего исследования куда интереснее было бы ответить на другой вопрос:
«Каким образом величина $d\Delta^\ast/d\delta^\ast|_{\delta^\ast=0}$
сказывается на эффективности угадывания символов в наименее предсказуемых для данной стратегии последовательностях и, собственно, каков у этих наименее предсказуемых последовательностей вид?» Эти ответы содержаться в следующей

Теорема 6: Пусть $S$ — произвольная выпуклая и симметричная стратегия. Бинарная последовательность $\alpha$, состоящая из $A$ «нулей» и $B$ «единиц» $ B \le A $, тогда и только тогда будет наименее предсказуемой для $S$ в своем композиционном классе, когда:
$a)$ последние $(A-B)$ позиций $\alpha$ заняты «нулями»;
$b)$ первые ее $2B$ элементов представляют из себя $B$ последовательно расположенных пар «нуля» и «единицы», порядок символов в каждой паре может быт выбран произвольным.


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

Теорема $6$ как две капли воды схожа с теоремой $1$, доказываются они тоже схожим способом.
Пусть $S$ — произвольная однородная выпуклая стратегия, а $\alpha$ — последовательность, которая в своем композиционном классе для $S$ является одной из наименее предсказуемых. Число «нулей» в $\alpha$ обозначим буквой $A$, а число «единиц» — буквой $B$. Для начала покажем, что если $B<A$, то на конце $\alpha$ обязан стоять «ноль».

Чтобы в последствии прийти к противоречию, предположим, что на конце $\alpha$ стоит «единица».
Пусть $k$ — это позиция самого правого нуля в $\alpha$, тогда последовательность $\beta=\lnot^{k + 1}(\alpha)$ заканчивается на $"...01"$ и ее можно представить как $\beta=\lnot^{k - 1}(\alpha) \cdot 01 $. Последовательность $\beta$ включает в себя ровно $A$ «нулей» и ровно $B' = B - (A+B - k - 1)$ «единиц». Так как $B' \le B$ и $B<A$, то $B'<A$, то есть, количество «нулей» в $\beta$ строго больше числа содержащихся в ней «единиц». Поскольку стратегия $S$ — беспорядковая, то $\beta=\lnot^{k + 1}(\alpha)$ является в своем композиционном классе одной из наименее предсказуемых для $S$. Последовательность $\lnot^{k - 1}(\alpha) \cdot 10 $, полученную из $\beta$ перестановкой ее двух последних символов, обозначим как $\beta'$. Последовательности $\beta$ и $\beta'$ имеют одинаковый состав, поэтому принадлежат одному и тому же композиционному классу. Cравним, насколько различаются математические ожидания числа тех символов, которые $S$ сможет угадать в каждой из них.

Очевидно, что перестановка $k$-го $k+1$-го элементов никак не повлияет на среднее
число символов, которые $S$ угадает среди первых $k-2$ элементов этих последовательностей, и нам остается только посчитать, какие различия возникнут на двух последних элементах.

В последовательности $\beta$ стоящий на предпоследнем месте «ноль» стратегия $S$ угадает с вероятностью

$(30)\ \ \ \ \frac{1}{2}+\Delta^\ast\left(\frac{(A-1)-(B^\prime-1)}{2\cdot(k-1)}\right)$


а стоящую на последнем месте единицу — с вероятностью

$(31)\ \ \ \ \frac{1}{2}-\Delta^\ast\left(\frac{A-(B^\prime-1)}{2k}\right)$


Средняя эффективность $S$ на $\beta$ будет выражаться как

$(32)\ \ \ \ Success(S, \beta)=Success(S, \lnot^{k - 1}(\alpha))+1+\Delta^\ast\left(\frac{A-B^\prime}{2\cdot(k-1)}\right)-\Delta^\ast\left(\frac{A-B^\prime+1}{2k)}\right)$


Если выполнить транспозицию, то шансы угадать ноль станут равными

$(33)\ \ \ \ \frac{1}{2}+\Delta^\ast\left(\frac{(A-1)-B^\prime}{2k)}\right)$


а шансы угадать единицу —

$(34)\ \ \ \ \frac{1}{2}-\Delta^\ast\left(\frac{(A-1)-(B^\prime-1)}{2\cdot(k-1)}\right)$


Таким образом средняя эффективность $S$ на $\beta'$ составит

$(35)\ \ \ \ Success(S, \beta')=Success(S, \lnot^{k - 1}(\alpha))+1-\Delta^\ast\left(\frac{A-B^\prime}{2\cdot(k-1)}\right)+\Delta^\ast\left(\frac{A-B^\prime - 1}{2k}\right)$


Соответственно прирост эффективности $Success(S, \beta') - Success(S, \beta)$, вызванный перестановкой, окажется равным

$(36)\ \ \ \ \Delta^\ast\left(\frac{A-B^\prime}{2k}+\frac{1}{2k}\right)\ +\ \Delta^\ast\left(\frac{A-B^\prime}{2k}-\frac{1}{2k}\right)-2{\Delta}^\ast\left(\frac{A-B^\prime}{2\cdot(k-1)}\right)$


Как известно, если некоторая функция $f(x)$ выпукла вверх, то для любых $X_1$ и $X_2$ из области ее определения выполняется неравенство

$(37)\ \ \ \ \ \frac{f\left(X_1\right)+f(X_2)}{2}\le f\left(\frac{X_1+X_2}{2}\right)$


Доказательством может служить рисунок 20.

image

рис 20

Функция $\Delta^\ast()$ по условиям — выпуклая вверх. Согласно (37)

$(38)\ \ \ \ \ \Delta^\ast\left(\frac{A-B^\prime}{2k}+\frac{1}{2k}\right)\ +\ \Delta^\ast\left(\frac{A-B^\prime}{2k}-\frac{1}{2k}\right)\ \le\ 2\Delta^\ast\left(\frac{A-B^\prime}{2k)}\right)$


Если подставить (38) в (36), мы получим неравенство:

$(39)\ \ \ \ \ Success\left(S,\beta^\prime\right)-Success\left(S,\beta\right)\le2\Delta^\ast\left(\frac{A-B^\prime}{2k}\right)-2\Delta^\ast\left(\frac{A-B^\prime}{2(k-1)}\right)$


Так как функция $\Delta^\ast()$ — строго возрастающая и

$(40)\ \ \ \ \ \ \frac{A-B^\prime}{2k}<\frac{A-B^\prime}{2(k-1)}$


то

$(41)\ \ \ \ \ \ \Delta^\ast\left(\frac{A-B^\prime}{2k}\right)<\Delta^\ast\left(\frac{A-B^\prime}{2(k-1)}\right)$


а значит

$(42)\ \ \ \ \ \ Success\left(S,\beta^\prime\right)-Success\left(S,\beta\right)<0$


Неравенство $(42)$ говорит нам о том, что $\beta$, то есть $\lnot^{k + 1}(\alpha)$, не в своем композиционном классе является наименее предсказуемой относительно $S$, но такое возможно, только если сама $\alpha$ в ее композиционном классе вопреки сделанному вначале предположению не является наименее предсказуемой относительно $S$.

Полученное противоречие показывает, что

$i)$ Если последовательность является в своем композиционном классе наименее предсказуемой для какой-нибудь выпуклой стратегии, то она обязательно заканчиваться наиболее распространенным в ней символом. Если же в такой последовательности количество «нулей» и «единиц» одинаково, то последние два ее элемента есть либо $"...01"$, либо — $"...10"$.

Возьмем любую стратегию $S$, которая является не только выпуклой, но в добавок еще и симметричной и любую наименее предсказуемую в своем композиционном классе для $S$ последовательность, составленную из равного числа «нулей» и «единиц». Как было сказано выше, на конце такой последовательности стоит либо $"...01"$, либо $"...10"$. Предположим, что выбранная нами последовательность заканчивается на $"...01"$. Поскольку $S$ однородна и симметрична, то поменяв местами два последних символа, мы снова получим наименее предсказуемую относительно $S$ последовательность. Таким образом,

$ii)$ если стратегия $S$ выпукла и симметрична, а $\alpha$ — любая наименее предсказуемая в своем композиционном классе для $S$ последовательность, составленная из равного числа «нулей» и «единиц», то обе последовательности:
$\lnot^{|\alpha| -2}(\alpha) \cdot 01$ и
$\lnot^{|\alpha| -2}(\alpha) \cdot 10$
— оказываются наименее предсказуемыми относительно $S$ в их композиционном классе.

Оставшаяся часть доказательства полностью повторяет доказательство теоремы $1$. С помощью $i)$ устанавливается, что любая последовательность из $A$ «нулей» и $B$, меньшего $A$, «единиц», будь она в своем композиционном классе наименее предсказуемой относительно некоторой выпуклой и симметричной стратегии $S$, на последних $A-B$ позициях содержит только «нули». Далее применяя $ii)$, доказывается, что первые $2B$ позиций в такой последовательности заняты последовательно идущими парами, каждая из которых включает ровно один «ноль» и ровно одну «единицу», неважно в каком порядке.


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

«Серебряную пулю» предложить вам у меня не получится, однако я разберу стратегию, которая по величине выигрыша в своем наихудшем сценарии примерно равна $S_{Coin}$, а по эффективности угадывания символов в последовательностях, имеющих существенный дисбаланс, — в некотором смысле значительно превосходит стратегии $S_{Soft}$ и $S_{Hard}$.

Итак, рассмотрим однородную, выпуклую симметричную стратегию $S_{Sqrt}$, у которой дисбаланс весов «нуля» и «единицы» в очередном предсказании определяется как знаковый квадратный корень из половины текущего дисбаланса частот. Другими словами «дельта»-функция $S_{Sqrt}$ вид:

$(43)\ \ \ \ \Delta^\ast\left(\delta^\ast\right)=\pm\sqrt{\frac{\delta^\ast}{2}}$


где функция $\pm\sqrt x$ — есть нечетное продолжение обычной функции $\sqrt x$, заданная по правилу:
$\pm\sqrt x = \sqrt x$, если $x \geq 0 $ и
$\pm\sqrt x = - \sqrt |x|$, если $x < 0 $.

Давайте найдем, чему равен наихудший средний результат $S_{Sqrt}$ в классе последовательностей, состоящих из $B = (1/2 + \delta) \cdot N$ «единиц» и $A = (1/2 - \delta) \cdot N$ «нулей».

Поскольку $S_{Sqrt}$ — выпуклая, то одной из наименее предсказуемых для нее последовательностей в классе $\Omega_{A,B}$ будет пульсирующая последовательность префиксного типа: $\alpha="1010...10111...111"$.

Каждую из $A$ «единиц», расположенных на участке пульсации, стратегия $S_{Sqrt}$ угадает с вероятностью $1/2$. На момент, когда будет делаться прогноз для $k+1$-вого по счету нуля, на ленте уже будут присутствовать $k$ «нулей» и $k+1$ «единица», создавая тем самым наблюдаемый дисбаланс

$(44)\ \ \ \ \ \ {\delta}^\ast=-\frac{1}{2(2k+1)}$


Шансы, с которыми этот прогноз окажется верным равны

$(45)\ \ \ \ \ \ \frac{1}{2}-\sqrt{\frac{1}{4(2k+1)}}$


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

$(46)\ \ \ \ \frac{A}{2}+\frac{A}{2}-\frac{1}{2}\cdot\sum_{k=0}^{A-1}\frac{1}{\sqrt{2k+1}}$



Теперь займемся «гомогенным» постфиксом $\alpha$. Перед тем, как будет напечатана $i+1$ из последних $(B-A)$ «единиц», на ленте будут находится $A$ «нулей» и $A+i$ «единиц», создавая своим присутствием наблюдаемый дисбаланс

$(47)\ \ \ \ \ {\delta}^\ast=-\frac{i}{2(i+2A)}$


Шансы, что сделанный в этот момент прогноз окажется правильным, составят

$(48) \ \ \ \ \ \frac{1}{2}+\sqrt{\frac{i}{4(i+2A)}}$


Таким образом математическое ожидание числа угаданных на гомогенном участке символов окажется равным:

$(49)\ \ \ \ \ \frac{(B-A)}{2}+\frac{1}{2}\cdot\sum_{i=0}^{B-A-1}\sqrt{\frac{i}{i+2A}}$


Объединяя вместе $(46)$ и $(49)$, мы получаем, что математическое ожидание числа угаданных символов на всей протяженности $\alpha$ равно

$(50)\ \ \ \ Success\left(S_{Sqrt},\ \alpha\right)=\ \frac{A+B}{2}+\frac{1}{2}\cdot\left(\sum_{i=0}^{B-A-1}\sqrt{\frac{i}{i+2A}}\right)-\frac{1}{2}\cdot\left(\sum_{k=0}^{A-1}\frac{1}{\sqrt{2k+1}}\right)$


Более-менее очевидно и это следует из $(50)$, что при фикксированном значении длинны пульсирующих последовательностей $N=A+B$ наименее предсказуемыми
для $S_{Sqrt}$ будут последовательности с нулевым дисбалансом, то есть такие, у которых $A=B$. В этом частном случае $(50)$ превращается в:

$(51)\ \ \ \ Success\left(S_{Sqrt},\ \alpha\right)=\frac{N}{2}-\frac{1}{2}\cdot\left(\sum_{k=0}^{N/2-1}\frac{1}{\sqrt{2k+1}}\right)$


Стоящая в конце $(51)$ сумма, по сути является штрафом за адаптацию. Для больших по значению $N$ его довольно точно можно оценить интегралом:

$(52)\ \ \ \ penalty\left(N\right)=\frac{1}{2}\cdot\sum_{k=0}^{N/2-1}\frac{1}{\sqrt{2k+1}}\approx\ \frac{1}{2}\int_{0}^{N/2}\frac{dt}{\sqrt{2t+1}}=\frac{1}{2}\int_{1}^{N+1}\frac{du}{2\sqrt u}\approx\frac{\sqrt N}{2}$


Вспомним теперь о стратегии $S_{Coin}$. Каждое ее предсказание — это «ноль» и «единица», взятые с вероятностями весами 1/2. Независимо от конкретного вида печатаемой на ленте последовательности, очередной ее элемент $S_{Coin}$ угадает с вероятностью 50%. В среднем в последовательности длинны $N$ правильно угаданными окажутся $N/2$ элементов, причем для больших $N$ их число будет иметь распределение близкое к нормальному со средним $N/2$ и стандартным отклонением $(\sqrt N)/2$.

Смотрите, что выходит: в своих наихудших сценариях математические ожидания эффективности $S_{Sqrt}$ и $S_{Coin}$ отличаются друг от друга на величину порядка их дисперсий, то есть по большому счету оказываются несущественными.

Теперь постараемся понять, как много стратегии $S_{Sqrt}$ удается отгадать символов в тех последовательностях, внутри которых между «нулями» и «единицами» присутствует значимый дисбаланс. Стратегия $S_{Sqrt}$ симметрична, поэтому ${Inf}_{A,B}\left(S_{Sqrt}\right) = {Inf}_{B,A}\left(S_{Sqrt}\right)$. Обе эти величины договоримся обозначать как ${Inf}_{[N,\delta]}\left(S_{Sqrt}\right)$. Перепишем $(50)$ в эквивалентной форме:

$(50^*)\ \ Success\left(S_{Sqrt},\ \alpha\right)=\ \frac{N}{2}+\frac{1}{2}\cdot\left(\sum_{i=0}^{2N|\delta| - 1}\sqrt{\frac{i}{i+N(1-2|\delta|)}}\right)-\frac{1}{2}\cdot\left(\sum_{k=0}^{N(1/2-|\delta|)-1}\frac{1}{\sqrt{2k+1}}\right)$


Поскольку $\alpha$ является для $S_{Sqrt}$ одной из наименее предсказуемых последовательностей в своем композиционном классе, то ${Inf}_{[N,\delta]}\left(S_{Sqrt}\right)=\ \frac{1}{N}Success\left(S_{Sqrt},\ \alpha\right) $, или:

$(53)\ \ \ {Inf}_{[N,\delta]}\left(S_{Sqrt}\right)=\ \frac{1}{2}+\frac{1}{2N}\cdot\left(\sum_{i=0}^{2N |\delta| -1}\sqrt{\frac{i}{i+N(1-2|\delta| )}}\right)-\frac{1}{2N}\cdot\left(\sum_{k=0}^{N(1/2-|\delta|) -1}\frac{1}{\sqrt{2k+1}}\right)$


Выражение для ${Inf}_{[N,\delta]}\left(S_{Sqrt}\right)$ оказывается составленной из трех слагаемых. Первое слагаемое:

$(54a)\ \ \ \ \ \ +\frac{1}{2}$


— это базовая эффективность, которую можно получить безо всякой адаптации. Второе:

$(54b)\ \ \ \ \ \ +\frac{1}{2N}\cdot\left(\sum_{i=0}^{2N |\delta| -1}\sqrt{\frac{i}{i+N(1-2|\delta|)}}\right)$


— положительная прибавка связанная с адаптацией. Последнее слогаемое:

$(54c)\ \ \ \ \ \ \frac{1}{2N}\cdot\left(\sum_{k=0}^{N(1/2-|\delta|) -1}\frac{1}{\sqrt{2k+1}}\right) \le \frac{1}{2N}\cdot\sum_{k=0}^{N/2-1}\frac{1}{\sqrt{2k+1}} \approx\frac{1}{2\sqrt N}$


— входит в $(54)$ со знаком «минус», представляя собой штраф за адаптацию.
Когда $N$ стремится к бесконечности, а $\delta$ остается фиксированным, первое слагаемое никак не изменяется, третье стремится к нулю (равномерно по $\delta$). Выясним, как ведет себя второе слагаемое. Перепишем $(54b)$ в виде

$(54b^*)\ \ \ \ \ \ \frac{1}{2}\cdot\sum_{i=0}^{2N|\delta|-1}\left(\sqrt{\frac{i/N|\delta|}{1/|\delta|-2+i/N|\delta|}}\cdot\frac{1}{N|\delta|}\right)$


Если $N$ велико, то $(54b^*)$ можно с хорошей точностью заменить интегралом:

$(55)\ \ \ \ \ \ \frac{|\delta|}{2}\cdot\int_{0}^{2}{\sqrt{\frac{t}{1/|\delta|-2+t}}dt}$


который от $N$ никак не зависит. Таким образом при больших $N$:

$(56)\ \ \ \ \ \ {Inf}_{[N,\delta]}\left(S_{Sqrt}\right)\approx\frac{1}{2}+\frac{|\delta|}{2}\cdot\int_{0}^{2}{\sqrt{\frac{t}{1/|\delta|-2+t}}dt}={\rho}_{Success}(\delta)$


График $\rho (\delta)$ представлен ниже на рисунке $21$

рис 21.
Если сравнить графики на рисунках $10$ и $21$, то можно заметить, что график функция $ {\rho}_{Success}(\delta) $ у стратегии $S_{Sqrt}$ проходит заметно ближе к прямой $y=1/2 + \rho$, чем тот же график у стратегии $S_{Soft}$. При малых по модулю $\delta$ знаменатель подкоренного выражения в $(56)$ равен примерно $1/|\delta|$ а сама функция $F(\delta)$:

$(57)\ \ \ \ \ {\rho}_{Success}(\delta)\approx\frac{1}{2}+\frac{|\delta|}{2}\cdot\int_{0}^{2}{\sqrt{\frac{t}{1/|\delta|}}dt}=\frac{1}{2}+\frac{2\sqrt2}{3}\cdot|\delta|\sqrt{|\delta|}$


то есть прибавка к базовым 50% угаданных символов у стратегии $S_{Sqrt}$ асимптотически больше чем квадратичная прибавка $2{\delta}^2$, которую обеспечивает стратегия $S_{Soft}$.

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


К горизонтам новых знаний


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

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

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

Каким образом можно было бы преодолеть описанные трудности?

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

У бинарных цепочек есть такое количественное свойство — величина дисбаланса между частотами содержащихся в них «нулей» и «единиц». По условию мы не знали, в какой мере печатаемая на ленте последовательность должна им обладать, однако это не мешало нам взять монетку и с ее помощью гарантированно угадать в среднем половину всех символов. Не обязательно было угадывать с помощью монетки: нам разрешалось самим построить стратегию. Если дисбаланс в последовательности велик, то желательно было, чтобы средняя доля символов, которые в итоге угадает выбранная нами стратегия, была как можно больше $1/2$, а если дисбаланс окажется мал, то желательно, чтобы эта доля по сравнению с $1/2$-ой была не слишком мала. В итоге мы построили несколько эффективных стратегий, основывавшихся на подсчете статистик в доступном наблюдению участке последовательностей. По сути статистические методы получилось применить там, где никакой случайности не предполагалось.

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

$1)$ Нужно предложить какой-то способ для выражения оценки неизвестного числа. Пока не ясно, чем она должна являться: тоже числом, распределением или иным математическим объектом.
$2)$ Необходимо будет определится с тем, к каким именно количественным свойствам действительнозначных последовательностей мы будем приспосабливаться. Выбор конкретного свойства или набора свойств зависит от рассматриваемой практической задачи, и было бы неплохо накопить много разобранных примеров.
$3)$ Если уже определены типы количественных свойств, по которым предстоит вести адаптацию, и способ выражения предиктивных оценок, то можно перебирать и анализировать предиктивные стратегии с тем, чтобы найти среди них лучшую или по крайней мере приемлемую. Здесь возникают еще две задачи. Первая — это предложить количественную меру того, насколько конкретная стратегия хорошо оценивает конкретную известную последовательность. Вторая задача задача состоит в том, чтобы предложить способ сравнения разных предиктивных стратегий в условиях, когда наперед не известно, какую именно последовательность им предстоит оценивать.

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

Благодарю за внимание и желаю удачи!
Сергей Коваленко.

2020 год
magnolia@bk.ru


(Pioneer-10 на фоне Юпитера)
Теги:
Хабы:
Всего голосов 20: ↑19 и ↓1+46
Комментарии28
23
Карма
0
Рейтинг
@Sergey_Kovalenko

Пользователь

Отправить сообщение

Публикации

Истории

Работа

Data Scientist
76 вакансий

Ближайшие события

8 октября – 4 декабря
ТурбоХакатон «Решения для электроэнергетики на базе искусственного интеллекта»
Онлайн
Больше событий в календаре
Разработка
Другое
5 – 17 ноября
Вайб-чек для бэкендеров на Хабр Карьере
Онлайн
Больше событий в календаре
Разработка
14 ноября
Конференция «ViRush 2024: BigData, ИИ и новые практики работы с BI»
Москва
Больше событий в календаре
Разработка
Аналитика
14 ноября
Вебинар «Как подтвердить знания про облака: анонс новых курсов и сертификации»
Онлайн
Больше событий в календаре
Разработка
Другое
15 – 16 ноября
IT-конференция Merge Skolkovo
Москва
Больше событий в календаре
Разработка
Маркетинг
Другое
20 ноября
Конференция InterComm «Рождение Титанов»
Москва
Больше событий в календаре
Менеджмент
Другое
22 – 24 ноября
Хакатон «AgroCode Hack Genetics'24»
Онлайн
Больше событий в календаре
Разработка
Другое
28 ноября
Конференция «TechRec: ITHR CAMPUS»
Москва • Онлайн
Больше событий в календаре
Менеджмент
Другое
25 – 26 апреля
IT-конференция Merge Tatarstan 2025
Казань
Больше событий в календаре
Разработка
Маркетинг
Другое

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2024, Habr