Формула случайного блуждания. Случайное блуждание

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

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

где . Числа имеют следующий смысл: если то при

изменения для очевидны.

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

Капитал игрока, участвующего в серии партий азартной игры, часто описывают процессом случайного блуждания. Предположим, что игрок А, имеющий капитал играет с бесконечно богатым партнером, при этом вероятность того, что он выиграет партию и увеличит свой капитал на единицу, равна а вероятность того, что он проиграет и тем самым уменьшит свой капитал на единицу, равна . Зависимость вероятностей выигрыша и проигрыша от отражает возможную зависимость условий игры от капитала. Так, можно условиться, что, оказавшись в состоянии О (соответствующем разорению игрока А), процесс остается в этом состоянии, т. е. Процесс где размер капитала игрока после партий, является процессом случайного блуждания. Этот процесс известен под названием «задачи о разорении игрока».

Случайное блуждание с соответствует одинаковым повторяющимся партиям; если то в каждой партии шансы игрока А явно предпочтительнее. В гл. 3 мы покажем, что в этом случае с вероятностью где его начальный капитал, игрок А разоряется (теряет свой капитал) и с вероятностью его капитал будет беспредельно возрастать. Если же то игра явно выгодна хозяевам игорного заведения, и почти наверное (с вероятностью 1) игрок А разорится, если будет играть достаточно долго. Игрок А обречен на разорение (с вероятностью 1) и в том случае, когда игра безобидна, т. е. когда

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

Как и ранее, есть вероятность того, что игрок А, имея капитал увеличит (уменьшит) его на единицу в следующей партии. Отметим, что в соответствии с матрицей переходных вероятностей (2.3) капитал игрока А (состояние процесса), достигнув величины а или обратившись в 0, остается в этих состояниях навсегда. Мы говорим, что игрок А разорен, если процесс достиг состояния 0; если же процесс попадает в состояние а, то мы говорим, что разорен игрок

Случайные блуждания оказываются полезными не только для описания игровых ситуаций, но и служат неплохими моделями физических процессов, в частности диффузии частиц. Если частица претерпевает случайные столкновения, то ее положение подвержено случайным флуктуациям, хотя описываемая ею траектория непрерывна. Если будущее положение (точнее, его распределение вероятностей) частицы зависит только от ее настоящего положения, то процесс где положение частицы в момент является марковским. Дискретная аппроксимация такого непрерывного движения соответствует случайному блужданию. Симметричное случайное блуждание представляет собой классический дискретный аналог броуновского движения (см. § 2 гл. 1). Под симметричным случайным блужданием на множестве всех целых чисел подразумевается марковская цепь с пространством состояний, являющимся множеством всех целых чисел, с элементами матрицы переходных вероятностей вида

где . Обычно симметричным случайным блужданием называют марковскую цепь с

Исследование некоторых физических моделей приводит нас к рассмотрению случайных блужданий на множестве неотрицательных целых чисел. Можно дать классификацию таких процессов на основе свойств нулевого состояния. Пусть случайное блуждание описывается матрицей (2.2). Если (а значит, и ), то нулевое состояние обладает свойствами отражающего экрана. Всякий раз, когда частица достигает нулевого состояния, в результате следующего перехода она оказывается в состоянии 1. Это соответствует ситуации, когда в нуле находится упругая стенка и частица отскакивает от нее без каких-либо остаточных явлений.

Если то нулевое состояние ведет себя как поглощающий экран. Попав в нулевое состояние, частица остается

в нем навсегда. Если то нулевое состояние является частично отражающим экраном.

Если случайное блуждание ограничено конечным числом состояний, скажем оба крайних состояния 0 и а независимо и в любой комбинации могут быть отражающими, поглощающими или частично отражающими экранами. Мы уже имели дело со случаем, когда состояния 0 и а были поглощающими [см. (2.3)].

Классическую модель диффузии через мембрану представляет собой модель Эренфестов. Модель описывается как процесс случайного блуждания с конечным числом состояний причем крайние состояния - а и а являются отражающими экранами. Матрица переходных вероятностей задается следующим образом:

