Биномиальная модель оценки опционов: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][ожидает проверки]
 
(не показано 18 промежуточных версий 2 участников)
Строка 3: Строка 3:
 
Биномиальная модель оценки опциона – итерационный метод, моделирующий цену опциона на временном отрезке, когда опцион действителен. Для некоторых типов опционов, например, американского, это единственный способ оценки, так как точное решение, позволяющее предсказать цену на всем временном отрезке, неизвестно.
 
Биномиальная модель оценки опциона – итерационный метод, моделирующий цену опциона на временном отрезке, когда опцион действителен. Для некоторых типов опционов, например, американского, это единственный способ оценки, так как точное решение, позволяющее предсказать цену на всем временном отрезке, неизвестно.
  
Если быть точнее, биномиальная модель представляет эволюцию цены базового актива опциона как двоичное дерево всех возможных цен при равномерном разбиении временного отрезка с сегодняшнего дня, с предположением, что на каждом шаге цена может только расти либо падать на фиксированное число с соответствующими вероятностями <math>p_u</math> и <math>p_d</math>. Другими словами, корнем дерева является сегодняшняя цена базового актива, каждый уровень представляет собой все возможные цены в данный момент времени. У каждого узла со значением <math>S</math> есть два дочерних со значениями <math>Su</math> и <math>Sd, u,d</math> – множители движения цены вверх и вниз соответственно за один шаг по времени <math>dT</math>. <math>u</math> и <math>d</math> зависят от волатильности <math>\sigma</math>:
+
Если быть точнее, биномиальная модель представляет эволюцию цены базового актива опциона как двоичное дерево всех возможных цен при равномерном разбиении временного отрезка с сегодняшнего дня, в предположении, что на каждом шаге цена может только расти, либо падать на фиксированное число с соответствующими вероятностями <math>p_u</math> и <math>p_d</math>. Другими словами, корнем дерева является сегодняшняя цена базового актива, каждый уровень представляет собой все возможные цены в данный момент времени. У каждого узла со значением <math>S</math> есть два дочерних узла со значениями <math>Su</math> и <math>Sd, u,d</math> – множители движения цены вверх и вниз соответственно за один шаг по времени <math>dT</math>. <math>u</math> и <math>d</math> зависят от волатильности <math>\sigma</math> следующим образом:
  
 
<math>u = e^{\sigma\sqrt{dT}}, d = e^{-\sigma\sqrt{dT}}, ud = 1.</math>
 
<math>u = e^{\sigma\sqrt{dT}}, d = e^{-\sigma\sqrt{dT}}, ud = 1.</math>
  
<math>p_d = 1 - p_u, p_u</math> ищется в предположении, что за <math>dT</math> доходность базового актива в среднем такая же, как и при отсутствии риска, то есть если в момент времени <math>t</math> стоимость базового актива <math>S</math>, то в момент времени <math>t + dT</math> она будет равна <math>Se^{rdT}</math>, где <math>r</math> - процентная ставка. Получается следующее уравнение:
+
где <math>p_d = 1 - p_u</math>, <math>p_u</math> ищется в предположении, что за <math>dT</math> доходность базового актива в среднем такая же, как и при отсутствии риска, то есть если в момент времени <math>t</math> стоимость базового актива <math>S</math>, то в момент времени <math>t + dT</math> она будет равна <math>Se^{rdT}</math>, где <math>r</math> - процентная ставка. В результате получается следующее уравнение:
  
 
<math>Se^{rdT} = (Su p_u + Sd p_d)</math>,
 
<math>Se^{rdT} = (Su p_u + Sd p_d)</math>,
Строка 13: Строка 13:
 
откуда <math>p_u = \frac{e^{rdT} - d}{u - d}.</math>
 
откуда <math>p_u = \frac{e^{rdT} - d}{u - d}.</math>
  
