重组二项式期望值的并行计算

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《Parallelizing Computation of Expected Values in Recombinant Binomial
  Trees》
---
作者：
Sai K. Popuri and Andrew M. Raim and Nagaraj K. Neerchal and Matthias
  K. Gobbert
---
最新提交年份：
2018
---
英文摘要：
  Recombinant binomial trees are binary trees where each non-leaf node has two child nodes, but adjacent parents share a common child node. Such trees arise in finance when pricing an option. For example, valuation of a European option can be carried out by evaluating the expected value of asset payoffs with respect to random paths in the tree. In many variants of the option valuation problem, a closed form solution cannot be obtained and computational methods are needed. The cost to exactly compute expected values over random paths grows exponentially in the depth of the tree, rendering a serial computation of one branch at a time impractical. We propose a parallelization method that transforms the calculation of the expected value into an \"embarrassingly parallel\" problem by mapping the branches of the binomial tree to the processes in a multiprocessor computing environment. We also propose a parallel Monte Carlo method which takes advantage of the mapping to achieve a reduced variance over the basic Monte Carlo estimator. Performance results from R and Julia implementations of the parallelization method on a distributed computing cluster indicate that both the implementations are scalable, but Julia is significantly faster than a similarly written R code. A simulation study is carried out to verify the convergence and the variance reduction behavior in the proposed Monte Carlo method.
---
中文摘要：
重组二叉树是二叉树，其中每个非叶节点有两个子节点，但相邻的父节点共享一个公共子节点。这种树出现在金融学中，当为期权定价时。例如，欧式期权的估值可以通过评估关于树中随机路径的资产回报的预期值来执行。在期权定价问题的许多变体中，无法获得封闭形式的解，需要计算方法。在随机路径上精确计算期望值的成本在树的深度呈指数增长，使得一次对一个分支进行串行计算不切实际。我们提出了一种并行化方法，通过将二叉树的分支映射到多处理器计算环境中的进程，将期望值的计算转化为“令人尴尬的并行”问题。我们还提出了一种并行蒙特卡罗方法，该方法利用映射来减少基本蒙特卡罗估计量的方差。分布式计算集群上并行化方法的R和Julia实现的性能结果表明，这两种实现都是可伸缩的，但Julia的速度明显快于类似编写的R代码。通过仿真研究，验证了所提出的蒙特卡罗方法的收敛性和方差缩减行为。
---
分类信息：

一级分类：Statistics        统计学
二级分类：Computation        计算
分类描述：Algorithms, Simulation, Visualization
算法、模拟、可视化
--
一级分类：Quantitative Finance        数量金融学
二级分类：Computational Finance        计算金融学
分类描述：Computational methods, including Monte Carlo, PDE, lattice and other numerical methods with applications to financial modeling
计算方法，包括蒙特卡罗，偏微分方程，格子和其他数值方法，并应用于金融建模
--

---
PDF下载：
--> Parallelizing_Computation_of_Expected_Values_in_Recombinant_Binomial_Trees.pdf (261.49 KB)

2022-6-13 22:15:52 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：并行计算 二项式 期望值 Applications Quantitative

重组二项式TreesSai K.Popuria、Andrew M.Raimb、Nagaraj K.Neerchala和Matthias K.Gobbertaa中预期值的并行计算美国马里兰州巴尔的摩市马尔兰大学数学和统计系，1000 HilltopCircle，Baltimore，MD 21250；b美国人口普查局统计研究与方法学中心，地址：4600 Silver Hill Road，Washing ton，DC 20233，USA，发表于《统计计算与模拟杂志》（DOI:10.1080/00949655.2017.1402898）摘要重组二叉树是二叉树，其中每个非叶节点有两个子节点，但相邻的p节点共享一个公共子节点。这种树在为期权定价时出现在金融中。例如，金融期权的估值可以通过评估资产对树中随机路径的预期价值来进行。在选择估值问题的许多变体中，无法获得闭式解，需要计算方法。在随机路径上精确计算期望值的成本在树的深度上呈指数增长，使得一次对一个分支进行串行计算不切实际。我们提出了一种并行化方法，通过将二叉树的分支映射到多处理器计算环境中的进程，将期望值的计算转化为令人尴尬的并行问题。我们还讨论了一种并行蒙特卡罗方法，该方法利用映射的优势，在基本蒙特卡罗估计量的基础上减少方差。性能在分布式计算集群上并行化方法的R和Julia实现的结果表明，这两种实现都是可伸缩的，但Julia明显快于类似编写的R代码。