Физическая интерпретация этой модели такова. Имеется две урны содержащие вместе 2а шаров. Предположим, что урна А содержит шаров. При каждом испытании случайным образом выбирается один шар и перекладывается в другую урну; при этом каждый из шаров имеет равную со всеми остальными вероятность быть переложенным независимо от того, в какой урне он находится. Каждое испытание приводит к изменению состояния 1) системы. Характерным для перемещения шаров будет преимущественное направление от урны с большей концентрацией к урне с меньшей концентрацией. Модель Эренфестов в некоторых случаях можно использовать для исследования физических систем, находящихся под действием восстанавливающих сил, величина которых пропорциональна расстоянию от положения равновесия.

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

Аналогично одномерному случаю -мерное симметричное случайное блуждание представляет собой дискретный аналог -мерного броуновского движения.

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

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

Если случайность - это свойство непредсказуемости, то значит вывод функции никогда нельзя точно предсказать. Логически из этого вытекает, что всеслучайные процессы - это невычислимые функции, поскольку нельзя создать алгоритм для их вычисления. Знаменитый тезис Черча-Тьюринга постулирует, что функция вычислима, только если ее можно вычислить с помощью машины Тьюринга:

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

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

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

  • Быть несжимаемой - компрессия подразумевает поиск представления информации, которое использует меньше информации. К примеру, бесконечной длинная двоичная строка 0101010101…. может быть выражена более точно как 01, повторенное бесконечно много раз, в то время как бесконечно длинная строка 0110000101110110101… не имеет четко выраженного паттерна, а значит ее нельзя сжать до чего-либо короче, чем эта же самая строка 0110000101110110101 … Это значит, что если Колмогоровская сложность больше или равна длина строки, тогда последовательность алгоритмически случайна.
  • Проходить статистические тесты на случайность - существует множество тестов на случайность, которые проверяют разницу между распределением последовательности относительно ожидаемого распределения любой последовательности, которая считается случайной.
  • Не приносить выгоду - интересный концепт, который подразумевает, что если возможно создать некую ставку , приводящую только к успеху, то значит она неслучайна.
В общем и целом, следует различать глобальное и локальное случайное блуждание. Первое относится к рынкам в долгосрочной перспективе, в то время как локальная гипотеза случайно блуждания может утверждать, что рынок случаен на протяжении некоторого минимального периода времени.

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

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

Взламывая рынок

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

Исследователь решил провести собственный эксперимент, для которого использовал следующие данные:

Также анализировались активы различных типов:

  • Обменные курсы пары доллар/фунт (USD vs GBP) с 1990 до 2015 (дневной график) ~ 25 лет
Набор тестов NIST работал на наборах реальных данных - они дискретиризировались и разбивались на периоды 3,5,7 и 10 лет. Кроме того, существует два способа генерирования тестовых окон - накладывающиеся окна и ненакладывающиеся окна. Первый вариант лучше, поскольку позволяет видеть грядущую случайность рынка, но влияет на качество агрегированных P-значений, поскольку окна не независимы.

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

Второй - двоичные данные, сгенерированные функцией SIN.

Проблемы

У каждого эксперимента есть свои слабые места. Не обошлось без них и в этот раз:
  1. Для некоторых тестов требуется больше данных, чем сгенерировал рынок (кроме случаев использования минутных или тиковых графиков, что не всегда возможно), что значит, что их статистическая значимость чуть менее, чем идеальна.
  2. Тесты NIST проверяют только стандартную случайность - это не значит, что рынки распределены не нормально или как-то по-другому, но все равно случайны.
  3. Случайно выбранные временные периоды (начинающиеся с 1 января каждого года) и уровень значимости (0,005). Тесты нужно проводить на куда более обширном наборе выборок, которые начинаются с каждого месяца или квартала. P-значение не оказало серьезного влияния на итоговые выводы, поскольку при разных его значениях (0,001, 0,005, 0,05) некоторые тесты все равно не были пройдены в определенные периоды (например, 1954-1959 гг.)