С помощью такого представления, можно получить цену в любом узле дерева. Для опциона "колл" она равна <math>V_{call} = max\{S - K, 0\}</math>, для "пут" <math>V_{put} = max\{K - S, 0\}</math>, <math>K</math> - страйк опциона. После расчета всех возможных цен опциона, начинается движение от листьев к корню по формуле
+
С помощью такого представления можно получить цену в любом узле дерева. Для опциона "колл" она равна <math>V_{call} = max\{S - K, 0\}</math>, для "пут" <math>V_{put} = max\{K - S, 0\}</math>, где <math>K</math> - страйк опциона. После расчета всех возможных цен опциона, начинается движение от листьев к корню по формуле
  
 
<math>V_t = (p_uV_{u, t+1} + p_dV_{d, t+1})e^{-rdT} (1)</math>,  
 
<math>V_t = (p_uV_{u, t+1} + p_dV_{d, t+1})e^{-rdT} (1)</math>,  
  
где <math>V_t</math> - цена опциона в некотором узле, <math>V_{u, t+1}, V_{d, t+1}</math> - цены опциона в дочерних узлах.
+
где <math>V_t</math> - цена опциона в некотором узле, <math>V_{u, t+1}</math> и <math>V_{d, t+1}</math> - цены опциона в дочерних узлах.
  
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
Для реализации алгоритма потребуются две формулы:
+
Для реализации алгоритма потребуются выполнять расчеты по следующим двум формулам:
  
1) <math>V_{T_i} = max\{Se^{V_sdT * 2i - N} - K, 0\}</math> - для расчета стоимости опциона в i-м листе дерева
+
(1) <math>V_{T_i} = max\{Se^{V_sdT * 2i - N} - K, 0\}</math> - для расчета стоимости опциона в <math>i</math>-м листе дерева;
  
2) <math>V_t = (p_uV_{u, t+1} + p_dV_{d, t+1})e^{-rdT}</math> - для расчета справедливой стоимости опциона
+
(2) <math>V_t = (p_uV_{u, t+1} + p_dV_{d, t+1})e^{-rdT}</math> - для расчета справедливой стоимости опциона.
  
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===
Вычислительным ядром алгоритма является вычисление справедливой стоимости опциона. Для этого действия потребуется <math>\frac{N(N-1)}{2}</math> операций, где <math>N</math> - число шагов по времени.
+
Вычислительным ядром алгоритма является вычисление справедливой стоимости опциона. Для этого действия потребуется <math>N(N-1)/2</math> операций, где <math>N</math> - число шагов по времени.
  
 
=== Макроструктура алгоритма ===
 
=== Макроструктура алгоритма ===
Строка 34: Строка 34:
 
1. Генерация цен опциона в листьях.
 
1. Генерация цен опциона в листьях.
  
2. Вычисление справедливой стоимости опциона по формуле <math>(1)</math>
+
2. Вычисление справедливой стоимости опциона по формуле (1).
  
 
=== Схема реализации последовательного алгоритма ===
 
=== Схема реализации последовательного алгоритма ===
На вход: количество этапов N, страйк K, цена базового актива на <math>t_0</math> S, волатильность базового актива v, шаг по времени dT, процентная ставка r.
+
На вход: количество этапов <math>N</math>, страйк <math>K</math>, цена базового актива на <math>t_0</math> <math>S</math>, волатильность базового актива <math>sigma</math>, шаг по времени <math>dT</math>, процентная ставка <math>r</math>.
  
1. Для i = 0, N:
+
1. Для i = 0,...,N:
  
 
1.1 price = S * exp(v * dT  * (2 - i * N))
 
1.1 price = S * exp(v * dT  * (2 - i * N))
Строка 49: Строка 49:
 
3. pd = 1 - pu
 
3. pd = 1 - pu
  
4. Для i = N, 1
+
4. Для i = N,...,1:
  
4.1 Для j = 0, i - 1
+
4.1 Для j = 0,..., i - 1:
  
 
4.1.1 steps[j] = pu * steps[j + 1] + pd * steps[j]
 
