# Parallelizing Computation of Expected Values in Recombinant Binomial Trees

Source: [Parallelizing Computation of Expected Values in Recombinant Binomial Trees](<https://www.sota2.com/research/paper/68fa7ca31e209131cea8eea2>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-26T06:04:59.824Z

Authors: Sai K. Popuri, Andrew M. Raim, Nagaraj K. Neerchal, Matthias K. Gobbert

Published: 2017-01-12T21:34:48.000Z

## Abstract

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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1701.03512>)

[PDF](<https://arxiv.org/pdf/1701.03512.pdf>)