В свое время в учебнике по теории вероятностей (Розанов Ю.А. Лекции по теории вероятностей, М.: Наука, 1968) особое внимание автора привлекла задача о наилучшем выборе. Эта задача заключается в том, что наблюдатель, руководствуясь своими критериями, должен выбрать из совокупности n предметов один – самый лучший, последовательно просматривая их друг за другом. Важной особенностью этой задачи является то обстоятельство, что, отвергнув уже рассмотренный предмет, к нему нельзя вернуться вновь. Из этого следует, что наблюдатель, сам того не ведая, может отвергнуть наилучший предмет в надежде найти еще более лучший при дальнейшем осмотре. Кроме того, для наблюдателя было бы неестественно останавливать свой выбор на предмете, который заведомо хуже какого-нибудь уже рассмотренного предмета. Таким образом, при последовательном просмотре имеющегося набора предметов наблюдатель может выбрать первый из них (и на этом дальнейший осмотр заканчивается), либо он будет продолжать перебор предметов до тех пор, пока на каком-то этапе ему не попадется предмет, который лучше осмотренных ранее. Наблюдатель может выбрать этот предмет (и тогда дальнейший осмотр завершается) или же продолжать осмотр с тем, чтобы выбрать предмет еще лучше и т.д.
Итак, в процессе перебора наблюдатель несет риск того, что может быть отвергнут самый лучший предмет, и тогда он либо уже ничего не выберет, либо ему придется довольствоваться самым последним, но, скорее всего, не самым лучшим предметом. В то же время, если количество предметов велико, то может оказаться нецелесообразным ограничиться первым попавшимся предметом и не попытать счастья найти, что-нибудь еще лучше.
Аналогичную задачу приходится решать и трейдеру, который торгует только в одну сторону – либо только продает, либо только покупает. Когда он продает, он должен постараться выявить максимальную цену дня, а когда покупает – его задача определить самую низкую цену дня. При этом он несет все те риски, которые нес и упомянутый выше наблюдатель: то есть, покупая, трейдер может упустить самую низкую цену в надежде встретить цену еще более низкую и, наоборот, при продаже может быть упущена самая высокая цена в расчете на то, что встретится еще более высокая цена. Точно также трейдер не может вернуться к лучшей цене, если она встречалась, ибо удачный момент уже канул в прошлое.
И все-таки, несмотря на похожесть и родство обеих задач, между ними есть и отличия.
В вышеназванном учебнике при рассмотрении описанной задачи ставился вопрос: если наблюдатель сделал свой выбор на k-м предмете, который оказался лучше всех предыдущих (поэтому-то на него и пал выбор), то какова вероятность того, что этот выбранный предмет окажется наилучшим среди всей совокупности как уже осмотренных, так и еще не осмотренных предметов? Ответ на поставленный вопрос находится следующим образом.
Рассмотрим два события:
1) событие B заключается в том, что из k рассмотренных предметов последний оказался самым лучшим, причем наблюдателю известно, что это событие произошло;
2) событие A состоит в том, что k-й по счету предмет оказался лучшим во всей совокупности предметов; к сожалению, об этом можно судить только после того, как просмотрена вся последовательность предметов.
Необходимо узнать, какова условная вероятность события A, если известно, что событие B произошло? На языке математики такая условная вероятность записывается как P(A|B). Она находится по известной формуле условной вероятности:
P(A|B) = P(AB)/P(B),
где в числителе вероятность пересечения событий A и B (то есть вероятность того, что осуществляется и событие A, и событие B одновременно), а в знаменателе вероятность события B. Понятно, что в нашем случае событие A содержится в B, а потому пересечение событий A и B совпадает с событием A, то есть P(AB) = P(A). Считается, что все возможные расположения предметов равновероятны. Вероятность события B равняется вероятности того, что при случайной перестановке k отличимых друг от друга предметов на порядковом месте k окажется наилучший. Эта вероятность равна (k–1)!/k!, где k! – общее число перестановок из k предметов, а (k–1)! – число перестановок из первых (k–1) предметов, при условии, что на k-м месте закреплен наилучший. Другими словами, P(B) = (k–1)!/k! = 1/k.
Точно также находится вероятность события A – она равняется вероятности того, что при случайной перестановке n отличимых друг от друга предметов на порядковом месте k окажется вполне конкретный – наилучший – предмет из всей совокупности рассматриваемых предметов. Так что P(A) = (n–1)!/n! = 1/n. Соответственно, искомая условная вероятность
P(A|B) = P(AB)/P(B) = P(A)/P(B) = k/n.
Отсюда становится ясно, что чем больший порядковый номер имеет наилучший предмет из всех уже просмотренных, тем больше вероятность, что он окажется лучшим и во всей совокупности. Вот почему было бы неразумно ограничиваться выбором первого предмета. Рассмотренная задача представляет собой пример случайного поиска.
Особенности одностороннего трейдинга
Теперь от сугубо математической задачи перейдем к конкретным проблемам, с которыми сталкивается трейдер в ходе односторонней торговли. В ходе торговли для трейдера было бы не слишком приемлемо опираться на случайный поиск. Было бы гораздо лучше, если бы он мог руководствоваться детерминированными методами. Возможно ли такое?
Чтобы говорить конкретно, представим себе условный пример, в котором трейдер должен в течение определенного периода времени продать имеющиеся у него доллары за рубли. В начале каждого торгового периода трейдер получает текущую котировку и должен сделать выбор: принять ее или же подождать более выгодного курса. Однако в отличие от задачи, рассмотренной во введении, трейдер в общем случае имеет возможность разделить начальное количество долларов на части и осуществлять их продажу последовательно – каждую часть по своему обменному курсу. Понятно, что такая более общая схема торговли может привести к более высокой прибыли.
Нетрудно догадаться, что эффективность выполнения трейдером всего торгового задания, будет определяться количеством рублей, которое он получит после окончания торгового периода в результате продажи долларов. При этом чтобы не усложнять анализа, мы не будем здесь учитывать возможность инвестирования рублей, полученных на начальном этапе, до окончания торгового горизонта.
Чтобы оценить эффективность одностороннего трейдинга, нам необходимо рассмотреть ряд понятий конкурентного анализа.
Пусть P = (Z,F,U) представляет собой задачу максимизации прибыли P, где Z – множество всех возможных последовательностей обменных курсов, генерируемых рынком на протяжении рассматриваемого периода времени; для каждого IZ F(I) представляет множество возможных решений трейдера для конкретной последовательности обменных курсов, а U – функция полезности, зависящая от I (определенной последовательности обменных курсов) и множества решений трейдера OF(I).
Допустим, что ALG представляет собой любой алгоритм, которым руководствуется трейдер для решения проблемы P – максимизации прибыли. Для любого данного I, именно ALG вычисляет OF(I). Обозначим прибыль (или доход), полученный алгоритмом ALG на входных данных I как ALG(I) = U(I,O). Каждый вариант входных данных может быть представлен конечной последовательностью I = i1, i2,…,in, а варианты возможных решений O также могут быть представлены конечной последовательностью O = o1, o2,…, on.
Алгоритм ALG будет называться онлайновым, если для каждого t = 1, 2, …, n-1, ALG должен рассчитать решение ot до того, как будет получено следующее входное значение it+1. И, напротив, назовем алгоритм оффлайновым, если он имеет возможность генерировать допустимые решения, имея «перед собой» всю входную последовательность целиком. Оптимальный (то есть самый эффективный) оффлайн алгоритм обозначим OPT. По определению, для каждой последовательности входных данных (обменных курсов или цен) I доход OPT можно представить как OPT(I) = supOF(I)U(I,O). Другими словами, OPT алгоритм всегда дает максимум полезности (прибыли или дохода). Оно и не мудрено – OPT алгоритм «видит» всю последовательность входных данных в целом, а задним умом всякий крепок. Апостериори (то есть после опыта) каждый может определить, какие решения были бы наилучшими.
Таким образом, OPT алгоритм является эталоном, а, следовательно, может послужить базой для создания меры того, насколько эффективно (то есть близко к эталону) провел всю операцию трейдер, работая в отличие от OPT алгоритма в реальном времени, иначе говоря, не имея перед собой всей последовательности входных данных, а получая каждый последующий ее элемент (один за другим) только с течением времени.
В качестве меры эффективности вводится конкурентное отношение c:
c = 
(1)
Для нашего конкретного случая в числителе будет количество рублей, которые получил бы OPT алгоритм на входной последовательности I – это максимальное количество, которое можно «выжать» на данной последовательности, а в знаменателе будет количество рублей, которые реально получит наш трейдер на той же самой входной последовательности обменных курсов, работая в реальном времени.
Понятно, что в самом общем случае значение c ≥ 1. Если значение c = 1, значит, трейдер сработал идеально – лучше выполнить торговое задание в рассмотренных условиях просто нельзя. На практике этого достичь, конечно же, невозможно (разве что случайно), хотя чем ближе значение с к 1, тем выше должна быть оценка качества работы трейдера. И все-таки, нужно смотреть на вещи трезво и задаваться правдоподобными и реальными значениями конкурентного отношения c.
Наименьшее конкурентное отношение c, которого достигает ALG, называется конкурентным отношением ALG. В этом случае можно сказать, что ALG достигает конкурентного отношения c или, что ALG является c-конкурентным алгоритмом.
Конкурентное отношение служит, таким образом, показателем эффективности в самых неблагоприятных условиях. Любой c-конкурентный онлайн-алгоритм гарантирует доход равный, по крайней мере, (1/c) части прибыли, полученной оптимальным оффлайн алгоритмом, независимо от того, насколько неблагоприятным и переменчивым окажется будущее. Это следует из формулы (1) в результате простого преобразования:
ALG(I) = OPT(I).
Собственно говоря, использование конкурентного отношения для измерения эффективности онлайн-алгоритмов и представляет собой конкурентный анализ. Главная особенность в использовании конкурентных отношений для анализа онлайн алгоритмов заключается в том, что нет необходимости опираться на статистическое моделирование входных последовательностей (скользящие средние и т.п.). Дело в том, что часто бывает очень сложно разработать реалистичные статистические модели для возможного входа (которые всегда сильно зависят от конкретного приложения).
Эта трудность еще более усугубляется в условиях сложных динамических сред, в качестве которых часто выступают экономические системы. По этой причине стратегии принятия финансовых решений являются очень привлекательной сферой для конкурентного анализа. Более того, нередко при принятии финансовых решений более желательно обеспечить некоторый минимальный уровень прибыльности, чем надеяться на ожидание более высокой средней прибыли в условиях подверженности значительному риску. По сути, это как раз то, что и предлагает конкурентный анализ.
Преимуществом конкурентного отношения является то, что оно предлагает единый показатель эффективности, в соответствии с которым любые две стратегии сопоставимы в некотором фундаментальном смысле. Однако следует понимать, что неприятие риска, связанное с конкурентным отношением, нередко может выступать в качестве недостатка, поскольку подобная мера эффективности может привести к чрезмерно «оборонительным» алгоритмам. В действительности, всякий раз, когда лица, принимающие решения имеют некоторую информацию со стороны или определенные (в том числе статистические) знания о развитии последовательностей входных данных было бы непростительно игнорировать их, а именно это делают алгоритмы, которые ориентированы на конкурентное соотношение. Предпринимались попытки объединения чистого конкурентного анализа с использованием прогнозов (в виде частичного знания о будущем входных последовательностей) с сохранением естественного стремления к уклонению от риска, которое присуще конкурентному отношению. Однако осуждение их уведет нас далеко в сторону.
Построение c-конкурентных онлайн-алгоритмов
После необходимых теоретических пояснений мы можем, наконец, обратиться к практическому созданию c-конкурентных онлайн-алгоритмов. Как уже отмечалось, такие алгоритмы основаны на уклонении от риска падения обменного курса.
Пусть с является произвольным конкурентным отношением, которое может быть достигнуто некоторым алгоритмом односторонней торговли; мы считаем, что с известно трейдеру – он определяет для себя приемлемый уровень конкурентного отношения (или ему его определяют). Теперь создадим c-конкурентный онлайн алгоритм, которого должен придерживаться трейдер, ведущий торговлю в одну сторону. Этот алгоритм базируется на очень простых правилах, которых всего два. Применительно к нашей задаче – продаже S0 долларов за рубли – эти правила формулируются следующим образом.
ПРАВИЛО 1. Рассматриваем возможность продажи долларов за рубли только тогда, когда текущий курс рубля является самым высоким из всех, которые наблюдались до сих пор.
ПРАВИЛО 2. Всякий раз, когда доллары продаются за рубли, продавать необходимо столько, сколько необходимо для того, чтобы гарантировать, что конкурентное отношение с будет достигнуто, даже если «Его Величество Рынок» уронит обменный курс рубля до минимально возможного значения и удержит его на этом уровне в течение всего оставшегося периода времени.
Эти два правила применимы на протяжении всего временного горизонта, за исключением его конечной точки, когда согласно условию трейдер вынужден будет продать все оставшиеся доллары за рубли, хотя бы и по невыгодному курсу.
"Минимально возможное значение", о котором говорится во втором правиле, определяется в соответствии с информацией, известной трейдеру. Мы в дальнейшем будем исходить из того, что обменные курсы колеблются в интервале [m,M], где m – минимальное значение (самый низкий курс рубля), а M – максимальное значение (самый высокий курс рубля), причем коэффициент колебания курса f = M/m. Таким образом, минимально возможное значение курса может быть представлено величиной m, если m известно; в другом случае это может быть значение равное (i)/f, если известно только f и (i) является самым высоким курсом (или ценой, если вести речь о ценных бумагах), которые наблюдались до сих пор. Кроме того, мы будем исходить из того, что нам известен временной горизонт, в течение которого необходимо реализовать все доллары.
На начальном этапе может показаться неясным, как следовать указанной линии поведения, особенно, как следовать Правилу 2, которое требует осуществлять продажу такого количества долларов, которое гарантирует достижение конкурентного соотношения c. Однако предположим, что можно вычислить количество, предусмотренное Правилом 2, и представим алгоритм, который следует этой линии поведения. Напомним, что такой алгоритм продает доллары за рубли в условиях уклонения от риска падения обменного курса до минимально возможного значения. Применение Правил 1 и 2 поясним на нескольких тривиальных примерах.
Пример 1. Обменные курсы не изменяются
Имеем следующую входную последовательность обменных курсов:
I1: i1 = i2 = … = in = m =M.
Поскольку в этом случае f = M/m = 1, то нетрудно видеть, что и оффлайн алгоритм OPT, и наш онлайн алгоритм ALG заработают одинаково, то есть получат по mS0 рублей. И тогда конкурентное отношение, рассчитываемое по формуле (1), будет равно
c = mS0/mS0 = 1.
Этот пример слишком уж тривиальный, а потому неинтересен.
Пример 2. После первого обменного курса происходит «обвал»
Имеем следующую входную последовательность обменных курсов:
I2: M = i1 = cm; i2 = … = in = m, где c ≥ 1 – это конкурентное отношение, которого требуется достигнуть, а m – минимально возможное значение обменного курса.
Понятно, что в этих условиях оптимальный оффлайн алгоритм OPT заработает максимум, а именно S0cm рублей.
Что же касается нашего трейдера, то здесь рассмотрим две ситуации.
В первой ситуации трейдер отказывается продавать доллары за рубли по курсу i1 = cm в надежде на более выгодный курс. Однако в действительности вышло так, что фортуна повернулась к нему задом, и он вынужден в последний момент все доллары продать по минимально возможному курсу, выручив за них S0m рублей – результат хуже, чем у оптимального алгоритма. Вычислим конкурентное отношение для этого случая:
c = S0cm/S0m = c. (2)
Как это ни удивительно, но, даже отказавшись торговать по первому – наиболее выгодному – обменному курсу, трейдер все-таки достиг конкурентного отношения, к которому стремился. Мораль: уклонившись от продажи долларов в случае, когда первый обменный курс i1 ≤ cm, трейдер, даже в условиях неблагоприятного развития дальнейших событий, может добиться требуемого конкурентного отношения c, чего не скажешь, когда i1 > cm.
Во второй ситуации трейдер решается совершить сделку по первому обменному курсу в соответствии с правилом 1 алгоритма, поскольку по условию этому обменному курсу ничего не предшествует, а потому он является самым высоким на данный момент. Трейдер решает продать s1 долларов. Тогда его выручка в рублях составит:
s1cm + (S0 – s1)m = S0m + s1m(c – 1).
Посмотрим, каким будет конкурентное отношение в этом случае:
c' = S0cm / [S0m + s1m(c – 1)]. (3)
Если принять во внимание, что при одинаковом числителе знаменатель дроби в формуле (3) больше, чем знаменатель в формуле (2), то становится ясно, что c' < c. Это означает, что во второй ситуации трейдер в большей степени приблизился к результату оптимального оффлайн алгоритма.
Пример 3. После первого обменного курса происходит обвал, но i1 > cm
Входная последовательность обменных курсов такова:
I3: M = i1 > cm; i2 = … = in = m, где c ≥ 1 – это конкурентное отношение, которого требуется достигнуть, а m – минимально возможное значение обменного курса.
Пример 2 был искусственно подобран так, что трейдер, даже отказавшись продавать доллары по первому обменному курсу, все равно достигал необходимого конкурентного отношения. Здесь мы снимаем ограничение на величину первого обменного курса, а потому трейдер вынужден будет торговать в соответствии с правилом 1, руководствуясь при этом и правилом 2.
В условиях входной последовательности I3 оптимальный оффлайн алгоритм получит выручку в рублях равную S0i1.
У трейдера, работающего в онлайне, выручка составит:
s1i1 + (S0 – s1)m = S0m + s1(i1 – m).
Поскольку трейдер должен обеспечить конкурентное отношение c, то можно записать уравнение:
c = S0i1 / [S0m + s1(i1 – m)], (4)
в котором неизвестной величиной является только s1 – количество долларов, продаваемых по первому обменному курсу (целевое значение конкурентного отношения c трейдер определил перед началом торговли, поэтому оно известно). Решение уравнения (4) дает:
s1 = (S0 /c)∙[(i1 – cm)/(i1 – m)]. (5)
Таким образом, значение s1 находится по формуле (5).
Пример 4. Общий случай
Входная последовательность обменных курсов:
I4: i1, i2,…, in.
Рассмотрим первый трейд (обменный курс i1). Так как текущий курс является самым высоким из наблюдавшихся до сих пор (мы с него и начали наблюдение), онлайн алгоритм ALG, которым руководствуется трейдер, предполагает совершение торговой операции. Поскольку конкурентное отношение с достигается этим торговым алгоритмом, существует некоторое s1 ≥ 0 такое, что отношение с будет все еще достижимым, если s1 долларов будут проданы за рубли.
Кроме того, выбранное количество долларов s1 таково, что конкурентное отношение с будет гарантировано даже если далее пойдет постоянное снижение обменного курса рубля и никакие дальнейшие торги не будут проводится (за исключением одной последней сделки, продающей оставшиеся доллары по минимально возможному обменному курсу). В частности, нет никакой необходимости рассматривать любой обменный курс, который меньше, чем i1.
Значение s1 находится по формуле (5).
После этого онлайн алгоритм ALG осуществляет анализ входящей последовательности на предмет поиска значения обменного курса ik > i1 (неравенство строгое).
Как только значение ik будет найдено, онлайн алгоритм ALG начинает решать задачу односторонней продажи (S0 – s1) долларов за рубли на укороченной входящей последовательности I’4: ik,…,in. Как решается эта задача мы уже видели выше.
Поскольку аналогичные рассуждения могут быть использованы для обоснования выбора сумм для остальных торговых операций, то такая линия поведения обеспечивает с-конкурентность алгоритма. Поэтому-то мы не будем больше утомлять читателя новыми формулами и выкладками, а просто предлагает применить индукцию и аналогию. Это даст возможность определять количество долларов, которое будет продаваться онлайн алгоритмом при нахождении каждого нового более выгодного обменного курса.
Нельзя не отметить, хотя мы на этом не заостряли внимания, что в общем случае издержки по получению котировок и комиссионные будут влиять на конкурентное отношение. В частности, когда вводятся фиксированные операционные издержки, конкурентное отношение увеличивается. Когда же операционные издержки определяются фиксированным процентом от цены, конкурентное отношение будет улучшено. И только в случае, когда операционные расходы определяются фиксированным процентом торгуемой суммы, конкурентное отношение любого алгоритма одностороннего трейдинга не зависит от операционных расходов.