4.1.1 steps[j] = pu * steps[j + 1] + pd * steps[j]
  
 
=== Последовательная сложность алгоритма ===
 
=== Последовательная сложность алгоритма ===
Алгоритм требует <math>4N + 4 + N^2 - N = N^2 + 3N + 4</math> операций умножения, <math>N^2 + 2N + 3</math> операций вычитания, <math>N + 4</math> вычислений экспоненты, <math>N</math> вычислений максимума и 3 операции вычисления квадратного корня. В итоге, последовательная сложность алгоритма равна <math>2N^2 + 7N + 14</math> элементарных операций.
+
Алгоритм требует выполнения <math>4N + 4 + N^2 - N = N^2 + 3N + 4</math> операций умножения, <math>N^2 + 2N + 3</math> операций вычитания, <math>N + 4</math> вычислений экспоненты, <math>N</math> вычислений максимума и 3 операции вычисления квадратного корня. В итоге, последовательная суммарная сложность алгоритма составляет <math>2N^2 + 7N + 14</math> элементарных операций.
  
 
=== Информационный граф алгоритма ===
 
=== Информационный граф алгоритма ===
Информационный граф алгоритма изображен на рисунке 1
+
Информационный граф алгоритма изображен на рисунке 1, где в узлах графа показаны выполняемые арифметические операции, а также функции <math>exp</math> и <math>max</math>.
  
 
[[Файл:BOPM.png]]
 
[[Файл:BOPM.png]]
  
 
=== Ресурс параллелизма алгоритма ===
 
=== Ресурс параллелизма алгоритма ===
Для вычисления значений справедливой стоимости опциона в листьях необходимо выполнить последовательно следующие ярусы:
+
Для вычисления значений справедливой стоимости опциона в листьях необходимо последовательно выполнить следующие ярусы:
  
1. Вычисление экспоненты
+
1. Вычисление экспоненты;
  
2. Умножение экспоненты на стоимость базового актива в момент времени <math>t_0</math>
+
2. Умножение экспоненты на стоимость базового актива в момент времени <math>t_0</math>.
  
При классификации по ширине ярусно-параллельной формы алгоритм имеет сложность <math>O(N)</math>. При классификации по высоте ЯПФ - <math>O(N)</math>
+
При классификации по ширине ярусно-параллельной формы алгоритм имеет сложность <math>O(N)</math>. При классификации по высоте ЯПФ - <math>O(N)</math>.
  
 
=== Входные и выходные данные алгоритма ===
 
=== Входные и выходные данные алгоритма ===
Входные данные алгоритма, как было указано ранее, количество этапов <math>N</math>, страйк <math>K</math>, цена базового актива на <math>t_0</math> <math>S</math>, волатильность базового актива <math>\sigma</math>, шаг по времени <math>\Delta T</math>, процентная ставка <math>r</math>. На выходе получается справедливая стоимость опциона <math>C</math>.
+
Входные данные алгоритма, как было указано ранее, это количество этапов <math>N</math>, страйк <math>K</math>, цена базового актива на <math>t_0</math> <math>S</math>, волатильность базового актива <math>\sigma</math>, шаг по времени <math>\Delta T</math>, процентная ставка <math>r</math>. На выходе получается справедливая стоимость опциона <math>C</math>.
  
 
=== Свойства алгоритма ===
 
=== Свойства алгоритма ===
Строка 109: Строка 109:
  
 
=== Локальность данных и вычислений ===
 
=== Локальность данных и вычислений ===
 +
Алгоритм обладает хорошей локальностью данных, так как при вычислении справедливой цены опциона используются соседние элементы массива.
 +
 
=== Возможные способы и особенности реализации параллельного алгоритма ===
 
=== Возможные способы и особенности реализации параллельного алгоритма ===
 
=== Масштабируемость алгоритма и его реализации ===
 