通过仿真研究验证了并行蒙特卡罗方法的收敛性和方差缩减行为。关键词多项式树，伯努利路径，蒙特卡罗估计，期权定价。1、导言N步重组二叉树是一个二叉树，其中每个非叶节点有两个子节点，我们将其标记为“向上”和“向下”。树的深度为N，因此从根节点到叶节点的任何路径都由N个向上或向下的步骤组成。该树被称为重组树，因为假定移动序列（向上，向下）与序列（向下，向上）相等。在这样的树中，有N+1个不同的叶节点和1+2+··+（N+1）=（N+1）（N+2）/2个节点。从根到叶的任何特定路径都可以写为二进制序列x=（x，…，xN），其中xj∈ B、 B={0，1}，1对应向上移动，而0对应向下移动。给定密度p（x）=p（x=x），我们可以将x视为从根到叶的随机路径。我们将参考随机变量X∈ BNas伯努利路径。N步二叉树有2NBernoulliCONTACT Sai K.Popuri。电子邮件：saiku1@umbc.eduDisclaimer：本文旨在向正在进行的研究的相关方提供信息，并鼓励对正在进行的工作进行讨论。所表达的观点是作者的观点，不一定是美国人口普查局的观点。SS/uSuS/u2SSu2（1- p） pp2p（1- p） （1）- p） p（1- p） 2图1.1：二s tep重组二叉树。路径。Cox等人提出的二项式期权定价模型是重组二项式树的一个主要示例。该模型考虑了基于S当前市场价格的未来股票价格的不确定性。图1.1说明了股票inN=2个时间段演化的二项式期权模型。

从根节点开始，股票价格向上移动一个数量u到概率为p的SU，或向下移动到概率为1的SU- p、 在一个步骤之后，两个子节点中的每一个子节点进一步分支到两个叶节点，其中u的因子以概率p应用，ord以概率1应用- p、 在这里，序列（上涨，下跌）和（道指n，上涨）都将股票价格带回其起始价格。二项式期权定价模型用于对期权等金融合同进行估值，这些合同的价值来自于较不复杂的基础资产，如股票价格。为了计算期权的价值，我们在每个时间步使用伯努利概率模型，从股票的当前市场价格到未来时间点构建一个重组二叉树。根据期权的类型，期权价值要么是预期期权支付的现值，要么是通过将树向后移动并在每个步骤修改期权价值来计算的。有关期权及其估值的更多详细信息，请参见赫尔（Hull）[2]和塞德尔（Seydel）[3]。当叶节点的期权支付取决于路径时，必须考虑所有2条可能的路径来计算期权支付的预期值。缺失纵向数据的模式混合模型提供了涉及重组二叉树的第二个示例。这里给出了一个简要的概述，而本文的其余部分则侧重于期权定价应用程序。在模式混合模型[4]中，每个受试者都有缺失值的纵向数据，并且考虑了给定缺失模式的数据的条件分布。让Yitbe为受试者i在时间t的响应，其中i=1，n和t=1，T多元响应Yi=（Yi1，…，YiT）可能包含缺失数据，其模式由Zi=（Zi1，…）表示。

，青春痘）；如果观察到Yitis，则Zitis为0，如果缺失，则为1。Hosseini和Neerchal【5】已将该框架应用于老年医学研究，其中护理人员在某些情况下代表患者提供响应，而患者自己在其他时间做出响应。这种模型的观测{（Yi，Zi）：i=1，…，n}的联合分布由nyi=1f（Yi | Zi，θ）g（Zi |θ），（1.1）给出，其中f和g分别是Yi | Zi和Zi的概率函数。注意，关于z的期望值计算将涉及所有贝努利路径z的求和。在重组二叉树的应用中，例如前面提到的两个，通常需要计算函数V（X）E[V（X）]=Xx的期望值∈BNV（x）p（x）。（1.2）期权价值计算和模式混合可能性（1.1）均采用这种形式。函数V（x）可能取决于整个路径x，而不仅仅取决于叶节点。请注意，（1.2）是2Nterms上的求和，因此随着N的增加，通过完全枚举进行计算很快变得不可行。在这项工作中，我们提出了一种在多处理器计算环境中并行计算的方法。在期权估价问题中，对期权进行估价的常用方法是使用一种有效的反向诱导方法，而不考虑（1.2）中的第2项。所提出的并行化方法适用于高级路径相关选项，这些选项是通过重组二叉树的采样路径进行估值的，而不是通过反向归纳进行估值的【6，第4章】。

