# Randomized Binomial Tree and Pricing of American-Style Options

Authors: Hu Xiaoping; Cao Jie
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Randomized binomial tree and methods for pricing American options were studied. Firstly, both the completeness and the no-arbitrage conditions in the randomized binomial tree market were proved. Secondly, the description of the node was given, and the cubic polynomial relationship between the number of nodes and the time steps was also obtained. Then, the characteristics of paths and storage structure of the randomized binomial tree were depicted. Then, the procedure and method for pricing American-style options were given in a random binomial tree market. Finally, a numerical example pricing the American option was illustrated, and the sensitivity analysis of parameter was carried out. The results show that the impact of the occurrence probability of the random binomial tree environment on American option prices is very significant. With the traditional complete market characteristics of  random binary and a stronger ability to describe, at the same time, maintaining a computational feasibility, randomized binomial tree is a kind of promising method for pricing financial derivatives.


---

## Body

## 1. Introduction

Cox et al. [1] proposed binomial option pricing method, which can approach the continuous-time option price shown by Black and Scholes [2] and Merton [3]. As Binomial option pricing method is simple and flexible to price all kinds of complex derivatives, and easy to realize the computer programming, it has become one of the mainstream methods of pricing derivatives, and also one of the frontiers and hot researches on pricing derivatives for decades. Benninga and Wiener and Tian researched the relative properties of the binary tree and priced complex financial derivatives by binary tree to improve the computational efficiency of binary tree algorithm [4, 5]. Rubinstein [6] expanded the built Edgeworth binary tree with random distribution of Edgeworth, which effectively involved the information of randomly distributed skewness and kurtosis, and made binary tree approach nonnormal distribution when applied to option pricing. Walsh [7] proved the effectiveness of binary tree algorithm via the study of the convergence and convergence speed problems of binary method from the theoretical point of view. Gerbessiotis [8] gave a parallel binomial option pricing method with independent architecture, studied algorithm parameter adjustment method of achieving the optimal theory acceleration, and verified the feasibility and effectiveness of the algorithm under different parallel computing environments. Georgiadis [9] tested that there is no so-called closed-form solution when pricing options with binary tree method. Simonato [10] posed Johnson binary tree based on the approximation to Johnson distribution of the random distribution, overcoming some possible problems in Edgeworth binary tree that the combination of skewness and kurtosis cannot constitute qualified random distribution. Due to the theory that Hermite orthogonal polynomials can approximate random distribution with the arbitrary precision, Leccadito et al. [11] raised the Hermite binary tree, which can contain any high-order moments of random distribution, and overcame the problem of numerical instability in Johnson binary tree. Cui et al., Qin et al., and Huang et al. studied the application of functional differential equations to pricing derivatives [12–14]. Wen et al. investigated the impact of the high-order moment and correlation on the prices of options [15, 16]. Yuen et al. [17] constructed a self-exciting threshold binomial model for pricing options. Aluigi et al. [18] introduced a fast and accurate derivatives pricing method based on the application of the Chapman-Kolmogorov equation, which has an intuitive lattice representation and is able to price a wide range of derivatives. Jimmy [19] proposed robust binomial lattices for pricing derivatives where probabilities can be chosen to match local densities. However, in the traditional binary tree market, if the formed combination (
u
,
d
) of the upward movement u and downward movement d is seen as a market environment (known by the binary theory; (
u
,
d
) determines the unique market volatility σ), there is only an environment in the traditional binary tree market and at each node the binary tree moved upward u or downward d only once (it means that market volatility is the same at any time). However, this assumption is far from the reality of the financial markets, because the stock prices will respond immediately to the various information from domestic and abroad, and thus it is very sensitive. For example, a sudden change in the risk-free interest rate, the conflict with its neighbor countries, good performance of the rival company, a new CEO, and other random emergency information will lead to great fluctuation in stock prices.Ganikhodjaev and Bayram and Kamola and Nasir [20–22] put forward the random binary tree applied to European option pricing. In this random binary tree market, there are at least two market environments, one of which (
u
1
,
d
1
) represents the normal state of the market while the other (
u
2
,
d
2
) is the abnormal state of the market. Therefore, the first market environment (
u
1
,
d
1
) which represents the normal state of the market corresponds to smaller market volatility and larger probability and the second market environment (
u
2
,
d
2
) has larger market volatility and smaller probability. The contribution of this paper is studying the related properties of random binary tree from the viewpoint of complete market and the number of nodes, giving the storage structure of random binary, describing the path characteristics of random binary tree, and researching the American option pricing problem under the random binary market.The other sections of this paper are as follows. In Section2, we introduce random binary tree and its properties; the American option pricing problem under random binary environment is studied in Section 3; In Section 4, we demonstrate the effectiveness of the algorithm through a numerical example and study the parameters sensitivity of relevant model.