=== Масштабируемость алгоритма и его реализации ===
Строка 116: Строка 118:
  
 
=== Существующие реализации ===
 
=== Существующие реализации ===
Существует
+
Существует множество реализаций этой модели. [http://developer.download.nvidia.com/compute/cuda/1.1-Beta/x86_website/Computational_Finance.html#binomialOptions Одно из них] представлено в качестве примера для NVIDIA CUDA SDK. Оно используется здесь для исследований.
 +
 
 +
Реализацию алгоритма можно найти здесь: [https://github.com/warm35/binomial/tree/master/NVIDIA_CUDA_SDK]
 +
 
 +
[[Категория:Алгоритмы]]

Текущая версия на 16:00, 8 июля 2016

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

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

Если быть точнее, биномиальная модель представляет эволюцию цены базового актива опциона как двоичное дерево всех возможных цен при равномерном разбиении временного отрезка с сегодняшнего дня, в предположении, что на каждом шаге цена может только расти, либо падать на фиксированное число с соответствующими вероятностями [math]p_u[/math] и [math]p_d[/math]. Другими словами, корнем дерева является сегодняшняя цена базового актива, каждый уровень представляет собой все возможные цены в данный момент времени. У каждого узла со значением [math]S[/math] есть два дочерних узла со значениями [math]Su[/math] и [math]Sd, u,d[/math] – множители движения цены вверх и вниз соответственно за один шаг по времени [math]dT[/math]. [math]u[/math] и [math]d[/math] зависят от волатильности [math]\sigma[/math] следующим образом:

[math]u = e^{\sigma\sqrt{dT}}, d = e^{-\sigma\sqrt{dT}}, ud = 1.[/math]

где [math]p_d = 1 - p_u[/math], [math]p_u[/math] ищется в предположении, что за [math]dT[/math] доходность базового актива в среднем такая же, как и при отсутствии риска, то есть если в момент времени [math]t[/math] стоимость базового актива [math]S[/math], то в момент времени [math]t + dT[/math] она будет равна [math]Se^{rdT}[/math], где [math]r[/math] - процентная ставка. В результате получается следующее уравнение:

[math]Se^{rdT} = (Su p_u + Sd p_d)[/math],

откуда [math]p_u = \frac{e^{rdT} - d}{u - d}.[/math]

С помощью такого представления можно получить цену в любом узле дерева. Для опциона "колл" она равна [math]V_{call} = max\{S - K, 0\}[/math], для "пут" [math]V_{put} = max\{K - S, 0\}[/math], где [math]K[/math] - страйк опциона. После расчета всех возможных цен опциона, начинается движение от листьев к корню по формуле

[math]V_t = (p_uV_{u, t+1} + p_dV_{d, t+1})e^{-rdT} (1)[/math],

где [math]V_t[/math] - цена опциона в некотором узле, [math]V_{u, t+1}[/math] и [math]V_{d, t+1}[/math] - цены опциона в дочерних узлах.

1.2 Математическое описание алгоритма

Для реализации алгоритма потребуются выполнять расчеты по следующим двум формулам:

(1) [math]V_{T_i} = max\{Se^{V_sdT * 2i - N} - K, 0\}[/math] - для расчета стоимости опциона в [math]i[/math]-м листе дерева;

(2) [math]V_t = (p_uV_{u, t+1} + p_dV_{d, t+1})e^{-rdT}[/math] - для расчета справедливой стоимости опциона.

1.3 Вычислительное ядро алгоритма

Вычислительным ядром алгоритма является вычисление справедливой стоимости опциона. Для этого действия потребуется [math]N(N-1)/2[/math] операций, где [math]N[/math] - число шагов по времени.

1.4 Макроструктура алгоритма

Алгоритм состоит из двух шагов:

1. Генерация цен опциона в листьях.

2. Вычисление справедливой стоимости опциона по формуле (1).

1.5 Схема реализации последовательного алгоритма

На вход: количество этапов [math]N[/math], страйк [math]K[/math], цена базового актива на [math]t_0[/math] [math]S[/math], волатильность базового актива [math]sigma[/math], шаг по времени [math]dT[/math], процентная ставка [math]r[/math].

1. Для i = 0,...,N:

1.1 price = S * exp(v * dT * (2 - i * N))

1.2 steps[i] = max(price - K, 0)

2. pu = (exp(r * dT) - exp(-sigma * sqrt(dT))) / (exp(sigma * sqrt(dT)) - exp(-sigma * sqrt(dT)))

3. pd = 1 - pu

4. Для i = N,...,1:

4.1 Для j = 0,..., i - 1:

4.1.1 steps[j] = pu * steps[j + 1] + pd * steps[j]

1.6 Последовательная сложность алгоритма

Алгоритм требует выполнения [math]4N + 4 + N^2 - N = N^2 + 3N + 4[/math] операций умножения, [math]N^2 + 2N + 3[/math] операций вычитания, [math]N + 4[/math] вычислений экспоненты, [math]N[/math] вычислений максимума и 3 операции вычисления квадратного корня. В итоге, последовательная суммарная сложность алгоритма составляет [math]2N^2 + 7N + 14[/math] элементарных операций.

1.7 Информационный граф алгоритма

Информационный граф алгоритма изображен на рисунке 1, где в узлах графа показаны выполняемые арифметические операции, а также функции [math]exp[/math] и [math]max[/math].

BOPM.png

1.8 Ресурс параллелизма алгоритма

Для вычисления значений справедливой стоимости опциона в листьях необходимо последовательно выполнить следующие ярусы:

1. Вычисление экспоненты;

2. Умножение экспоненты на стоимость базового актива в момент времени [math]t_0[/math].

При классификации по ширине ярусно-параллельной формы алгоритм имеет сложность [math]O(N)[/math]. При классификации по высоте ЯПФ - [math]O(N)[/math].

1.9 Входные и выходные данные алгоритма

Входные данные алгоритма, как было указано ранее, это количество этапов [math]N[/math], страйк [math]K[/math], цена базового актива на [math]t_0[/math] [math]S[/math], волатильность базового актива [math]\sigma[/math], шаг по времени [math]\Delta T[/math], процентная ставка [math]r[/math]. На выходе получается справедливая стоимость опциона [math]C[/math].

1.10 Свойства алгоритма

Отношение последовательной и параллельной сложностей алгоритма в случае неограниченных ресурсов является линейным.

2 Программная реализация алгоритма

2.1 Особенности последовательной реализации алгоритма

Код последовательной реализации на языке C может выглядеть так:

#include <stdlib.h>
#include <float.h>
#include <math.h>

double price(int N, double K, double S, double vol, double dT, double r) {
   double *steps = malloc(sizeof(double) * (N + 1));
   for(int i = 0; i <= N; i++) { 
       double price = S * expf(vol * dT * (2. * i - N)); 
       steps[i] = fmaxf(price - K, .0); 
   }

   double pu = (expf(r * dT) - expf(-vol * sqrt(dT))) / (expf(vol * sqrt(dT)) - expf(-vol * sqrt(dT))), pd = 1 - pu;

   for(int i = N; i > 0; i--)
       for(int j = 0; j <= i - 1; j++) 
           steps[j] = pu * steps[j + 1] + pd * steps[j]; 

   double C = steps[0];

   free(steps);
   steps = 0x0;

   return C;
}

2.2 Локальность данных и вычислений

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

2.3 Возможные способы и особенности реализации параллельного алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

При большом количестве периодов, возможна реализация на GPU.

2.7 Существующие реализации

Существует множество реализаций этой модели. Одно из них представлено в качестве примера для NVIDIA CUDA SDK. Оно используется здесь для исследований.

Реализацию алгоритма можно найти здесь: [1]