Результаты

Вот каких результатов удалось добиться с помощью двух способов тестирования с накладывающимися или ненакладывающимися окнами:

Выводы можно сделать следующие:

  1. Значения лежат между значениями двух бенчмарков, что означает, что рынки менее случайны, чем вихрь Мерсенна и более случайны чем SIN-функция. Но в итоге они не случайны.
  2. Значения серьезно различаются по измерению - размер окна серьезно влияет на результат, и уникальности - рынки не одинаково случайны, некоторые из них более случайны, чем другие.
  3. Значения для бенчмарков консистентно хороши для вихря Мерсенна (в среднем пройдено более 90% тестов) и плохи для SIN-графа (пройдено в среднем 10-30% тестов).
В начале статьи мы рассматривали пример с экспериментом профессора Бертона Малкиеля, который написал знаменитую книгу «Случайное блуждание по Уолл-стрит» (

Хаотическое движение броуновских частиц в жидкости или газе представляет собой пример случайных блужданий. Теория броуновского движения была построена А.Эйнштейном и М.Смолуховским в 1905 - 1906 гг.

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

6.1. Закономерности случайных блужданий

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

N частиц (которые в начальный момент для удобства наблюдений распределены на осиy ) смещаются последовательными шагами ∆x вдоль осиx . Каждый шаг каждой частицы выбирается случайным и независимым от других шагов. Однако распределение вероятностей при выборе любого шага одно и то же. Примем, что смещения в противоположные стороны равновероятны. Это значит, что среднее значение смещения

∆x = 0.

Смысл этого равенства в том, что среднее арифметическое смещений ∆x очень большого числа частиц приближается к нулю по мере роста этого числа. Так понимается усреднение и далее. Иногда такие средние величины называютаприорными 19 . Кроме того, мы будем использовать «наблюдаемые средние» – средние арифметические для заданного числа частиц (как правило, очень большого). «Наблюдаемое среднее» смещения частицы ∆x н мало, но не равно нулю.

После каждого шага частицы будут «расползаться» от оси y . Обозначимx (k ) координату некоторой частицы черезk шагов. Тогда

x (k + 1) =x (k ) + ∆x.

Усреднив это равенство (вновь по множеству частиц), получаем

x (k + 1) =x (k ) ,

т.е. среднее значение x (k ) не изменяется от шага к шагу и, следовательно, равноx (0) = 0. Наблюдаемое значениеx н для большого числа частиц

x (k )н =N

1 x j (k )

ранее предполагаем, что вероятность выпадения «орла» равна 1/2.

окажется близким к нулю (здесь x j - координата j -й частицы)20 .

Ширину полосы, по которой распределяются частицы после k -го шага, удобно характеризовать величинойx 2 (k ) . Чтобы выяснить зависимость этой величины от числа шагов, возведем равенство (2 ) в квадрат и усредним:

x 2 (k + 1) =x 2 (k ) + 2x (k )∆x + (∆x )2 .

Ввиду независимости x (k ) и ∆x имеем

x (k )∆x =x (k ) ∆x = 0.

Обозначим (∆x )2 =a 2 . Из (4) следует

x 2 (k + 1) =x 2 (k ) +a 2 ,

т.е. средний квадрат координаты растет с каждым шагом на величину a 2 . Значит,

x2 (k) = ka2 .

Наблюдаемое значение

н =

xj 2

изменяется приблизительно пропорционально числу шагов.

Распределение частиц в занятой ими полосе более детально характеризуется функцией распределения f (x ), определяющей концентрацию частиц;dW =f (x )dx

– вероятность того, что координата j -й частицы после k -го шага окажется в интервалеx ≤ x j ≤ x +dx . Теория случайных блужданий дает для достаточно большого числа шаговk распределение Гаусса

f (x ) =

√ 2 πka2

Наблюдаемая функция распределения получается путем разбиения оси x на конечные интервалы и подсчета числа частиц в каждом из них. Результат подсчета представляется графически ступенчатой кривой –гистограммой (рис.7 ).

Обратим внимание на одно свойство зависимости (5 ). Если укрупнить шаги по времени вl раз, то средний квадрат смещения за один шагa 2 следует в соот-

K/l . В итоге

ветствии с (5 ) заменить наa

А число шагов k – наk

(k ) =la

· k/l = a

k , т.е. вид зависимости (5 ) не изменяется при укрупнении

20 При заданном числе частицN это справедливо для не слишком большого номера шагаk .

Рис. 7. Распределение частиц при диффузии (гистограмма и теоретическая кривая)

6.2. Оценка параметров движения броуновской частицы в жидкости

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

Если же скорость частицы близка к тепловой, v v T , то и сила, естественно, гораздо меньше, а отклонения ее от среднего значения−αv весьма существенны.

21 Для шарика радиусаR в жидкости с коэффициентом вязкостиη согласно закону Стокса

α = 6 πηR.

Именно эти отклонения ответственны за безостановочное хаотическое движение частицы. Если речь идет о таком движении, то τ из (9 ) можно понимать как оценку времени, спустя которое частица «забывает» начальное направление движения. Но та же величинаτ дает грубую оценку интервала времени, в течение которого частица «помнит» направление движения. (Может быть, для оценки времени «гарантированного забывания» стоило бы взять 2τ , а для оценки времени гарантированного сохранения направленияτ/ 2, но нас интересуют не «гарантированные», а средние времена, поэтому будем полагать, что коэффициенты 2, 1/2 и т.п. лежат за пределами принятой точности оценок.)

За время τ частица проходит путь, равный по порядку величины

a vT τ.

Смещения частицы за различные интервалы времени порядка τ мы можем рассматривать как случайные, подобные рассматривавшимся ранее ∆x , только направленные не вдоль осиx , а в произвольном направлении (например, как три одновременных и независимых смещения вдоль трех осей координат). Движение частицы за времяt τ можно разбить наk t/τ таких шагов. Смещение частицы за времяt оценивается по аналогии с (5 ):

(t) ka(vT τ)

Этот результат обычно представляют в виде

r2 (t) = 6 D t,

где D – коэффициент диффузии22 . С учетом (8 ), (9 ), (11 )

D k α Б T .(13)

Если сначала частицы были сосредоточены в каком-то малом объеме, то со временем они распространяются все дальше, занимая область размераr (t ).

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

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

22 Для случайных блужданий в направлении осиx вместо (12 ) имеемx 2 (t ) = 2 D t .

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

Прежде всего давайте рассмотрим несколько примеров случайных блужданий. Их можно описать «чистым» продвижением D N , за N шагов. На фиг. 6.5 показаны три примера путей при случайном блуждании.

Что можно сказать о таком движении? Ну, во-первых, можно спросить: как далеко мы в среднем продвинемся? Нужно ожидать, что среднего продвижения вообще не будет, поскольку мы с равной вероятностью можем идти как вперед, так и назад. Однако чувствуется, что с увеличением N мы все с большей вероятностью можем блуждать где-то все дальше и дальше от начальной точки. Поэтому возникает вопрос: каково среднее абсолютное расстояние, г. е. каково среднее значение |D|? Впрочем, удобнее иметь дело не с |D|, а с D 2 ; эта величина положительна как для положительного, так и для отрицательного движения и поэтому тоже может служить разумной мерой таких случайных блужданий.

Можно показать, что ожидаемая величина D 2 N равна просто N— числу сделанных шагов. Кстати, под «ожидаемой величиной» мы понимаем наиболее вероятное значение (угаданное наилучшим образом), о котором можно думать как об ожидаемом среднем значении большого числа повторяющихся процессов блуждания. Эта величина обозначается как и называется, кроме того, «средним квадратом расстояния». После одного шага D 2 всегда равно +1, поэтому, несомненно, = 1. (За единицу расстояния всюду будет выбираться один шаг, и поэтому я в дальнейшем не буду писать единиц длины.)

Ожидаемая величина D 2 N для N > 1 может быть получена из D N -1 . Если после (N — 1) шагов мы оказались на расстоянии D N -1 то еще один шаг даст либо D N = D N -1 + 1, либо D N =D N -1 — 1. Или для квадратов

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

Если теперь вспомнить, что = 1, то получается очень простой результат:

Отклонение от начального положения можно характеризовать величиной типа расстояния (а не квадрата расстояния); для этого нужно просто извлечь квадратный корень из D < 2 N > и получить так называемое «среднее квадратичное расстояние» Dск:

Мы уже говорили, что случайные блуждания очень похожи на опыт с подбрасыванием монет, с которого мы начали эту главу. Если представить себе, что каждое продвижение вперед или назад обусловливается выпадением «орла» или «решки», то D N . будет просто равно N 0 — N P , т. е. разности числа выпадений «орла» и «решки». Или поскольку N 0 + N P = N (где N — полное число подбрасываний), то D N = 2N 0 — N. Вспомните, что раньше мы уже получали выражение для ожидаемого распределения величины No [она обозначалась тогда через k; см. уравнение (6.5)]. Ну а поскольку N — просто постоянная, то теперь такое же распределение получилось и для D. (Выпадение каждого «орла» означает невыпадение «решки», поэтому в связи между N 0 и D появляется множитель 2.) Таким образом, на фиг. 6.2 график представляет одновременно и распределение расстояний, на которые мы можем уйти за 30 случайных шагов (k = 15 соответствует D = 0, а k= 16 соответствует D= 2 и т. д.).

Отклонение N 0 от ожидаемой величины N/2 будет равно

откуда для среднего квадратичного отклонения получаем

Вспомним теперь наш результат для D ск. Мы ожидаем, что среднее расстояние, пройденное за 30 шагов, должно быть равно √30 = 5,5, откуда среднее отклонение k от 15 должно быть 5,5: 2 ≈ 2,8. Заметьте, что средняя полуширина нашей кривой на фиг. 6.2 (т. е. полуширина «колокола» где-то посредине) как раз приблизительно равна 3, что согласуется с этим результатом.

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

Одновременно ожидается, что действительное число выпадений «орла» должно отличаться от N/2 на величину порядка √N/2, или, если говорить о доле отклонения, она равна

т. е. чем больше N, тем ближе к половине отношение N0/N.

На фиг. 6.6 отложены числа N 0 /N для тех подбрасываний монеты, о которых мы говорили раньше. Как видите, при увеличении числа N кривая все ближе и ближе подходит к 0,5. Но, к сожалению, нет никаких гарантий, что для каждой данной серии или комбинации серий наблюдаемое отклонение будет близко к ожидаемому отклонению. Всегда есть конечная вероятность, что произойдет большая флуктуация — появление большого числа выпадений «орла» или «решки»,— которая даст произвольно большое отклонение. Единственное, что можно сказать,— это если отклонения близки к ожидаемому 1/2√N (скажем, со множителем 2 или 3), то нет оснований считать монету «поддельной» (или что партнер плутует).

Мы не рассматривали еще случаи, когда для монеты или какого-то другого объекта испытания, подобного монете (в том смысле, что возможны два или несколько достоверно не предсказуемых исхода наблюдения, например камень, который может упасть только на какую-то из двух сторон), имеется достаточно оснований полагать, что вероятности разных исходов не равны. Мы определили вероятность Р(О) как отношение /N. Но что принять за величину ? Каким образом можно узнать, что ожидается! Во многих случаях самое лучшее, что можно сделать, это подсчитать число выпадений «орла» в большой серии испытаний и взять = N 0 (наблюденное). (Как можно ожидать чего-то еще?) При этом, однако, нужно понимать, что различные наблюдатели и различные серии испытаний могут дать другое значение Р(О), отличное от нашего. Следует ожидать, однако, что все эти различные ответы не будут расходиться больше чем на 1/2√N [если Р(О) близко к половине]. Физики-экспериментаторы обычно говорят, что «экспериментально найденная» вероятность имеет «ошибку», и записывают это в виде

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

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

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

Если случайность - это свойство непредсказуемости, то значит вывод функции никогда нельзя точно предсказать. Логически из этого вытекает, что всеслучайные процессы - это невычислимые функции, поскольку нельзя создать алгоритм для их вычисления. Знаменитый тезис Черча-Тьюринга постулирует, что функция вычислима, только если ее можно вычислить с помощью машины Тьюринга:

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

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

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

  • Быть несжимаемой - компрессия подразумевает поиск представления информации, которое использует меньше информации. К примеру, бесконечной длинная двоичная строка 0101010101…. может быть выражена более точно как 01, повторенное бесконечно много раз, в то время как бесконечно длинная строка 0110000101110110101… не имеет четко выраженного паттерна, а значит ее нельзя сжать до чего-либо короче, чем эта же самая строка 0110000101110110101 … Это значит, что если Колмогоровская сложность больше или равна длина строки, тогда последовательность алгоритмически случайна.
  • Проходить статистические тесты на случайность - существует множество тестов на случайность, которые проверяют разницу между распределением последовательности относительно ожидаемого распределения любой последовательности, которая считается случайной.
  • Не приносить выгоду - интересный концепт, который подразумевает, что если возможно создать некую ставку , приводящую только к успеху, то значит она неслучайна.
В общем и целом, следует различать глобальное и локальное случайное блуждание. Первое относится к рынкам в долгосрочной перспективе, в то время как локальная гипотеза случайно блуждания может утверждать, что рынок случаен на протяжении некоторого минимального периода времени.

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

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

Взламывая рынок

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

Исследователь решил провести собственный эксперимент, для которого использовал следующие данные:

Также анализировались активы различных типов:

  • Обменные курсы пары доллар/фунт (USD vs GBP) с 1990 до 2015 (дневной график) ~ 25 лет
Набор тестов NIST работал на наборах реальных данных - они дискретиризировались и разбивались на периоды 3,5,7 и 10 лет. Кроме того, существует два способа генерирования тестовых окон - накладывающиеся окна и ненакладывающиеся окна. Первый вариант лучше, поскольку позволяет видеть грядущую случайность рынка, но влияет на качество агрегированных P-значений, поскольку окна не независимы.

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

Второй - двоичные данные, сгенерированные функцией SIN.

Проблемы

У каждого эксперимента есть свои слабые места. Не обошлось без них и в этот раз:
  1. Для некоторых тестов требуется больше данных, чем сгенерировал рынок (кроме случаев использования минутных или тиковых графиков, что не всегда возможно), что значит, что их статистическая значимость чуть менее, чем идеальна.
  2. Тесты NIST проверяют только стандартную случайность - это не значит, что рынки распределены не нормально или как-то по-другому, но все равно случайны.
  3. Случайно выбранные временные периоды (начинающиеся с 1 января каждого года) и уровень значимости (0,005). Тесты нужно проводить на куда более обширном наборе выборок, которые начинаются с каждого месяца или квартала. P-значение не оказало серьезного влияния на итоговые выводы, поскольку при разных его значениях (0,001, 0,005, 0,05) некоторые тесты все равно не были пройдены в определенные периоды (например, 1954-1959 гг.)

Результаты

Вот каких результатов удалось добиться с помощью двух способов тестирования с накладывающимися или ненакладывающимися окнами:

Выводы можно сделать следующие:

  1. Значения лежат между значениями двух бенчмарков, что означает, что рынки менее случайны, чем вихрь Мерсенна и более случайны чем SIN-функция. Но в итоге они не случайны.
  2. Значения серьезно различаются по измерению - размер окна серьезно влияет на результат, и уникальности - рынки не одинаково случайны, некоторые из них более случайны, чем другие.
  3. Значения для бенчмарков консистентно хороши для вихря Мерсенна (в среднем пройдено более 90% тестов) и плохи для SIN-графа (пройдено в среднем 10-30% тестов).
В начале статьи мы рассматривали пример с экспериментом профессора Бертона Малкиеля, который написал знаменитую книгу «Случайное блуждание по Уолл-стрит» (