我们的方法使用单程序多数据（SP MD）方法[7]，其中M个进程中的每个进程都确定其指定的BN子集，而无需中央进程的协调。因此，计算可以转化为一个令人尴尬的并行问题[8]，在这个问题中，进程不需要通信，除非在计算结束时，因此可以有效地对许多进程进行分级。即使有大量进程M，路径2n的数量也会随着N的增加而迅速变得非常大。因此，我们考虑一种分区MonteCarlo方法，该方法使用类似的并行化来减少相对于basicMonte Carlo的近似误差。论文的其余部分组织如下。第2节介绍了使用伯努利路径对选项进行估值的二进制树模型。第3节描述了一个精确计算期望值的并行方案。第4节介绍了近似计算期望值的分区蒙特卡罗方法。第5节介绍了R和Julia中自动选项方法的实施结果。C第6.2节给出了包括在内的备注。使用二叉树模型对路径依赖型期权进行估值期权是一种金融合同，赋予所有者在预先指定的未来日期以预先指定的价格购买或出售一定数量股票的权利，但不是义务。出售期权赋予所有者购买股份的权利，而看跌期权赋予所有者出售股份的权利。有几个因素用于评估期权的价值。执行价格K是一个预先指定的执行价格。时间T为未来到期日；对于本文所考虑的欧式期权，期权只能在时间T行使，随后变得一文不值。期权的价值是买方在购买期权时愿意支付的金额。

这取决于K、T和标的股票的特征。更正式地说，让V（St）表示在时间t时期权的价值，此时标的股票的价格为St。我们假设在时间t=0时开始购买或出售期权。目标是计算V（S），即t=0时选项的值。虽然t<t的V（St）未知，但V（St）值（称为Payo ff）是确定的。看涨期权在到期时的价值V（ST）为nbyv（ST）=m ax{ST- K、 0}。（2.1）对于看跌期权，到期时T的值由V（ST）=max{K给出- ST，0}。（2.2）请注意，在（2.1）和（2.2）中，支付V（ST）仅取决于时间T、ST的股票价格和行权价格K。在更复杂的期权中，支付通常取决于其他因素。例如，路径依赖型期权的支付取决于某个时间段内股票的历史价格。目前，我们将把注意力限制在（2.1）和（2.2）中的简单选项上。期权估值的二叉树方法基于使用重组二叉树模拟t=0和t之间标的股票未来价格的演变。我们将间隔[0，T]划分为等距时间步。我们选择N作为时间步数，它决定了树的大小，并将δt=t/N作为每个时间步的大小。表示i=0时的ti=iδt，N作为不同的时间点。想象一个二维网格，横轴为t，纵轴为股票价格t；通过离散化时间，我们将水平轴切成等距的时间步长。接下来，我们离散化Stat每个t=tiresulting in value Stij，其中jis是纵轴上的指数。为了便于注释，我们将写Stijas Sij。

binomialtree方法作出以下假设。A1股票价格在时间步长δt内仅取两个可能值：价格上升至Tiu或下降至ti+1时的Stid，0<d<u，其中u是向上移动的因子，d是向下移动的因子。为了加强模拟股票价格的对称性，我们假设ud=1。A2在时间Tian和ti+1之间上移的概率为p f或i=0，N- 1.A3 E（Sti+1 | Sti）=Stieqδt，其中q是年度风险利率。例如，q可能是高信用银行储蓄账户的利率。在假设A1-A3下，如果假设股票价格变动与方差σ呈对数正态分布，则可以显示u=β+pβ+1，p=（等式δt- d） /（u- d） ，β=（e-qδt+e（q+σ）δt）。标准偏差σ也称为股票的波动率。有关derivingu和p的更多详细信息，请参见Hull[2]或Seydel[3]。上述描述严格遵循Seydel【3】第1.4节的符号和发展。从市场S中的当前股票价格开始，使用u和p构建可能的未来股票价格的网格Sijis。算法1展示了构建模拟未来股票价格的二叉树的过程，并计算看涨期权在时间T的支付，其中，V（ST）由时间T的每个j的（2.1）给出。因此，VNj=max{SNj- K、 0}，j=0，N、 其中Vijis V（Sij）。图e2.1显示了一个两步重组二叉树，用于从股票价格S开始的买入期权，股票价格演变和期权支付。为了计算期权值V（S），必须计算到达树的每个叶节点的概率。这些可以从遍历N维伯努利路径的概率中获得。