## 2. Randomized Binary Tree

### 2.1. Random Walks in an Independent Environment

Solomon [23] is the first person to study random walks in an independent environment in the integer field. Let a
n
(
0
≤
a
n
≤
1, for all n
∈
Z
) be a sequence of independent and identically distributed random variables; then the random walks in an independent environment in the integer domain are a random sequence {
x
n
}, where x
0
=
0 and x
n
+
1
=
x
n
+
1
,
x
n
-
1, the occurrence probability of x
n
+
1
=
x
n
+
1 is a
n
x
n, and the probability of x
n
+
1
=
x
n
-
1 is 1
-
a
n
x
n. Solomon noted that random environment in a certain sense slowed random walk down. And Menshikov [24] studied the asymptotic behavior of random walks in an independent environment.


### 2.2. Randomized Binary Tree

Ganikhodjaev and Bayram and Kamola and Nasir [20–22] raised the concept of a random binary tree based on the theory of random walks in an independent environment. In the traditional model of the binary tree, the stock price moves upward u in a certain probability or moves downward d in a certain probability at each time node. (
u
,
d
) is named as the environment of binary tree and it is the same at any time in the traditional binary tree. In the random binary tree model, U
n and D
n are independent and identically distributed random variables. U
n can only take two values u
1, u
2 and D
n can only take two values d
1, d
2. Random market environment describes two market environments (
u
1
,
d
1
) and (
u
2
,
d
2
), where the probability of market environment (
u
1
,
d
1
) is α
(
0
≤
α
≤
1
) and the other is 1
-
α.Theorem 1.
If the following condition is satisfied, the random binary tree market must be a market with no arbitrage:(1)
max
⁡
(
d
1
,
d
2
)
<
R
<
min
⁡
(
u
1
,
u
2
)
,
where R is the risk-free discount factor and the probability of market environment α is given.Proof.
See reference [20–22].
Compared with the theorem given in [20–22], Theorem 1 puts forward another condition that the probability of market environment α is given. In fact, if this condition is not given, we cannot draw the conclusion that the random binary market is complete although p
1, p
2 are uniquely determined when calculating risk-neutral probabilities, for α is arbitrary; thus there will be infinitely many unconditional risk-neutral probabilities. In this paper, Theorem 1 shows that, under appropriate conditions, random binary market is a market with no arbitrage as the traditional binary market. That is to say, although there are four successor nodes following each node of random binary tree, it is totally different with quadtree in the incomplete market. Denote the stock price in the first period by S; then the stock price in the Nth period is
(2)
S
u
1
n
-
i
d
1
i
u
2
N
-
n
-
j
d
2
j
,
where n
=
0,1
,
2
,
…
,
N,i
=
0,1
,
2
,
…
,
n, and j
=
0,1
,
2
,
…
,
N
-
n.Theorem 2.
When the random binary tree is in theNth period, the total number of nodes is
(3)
1
6
N
3
+
N
2
+
11
6
N
+
1
.Proof.
As known by the above equation, for each givenn, there are n
+
1 kinds of situations for the market environment (
u
1
,
d
1
). But now, there are N
-
n
+
1 kinds of market situations for the market environment (
u
2
,
d
2
). It means if the n is given, the corresponding quantity of the nodes in the random binary tree is as follows:
(4)
(
n
+
1
)
(
N
-
n
+
1
)
.
In theNth period, n
=
0,1
,
2
,
…
,
N; therefore there are
(5)
∑
n
=
0
N
(
n
+
1
)
(
N
-
n
+
1
)
=
1
6
N
3
+
N
2
+
11
6
N
+
1
nodes in the random binary tree. The proof is over.As can be seen from Theorem2, the number of nodes in random binary tree is the cubic polynomial of period, which avoid the problem that the number of nodes shows explosive growth with the increase of N when the number of nodes is the exponential function of period (such as 4
N) and makes it computationally feasible. The number of nodes in random binary tree decreases from nonrecombinant 4
N down to the cubic polynomial of N, so there are all kinds of restructuring its path, and it is more difficult to show its nodes and describe its path.As can be seen from the formula and the proof of Theorem2, random binary tree nodes can be described by the four-tuple as follows:
(6)
(
N
,
n
,
i
,
j
)
,
where n
=
0,1
,
2
,
…
,
N, i
=
0,1
,
2
,
…
,
n, and j
=
0,1
,
2
,
…
,
N
-
n
,
N, N is the period, n is the occurrence number of market environment (
u
1
,
d
1
), the occurrence number of market environment (
u
2
,
d
2
) is N
-
n, i represents that the frequency of u
1 is n
-
i under the market environment (
u
1
,
d
1
), which of d
1 is i, and j represents that the frequency of u
2 is N
-
n
-
j under the market environment (
u
2
,
d
2
), which of d
2 is j.There is a one-to-one relationship between the four-tuple given by formula (6) and the stock price in formula (2). Therefore in the rest of the paper, we often use the four-tuple instead of the stock price in formula (2) without explanation in order to symbol simplicity.In the random binary tree, the child nodes of the node(
N
,
n
,
i
,
j
) are
(7)
(
N
+
1
,
n
+
1
,
i
,
j
)
,
(
N
+
1
,
n
+
1
,
i
+
1
,
j
)
,
(
N
+
1
,
n
,
i
,
j
)
,
(
N
+
1
,
n
,
i
,
j
+
1
)
,
where the former two nodes correspond to the market environment (
u
1
,
d
1
) and the latter two nodes are for the market environment (
u
2
,
d
2
). To facilitate the calculation process, it must map random binary tree node representation in the four-tuple given by formula (6) to one-dimensional representation. Let
(8)
index
=
∑
m
≥
0
,
m
=
0
n
-
1
(
m
+
1
)
(
N
-
m
+
1
)
+
(
N
-
n
+
1
)
i
+
j
+
1
=
1
6
(
3
N
-
2
n
)
n
2
+
1
2
(
N
+
n
)
n
+
5
6
n
+
(
N
-
n
+
1
)
i
+
j
+
1
.Theorem 3.
If the value ofN is given and the values obtained from four-tuple (
N
,
n
1
,
i
1
,
j
1
) and four-tuple (
N
,
n
2
,
i
2
,
j
2
) by mapping are equal, that is, i
n
d
e
x
1
=
i
n
d
e
x
2, then n
1
=
n
2
,
i
1
=
i
2
,
j
1
=
j
2 must exist; that is, the four-tuple (
N
,
n
1
,
i
1
,
j
1
) is equal to the four-tuple (
N
,
n
2
,
i
2
,
j
2
).Proof.
For(9)
0
=
inde
x
1
-
inde
x
2
=
(
1
6
(
3
N
-
2
n
1
)
n
1
2
+
1
2
(
N
+
n
1
)
n
1
+
5
6
n
1
+
(
N
-
n
1
+
1
)
i
1
+
j
1
+
1
)
-
(
1
6
(
3
N
-
2
n
2
)
n
2
2
+
1
2
(
N
+
n
2
)
n
2
+
5
6
n
2
1
6
+
(
N
-
n
2
+
1
)
i
2
+
j
2
+
1
)
.
Supposingn
1
≠
n
2, we might as well set n
1
>
n
2; then
(10)
inde
x
1
-
inde
x
2
>
(
1
6
(
3
N
-
2
(
n
2
+
1
)
)
(
n
2
+
1
)
2
+
1
2
(
N
+
(
n
2
+
1
)
)
(
n
2
+
1
)
+
5
6
(
n
2
+
1
)
+
1
)
-
(
1
6
(
3
N
-
2
n
2
)
n
2
2
+
1
2
(
N
+
n
2
)
n
2
+
5
6
n
2
+
(
N
-
n
2
+
1
)
n
2
+
(
N
-
n
2
)
+
1
1
6
)
=
1
>
0
which is in contradiction with inde
x
1
-
inde
x
2
=
0. Therefore if inde
x
1
-
inde
x
2
=
0, then n
1
=
n
2
=
n.
Suppose further that wheninde
x
1
-
inde
x
2
=
0,n
1
=
n
2, i
1
≠
i
2, and we might as well let i
1
>
i
2; then
(11)
inde
x
1
-
inde
x
2
=
(
N
-
n
+
1
)
(
i
1
-
i
2
)
+
(
j
1
-
j
2
)
>
N
-
n
+
1
+
(
j
1
-
j
2
)
forj
1
,
j
2
=
0,1
,
2
,
…
,
N
-
n.
Therefore(12)
inde
x
1
-
inde
x
2
>
N
-
n
+
1
-
(
N
-
n
)
=
1
>
0
,
which is contradictory. So i
1
=
i
2 must exist. Obviously, when n
1
=
n
2,i
1
=
i
2, there must be j
1
=
j
2, and the theorem is correct. The proof is over.Theorem3 shows that in mapping there is a one-to-one mapping relation between random binary tree node and a group of the array. A random binary tree node uniquely corresponds to an element in one-dimensional array and an element in one-dimensional array uniquely corresponds to a random binary tree node.Suppose that the probability ofu
1 under the market environment (
u
1
,
d
1
) is p
1
(
0
<
p
1
<
1
) and which of d
1 is 1
-
p
1 and that the probability of u
2 under the market environment (
u
2
,
d
2
) is p
2
(
0
<
p
2
<
1
) and which of d
2 is 1
-
p
2.Theorem 4.
In the random binary tree, the unconditional probability of four child nodes(
N
+
1
,
n
+
1
,
i
,
j
),(
N
+
1
,
n
+
1
,
i
+
1
,
j
),(
N
+
1
,
n
,
i
,
j
), and(
N
+
1
,
n
,
i
,
j
+
1
)  of any node  (
N
,
n
,
i
,
j
) are, respectively, α
p
1,a
(
1
-
p
1
),(
1
-
α
)
p
2, and (
1
-
α
)
(
1
-
p
2
).The proof is dropped.It is easy to obtain the result of Theorem4 by making use of the Bayesian rule. With the help of Theorem 4, we can compute the expectation of random distribution and furthermore give the price of complex derivatives.


## 2.1. Random Walks in an Independent Environment

Solomon [23] is the first person to study random walks in an independent environment in the integer field. Let a
n
(
0
≤
a
n
≤
1, for all n
∈
Z
) be a sequence of independent and identically distributed random variables; then the random walks in an independent environment in the integer domain are a random sequence {
x
n
}, where x
0
=
0 and x
n
+
1
=
x
n
+
1
,
x
n
-
1, the occurrence probability of x
n
+
1
=
x
n
+
1 is a
n
x
n, and the probability of x
n
+
1
=
x
n
-
1 is 1
-
a
n
x
n. Solomon noted that random environment in a certain sense slowed random walk down. And Menshikov [24] studied the asymptotic behavior of random walks in an independent environment.


## 2.2. Randomized Binary Tree

Ganikhodjaev and Bayram and Kamola and Nasir [20–22] raised the concept of a random binary tree based on the theory of random walks in an independent environment. In the traditional model of the binary tree, the stock price moves upward u in a certain probability or moves downward d in a certain probability at each time node. (
u
,
d
) is named as the environment of binary tree and it is the same at any time in the traditional binary tree. In the random binary tree model, U
n and D
n are independent and identically distributed random variables. U
n can only take two values u
1, u
2 and D
n can only take two values d
1, d
2. Random market environment describes two market environments (
u
1
,
d
1
) and (
u
2
,
d
2
), where the probability of market environment (
u
1
,
d
1
) is α
(
0
≤
α
≤
1
) and the other is 1
-
α.Theorem 1.
If the following condition is satisfied, the random binary tree market must be a market with no arbitrage:(1)
max
⁡
(
d
1
,
d
2
)
<
R
<
min
⁡
(
u
1
,
u
2
)
,
where R is the risk-free discount factor and the probability of market environment α is given.Proof.
See reference [20–22].
Compared with the theorem given in [20–22], Theorem 1 puts forward another condition that the probability of market environment α is given. In fact, if this condition is not given, we cannot draw the conclusion that the random binary market is complete although p
1, p
2 are uniquely determined when calculating risk-neutral probabilities, for α is arbitrary; thus there will be infinitely many unconditional risk-neutral probabilities. In this paper, Theorem 1 shows that, under appropriate conditions, random binary market is a market with no arbitrage as the traditional binary market. That is to say, although there are four successor nodes following each node of random binary tree, it is totally different with quadtree in the incomplete market. Denote the stock price in the first period by S; then the stock price in the Nth period is
(2)
S
u
1
n
-
i
d
1
i
u
2
N
-
n
-
j
d
2
j
,
where n
=
0,1
,
2
,
…
,
N,i
=
0,1
,
2
,
…
,
n, and j
=
0,1
,
2
,
…
,
N
-
n.Theorem 2.
When the random binary tree is in theNth period, the total number of nodes is
(3)
1
6
N
3
+
N
2
+
11
6
N
+
1
.Proof.
As known by the above equation, for each givenn, there are n
+
1 kinds of situations for the market environment (
u
1
,
d
1
). But now, there are N
-
n
+
1 kinds of market situations for the market environment (
u
2
,
d
2
). It means if the n is given, the corresponding quantity of the nodes in the random binary tree is as follows:
(4)
(
n
+
1
)
(
N
-
n
+
1
)
.
In theNth period, n
=
0,1
,
2
,
…
,
N; therefore there are
(5)
∑
n
=
0
N
(
n
+
1
)
(
N
-
n
+
1
)
=
1
6
N
3
+
N
2
+
11
6
N
+
1
nodes in the random binary tree. The proof is over.As can be seen from Theorem2, the number of nodes in random binary tree is the cubic polynomial of period, which avoid the problem that the number of nodes shows explosive growth with the increase of N when the number of nodes is the exponential function of period (such as 4
N) and makes it computationally feasible. The number of nodes in random binary tree decreases from nonrecombinant 4
N down to the cubic polynomial of N, so there are all kinds of restructuring its path, and it is more difficult to show its nodes and describe its path.As can be seen from the formula and the proof of Theorem2, random binary tree nodes can be described by the four-tuple as follows:
(6)
(
N
,
n
,
i
,
j
)
,
where n
=
0,1
,
2
,
…
,
N, i
=
0,1
,
2
,
…
,
n, and j
=
0,1
,
2
,
…
,
N
-
n
,
N, N is the period, n is the occurrence number of market environment (
u
1
,
d
1
), the occurrence number of market environment (
u
2
,
d
2
) is N
-
n, i represents that the frequency of u
1 is n
-
i under the market environment (
u
1
,
d
1
), which of d
1 is i, and j represents that the frequency of u
2 is N
-
n
-
j under the market environment (
u
2
,
d
2
), which of d
2 is j.There is a one-to-one relationship between the four-tuple given by formula (6) and the stock price in formula (2). Therefore in the rest of the paper, we often use the four-tuple instead of the stock price in formula (2) without explanation in order to symbol simplicity.In the random binary tree, the child nodes of the node(
N
,
n
,
i
,
j
) are
(7)
(
N
+
1
,
n
+
1
,
i
,
j
)
,
(
N
+
1
,
n
+
1
,
i
+
1
,
j
)
,
(
N
+
1
,
n
,
i
,
j
)
,
(
N
+
1
,
n
,
i
,
j
+
1
)
,
where the former two nodes correspond to the market environment (
u
1
,
d
1
) and the latter two nodes are for the market environment (
u
2
,
d
2
). To facilitate the calculation process, it must map random binary tree node representation in the four-tuple given by formula (6) to one-dimensional representation. Let
(8)
index
=
∑
m
≥
0
,
m
=
0
n
-
1
(
m
+
1
)
(
N
-
m
+
1
)
+
(
N
-
n
+
1
)
i
+
j
+
1
=
1
6
(
3
N
-
2
n
)
n
2
+
1
2
(
N
+
n
)
n
+
5
6
n
+
(
N
-
n
+
1
)
i
+
j
+
1
.Theorem 3.
If the value ofN is given and the values obtained from four-tuple (
N
,
n
1
,
i
1
,
j
1
) and four-tuple (
N
,
n
2
,
i
2
,
j
2
) by mapping are equal, that is, i
n
d
e
x
1
=
i
n
d
e
x
2, then n
1
=
n
2
,
i
1
=
i
2
,
j
1
=
j
2 must exist; that is, the four-tuple (
N
,
n
1
,
i
1
,
j
1
) is equal to the four-tuple (
N
,
n
2
,
i
2
,
j
2
).Proof.
For(9)
0
=
inde
x
1
-
inde
x
2
=
(
1
6
(
3
N
-
2
n
1
)
n
1
2
+
1
2
(
N
+
n
1
)
n
1
+
5
6
n
1
+
(
N
-
n
1
+
1
)
i
1
+
j
1
+
1
)
-
(
1
6
(
3
N
-
2
n
2
)
n
2
2
+
1
2
(
N
+
n
2
)
n
2
+
5
6
n
2
1
6
+
(
N
-
n
2
+
1
)
i
2
+
j
2
+
1
)
.
Supposingn
1
≠
n
2, we might as well set n
1
>
n
2; then
(10)
inde
x
1
-
inde
x
2
>
(
1
6
(
3
N
-
2
(
n
2
+
1
)
)
(
n
2
+
1
)
2
+
1
2
(
N
+
(
n
2
+
1
)
)
(
n
2
+
1
)
+
5
6
(
n
2
+
1
)
+
1
)
-
(
1
6
(
3
N
-
2
n
2
)
n
2
2
+
1
2
(
N
+
n
2
)
n
2
+
5
6
n
2
+
(
N
-
n
2
+
1
)
n
2
+
(
N
-
n
2
)
+
1
1
6
)
=
1
>
0
which is in contradiction with inde
x
1
-
inde
x
2
=
0. Therefore if inde
x
1
-
inde
x
2
=
0, then n
1
=
n
2
=
n.
Suppose further that wheninde
x
1
-
inde
x
2
=
0,n
1
=
n
2, i
1
≠
i
2, and we might as well let i
1
>
i
2; then
(11)
inde
x
1
-
inde
x
2
=
(
N
-
n
+
1
)
(
i
1
-
i
2
)
+
(
j
1
-
j
2
)
>
N
-
n
+
1
+
(
j
1
-
j
2
)
forj
1
,
j
2
=
0,1
,
2
,
…
,
N
-
n.
Therefore(12)
inde
x
1
-
inde
x
2
>
N
-
n
+
1
-
(
N
-
n
)
=
1
>
0
,
which is contradictory. So i
1
=
i
2 must exist. Obviously, when n
1
=
n
2,i
1
=
i
2, there must be j
1
=
j
2, and the theorem is correct. The proof is over.Theorem3 shows that in mapping there is a one-to-one mapping relation between random binary tree node and a group of the array. A random binary tree node uniquely corresponds to an element in one-dimensional array and an element in one-dimensional array uniquely corresponds to a random binary tree node.Suppose that the probability ofu
1 under the market environment (
u
1
,
d
1
) is p
1
(
0
<
p
1
<
1
) and which of d
1 is 1
-
p
1 and that the probability of u
2 under the market environment (
u
2
,
d
2
) is p
2
(
0
<
p
2
<
1
) and which of d
2 is 1
-
p
2.Theorem 4.
In the random binary tree, the unconditional probability of four child nodes(
N
+
1
,
n
+
1
,
i
,
j
),(
N
+
1
,
n
+
1
,
i
+
1
,
j
),(
N
+
1
,
n
,
i
,
j
), and(
N
+
1
,
n
,
i
,
j
+
1
)  of any node  (
N
,
n
,
i
,
j
) are, respectively, α
p
1,a
(
1
-
p
1
),(
1
-
α
)
p
2, and (
1
-
α
)
(
1
-
p
2
).The proof is dropped.It is easy to obtain the result of Theorem4 by making use of the Bayesian rule. With the help of Theorem 4, we can compute the expectation of random distribution and furthermore give the price of complex derivatives.