由于我们假设p从A2开始是常数，所有上下移动次数相同的路径都具有相同的被遍历概率。算法1构建股票价格的网格，并计算二项式方法的期权支付。对于i=1，2，N剂量=Sujdi-j=0，1，对于j=0，N doVNj← 最大{SNj- K、 SDSUSD2v20=最大值（Sd2）的0}结束- K、 0）SduV21=最大值（Sdu- K、 0）Su2V22=最大值（Su2- K、 0）（1- p） pp2p（1- p） （1）- p） p（1- p） 2图2.1：具有看涨期权支付的两s tep重组二叉树。期权值V（s）计算为在年利率q asV（s）=e下贴现至启动时间t=0的预期支付-qTNXi=0p（i）VNi=e-qTNXi=0镍pi（1- p） N个-iVNi，（2.3），其中p（i）=镍pi（1- p） N个-iis遍历以叶节点i结束的路径的概率，whosepayo fff是VNi。设X=（X，…，XN）表示伯努利路径，其中每个Xi~ 伯努利（p）独立，对于i=1，N、 图2.2显示了图2.1中的两步二叉树，其中到叶节点的伯努利路径显示为向量。路径x的概率由p（x=x）=px′（1）给出- p） N个-x′，其中1是1的N维向量。因为有镍到达叶节点i的方式，P{到达终端节点i}=镍pi（1- p） N个-i=Xx∈BN:x′1=ipx′（1- p） N个-x′。（2.4）SSdSuSd2；（0，0）Sud；（1，0）Sdu；（0，1）Sd2；(1, 1)(1 - p） pp2p（1- p） （1）- p） p（1- p） 2图2.2：具有伯努利路径的两步二叉树。将（2.3）中的（2.4）代入，我们得到v（S）=e-qTNXi=0VNiXx∈BN:x′1=ipx′（1- p） N个-x′。（2.5）如果每个时间步上下移动的幅度和概率是恒定的，则使用（2.5）而不是（2.3）评估期权价值的计算优势很小。

然而，如果树是使用时变的上下移动来构建的，并且在时间t时上下移动的对应概率为pto，或者如果路径x依赖于路径，则不能使用（2.3）中的模型。设p（x）为穿过伯努利路径x的概率，VN（x）为相应的支付。因此，伯努利路径的空间为BN，（2.5）becomesV（S）=e-qTNXi=0Xx∈BN:x′1=ip（x）VN（x）=e-qTXx∈BNVN（x）p（x），（2.6），其中p（x）=QNi=1pI（xi=1）i（1- pi）I（xi=0），I是指示函数。注意，（2.6）与（1.2）相似。我们试图将（2.6）中期权价值V（S）的计算或（1.2）中预期值的计算并行化。3、并行伯努利路径算法随着N的增加，期望值（2.6）的计算迅速变得昂贵，因为必须考虑2NBernoullipaths。例如，取N=24会产生16777216条可能的路径。通过注意到问题是令人尴尬的并行问题，多个处理器可以有效地分担计算负担。Ganesan等人【9】和Kolb及Pharr【10】等提出了基于二叉树中的反向归纳法评估期权定价模型的并行方法。据我们所知，以前从未考虑过使用伯努利路径并行化期望值计算的方法。在我们之前的工作中，Popuri等人[11]使用了一种主-工作者范式，其中主流程构建tr ee，计算报酬，将终端节点分配给工作者流程，并从每个workerprocess收集计算值以构建最终结果。尽管在计算过程中各进程之间没有相互通信，但主进程和工作进程之间有大量的初始通信。我们的方法基于SPMD范式，即在所有进程上并行执行单个程序。