## 3. Pricing American Options Based on Randomized Binomial Tree

Suppose risk-free rate isr, R
=
e
r
Δ
T is the risk-free discount factor, T is option maturity, Δ
T
=
T
/
N is the time of each period of random binary tree, and N is the periods of random binary tree. According to the principle of risk-neutral pricing, we can get
(13)
p
1
=
R
-
d
1
u
1
-
d
1
,
p
2
=
R
-
d
2
u
2
-
d
2
.
Set American options maturity is T, the payoff function is f
(
(
N
,
n
,
i
,
j
)
,
K
), and K is the option strike price. American option pricing under random binary tree still uses the backward induction method; the specific calculating steps are as follows.Step 1.
On the American option expiry dateT (the N
th period of the random binary tree), calculating the immediate strike price f
(
(
N
,
n
,
i
,
j
)
,
K
) at each node, this moment American option price is V
(
(
N
,
n
,
i
,
j
)
)
=
f
(
(
N
,
n
,
i
,
j
)
,
K
).Step 2.
When the periodm
=
1,2
,
…
,
N
-
1, for each node (
m
,
n
,
i
,
j
) in this period, calculate the immediate strike pricef
(
(
m
,
n
,
i
,
j
)
,
K
) of American option of this node and then calculate the value of American option to continue to hold
(14)
c
(
(
m
,
n
,
i
,
j
)
)
=
1
R
{
a
p
1
V
(
(
m
+
1
,
n
,
i
,
j
)
)
+
a
(
1
-
p
1
)
V
(
(
m
+
1
,
n
,
i
+
1
,
j
)
)
+
(
1
-
a
)
p
2
V
(
(
m
+
1
,
n
+
1
,
i
,
j
)
)
+
(
1
-
a
)
×
(
1
-
p
2
)
V
(
(
m
+
1
,
n
+
1
,
i
,
j
+
1
)
)
}
.
The value of American option at node (
m
,
n
,
i
,
j
) is
(15)
V
(
(
m
,
n
,
i
,
j
)
)
=
max
⁡
(
f
(
(
m
,
n
,
i
,
j
)
,
K
)
,
c
(
(
m
,
n
,
i
,
j
)
)
)
.Step 3.
The initial value of American option is(16)
V
=
V
(
(
0,0
,
0,0
)
)
=
1
R
{
a
p
1
V
(
(
1,0
,
0,0
)
)
+
a
(
1
-
p
1
)
V
(
(
1,0
,
1,0
)
)
+
(
1
-
a
)
p
2
V
(
(
1,1
,
0,0
)
)
+
(
1
-
a
)
(
1
-
p
2
)
V
(
(
1,1
,
0,1
)
)
}
.


## 4. A Numerical Example

Let the first market environmentu
1
=
1.1,d
1
=
0.9, the second market environment u
2
=
1.4,d
2
=
0.7, continuous risk-free year rate r
=
12
%, and initial stock price S
=
20; then f
(
x
,
K
)
=
max
⁡
(
K
-
x
,
0
) is the payoff function of American put option, where maturity T
=
0.5 year and N
=
100. In Figure 1 there are five curves corresponding to strike price K
=
24
,
22
,
20
,
18
,
16, respectively; the horizontal axis is the occurrence probability α of the first market environment, and the vertical axis represents the initial price of American option.Figure 1
The relation of American put option price and market environment occurrence probability.As we know from Figures1 and 2, whether the real option, at-the-money option, or out-of-the-money option, the prices of American put option and American call option both decrease as the occurrence probability α increases under the first market environment (
u
1
,
d
1
). However, the market volatility under the first market environment (
u
1
,
d
1
) is less than that under the second market environment (
u
2
,
d
2
). What is more, there is only one market environment in the traditional binomial model, and the corresponding market volatility only considers the normal volatility of the market; thus the traditional binary model, compared with random binary tree model, underestimated the American put and call option price.Figure 2
The relation of American call option price and market environment occurrence probability.


## 5. Conclusion

In this paper we studied the completeness and nonarbitrage of random binary tree and gave the node representation of the random binary tree as well as describing the path representation method of random binary tree. Based on the backward induction method, the steps and the procedures were shown. Through the numerical example, we studied the sensitivity analysis of American put option price to the random binary tree parameters.Randomized binary tree maintains the complete-market character of the traditional binary tree; moreover it has a stronger ability to describe and the quantity of nodes is cubic polynomial of the number of periods which makes the calculation feasible. The future research can be extended into two directions: one is to combine with Johnson binary tree and Hermite binary tree so as to further study the relevant characteristics of random binary tree; the other direction is to research other options pricing dependence on the path, such as Asian options, barrier options, and look-back options under the random binary environment.



---

*Source: 291737-2014-03-12.xml*