# Trinomial trees simulation

We consider a diffusion process $$X_t$$ which evolves according to $dX_t = \mu(t,X_t)dt + \sigma(t,X_t)dW_t$ where $$\mu$$ and $$\sigma$$ are smooth scalar real functions and $$W_t$$ is a scalar standard Brownian motion.

We observe the process on the time interval $$[0,T]$$ and we make the time discretization $$t_0 = 0, t_1 = \frac T N, \ldots, t_N = T$$.

We will see three different trinomial trees constructions.

#### Basic trinomial tree

At each time step $$i$$, starting form $$x_{i,j}$$ the process can go up, straight or down as follows :

$\begin{cases} x_{i+1,j+1}= x_{i,j} + (j+1)\Delta x_{i+1}\\ x_{i+1,j}= x_{i,j} + j \Delta x_{i+1} \\ x_{i+1,j-1}= x_{i,j} + (j-1)\Delta x_{i+1} \end{cases}$

with $$\Delta x_{i+1} = V_i \sqrt{3}$$ and $$x_{0,0}=X_0$$.

The result of this construction is a symmetric tree around $$X_0$$.

#### Trinomial tree with boundaries conditions

We suppose that the conditional law of the process at time $$i$$ depends only on $$i$$. Then if we set two levels $$0<a<b<1$$, at each time step $$i$$ we can compute the inferior and the superior quantile $$Q_{min}^i$$ and $$Q_{max}^i$$, such that $\mathbb{P}(X_{t_i}<Q_{min}^i)=a \quad \text{and} \quad \mathbb{P}(X_{t_i}<Q_{max}^i)=b.$

Starting from $$x_{i,j}$$, we proceed at the tree construction depending on whether we passed or not the quantiles boundaries at the next step:

• If $$j\Delta x_{i+1} > Q_{max}^{i+1}$$, the process can go straight or twice down as follows :

$\begin{cases} x_{i+1,j}= x_{i,j} + j\Delta x_{i+1}\\ x_{i+1,j-1}= x_{i,j} + (j-1) \Delta x_{i+1} \\ x_{i+1,j-2}= x_{i,j} + (j-2)\Delta x_{i+1} \end{cases}$

• If $$j\Delta x_{i+1} < Q_{min}^{i+1}$$, the process can go straight or twice up as follows :

$\begin{cases} x_{i+1,j}= x_{i,j} + j\Delta x_{i+1}\\ x_{i+1,j+1}= x_{i,j} + (j+1) \Delta x_{i+1} \\ x_{i+1,j+2}= x_{i,j} + (j+2)\Delta x_{i+1} \end{cases}$

• Otherwise, the tree follows a basic evolution

$\begin{cases} x_{i+1,j+1}= x_{i,j} + (j+1)\Delta x_{i+1}\\ x_{i+1,j}= x_{i,j} + j \Delta x_{i+1} \\ x_{i+1,j-1}= x_{i,j} + (j-1)\Delta x_{i+1} \end{cases}$

with $$\Delta x_{i+1} = V_i \sqrt{3}$$.

#### Trinomial tree with Hull-White method

We state that starting from $$x_{i,j}$$ we can reach the positions

$\begin{cases} x_{i+1,k+1}=(k+1)\Delta x_{i+1} \quad \text{with probability} \quad p_u, \\ x_{i+1,k}=k\Delta x_{i+1} \quad \text{with probability} \quad p_m, \\ x_{i+1,k-1}=(k-1)\Delta x_{i+1} \quad \text{with probability} \quad p_d. \end{cases}$

We compute the conditional mean and the conditional variance of the process,

$\mathbb{E} ( X(t_{i+1} ) | X(t_{i}) = x_{i,j} ) = M_{i,j},$ $\mathbb{V} ( X(t_{i+1} ) | X(t_{i}) = x_{i,j} ) = V_{i,j}^2.$

We search for $$p_u$$, $$p_m$$ and $$p_d$$ such that the conditional mean and the conditional variance match those in the tree.

We notice that

\begin{aligned} x_{i+1,k+1} &= x_{i+1,k} + \Delta x_{i+1},\\ x_{i+1,k-1} &= x_{i+1,k} - \Delta x_{i+1}. \end{aligned}

Then we can write

\begin{aligned} p_u( x_{i+1,k} + \Delta x_{i+1} ) + p_m x_{i+1,k} +p_d (x_{i+1,k} - \Delta x_{i+1}) &= M_{i,j}, \\ p_u( x_{i+1,k} + \Delta x_{i+1} )^2 + p_m x_{i+1,k}^2 +p_d (x_{i+1,k} - \Delta x_{i+1})^2 &= V_{i,j}^2 + M_{i,j}^2, \end{aligned}

which brings us to

\begin{aligned} x_{i+1,k} + (p_u + p_d) \Delta x_{i+1} &= M_{i,j},\\ x_{i+1,k}^2 + 2x_{i+1,k} \Delta x_{i+1} (p_u-p_d) + \Delta x_{i+1}^2 (p_u + p_d ) &= V_{i,j}^2 + M_{i,j}^2. \end{aligned}

Setting $$\eta_{j,k} = M_{i,j} - x_{i+1,k}$$, we can write

\begin{aligned} (p_u + p_d) \Delta x_{i+1} &= \eta_{j,k}, \\ (p_u + p_d ) \Delta x_{i+1}^2 &= V_{i,j}^2 + \eta_{j,k}^2 \end{aligned}

and remembering that $$p_m = 1- p_u -p_d$$, we obtain

\begin{aligned} p_u &= \frac{V_{i,j}^2}{2 \Delta x_{i+1}^2}+ \frac{\eta_{j,k}^2}{2 \Delta x_{i+1}^2} + \frac{\eta_{j,k}}{2 \Delta x_{i+1}},\\ p_m &= 1 - \frac{V_{i,j}^2}{\Delta x_{i+1}^2} - \frac{\eta_{j,k}^2}{\Delta x_{i+1}^2},\\ p_d &= \frac{V_{i,j}^2}{2 \Delta x_{i+1}^2}+ \frac{\eta_{j,k}^2}{2 \Delta x_{i+1}^2} - \frac{\eta_{j,k}}{2 \Delta x_{i+1}}. \end{aligned}

We take advantage of the available degrees of freedom, in order to obtain quantities that are always positive. For that, we assume that $$V_{i,j}$$ is independent of $$j$$. From now on we write $$V_i$$ instead of $$V_{i,j}$$. We set $$\Delta x_{i+1} = V_i \sqrt{3}$$, we choose the level $$k$$ and $$\eta_{j,k}$$ in such a way that $$x_{i+1,k}$$ is as close as possible to $$M_{i,j}$$ : $k = round\left( \frac{M_{i,j}}{\Delta x_{i+1}}\right),$ where $$round(x)$$ is the closest integer to the real number $$x$$.

Finally we get : \begin{aligned} p_u &= \frac{1}{6}+ \frac{\eta_{j,k}^2}{6 V_{i}^2} + \frac{\eta_{j,k}}{2 V_i \sqrt{3}}, \\ p_m &= \frac{1}{2} - \frac{\eta_{j,k}^2}{3 V_i^2}, \\ p_u &= \frac{1}{6}+ \frac{\eta_{j,k}^2}{6 V_{i}^2} - \frac{\eta_{j,k}}{2 V_i \sqrt{3}}. \end{aligned}

## The Vasicek model

A short rate $$r(t)$$ is an interest rate at which an entity can borrow money for an infinitesimally short period at time $$t$$.

Vasicek (1977) assumed that the short rate $$r_t$$ follows an Ornstein-Uhlenbeck process with constant coefficients under the risk-neutral measure : $dr_t = k(\theta - r_t ) dt + \sigma dW_t$ where $$r_0=r(0)$$, $$k$$, $$\theta$$ and $$\sigma$$ are positive constants. The conditional mean and the variance of $$r_t$$ are given by $\mathbb{E} (r_t | \mathcal{F}_s ) = r_s e^{-k(t-s)} + \theta (1 - e^{-k(t-s)} ),$ $\mathbb{V} (r_t | \mathcal{F}_s ) = \frac{\sigma^2}{2k} ( 1 - e^{-2k(t-s)} ).$

### Standard construction of trinomial tree

#### Basic Tree

We build the basic tree for the Vasicek model with : $\Delta r = V \sqrt{3}$ and $V=\sqrt{ \frac{\sigma^2}{2k}(1-e^{-2k\Delta t}) }.$

#### Tree with boundaries conditions

We notice that $$r_t$$ follows a normal distribution with mean and variance given by

$\mathbb{E} ( r_t )= r_{0}e^{-kt} + \theta (1 - e^{-kt} ),$ $\mathbb{V} ( r_t ) = \sqrt{ \frac{\sigma^2}{2k}(1-e^{-2kt}) }.$

We will fix two boundaries $$0<a<b<1$$ and at each time step we will compute the two quantiles $$Q_{min}^i$$ and $$Q_{max}^i$$ such that

$\mathbb{P}(r_{t_i}<Q_{min}^i)=a \quad \text{and} \quad \mathbb{P}(r_{t_i}<Q_{max}^i)=b.$

#### Tree with Hull-White method

The equivalence of the conditional mean and variance, and the additional conditions bring us to

\begin{aligned} p_u &= \frac{1}{6}+ \frac{\eta_{j,k}^2}{6 V^2} + \frac{\eta_{j,k}}{2 V \sqrt{3}},\\ p_m &= \frac{1}{2} - \frac{\eta_{j,k}^2}{3 V^2},\\ p_u &= \frac{1}{6}+ \frac{\eta_{j,k}^2}{6 V^2} - \frac{\eta_{j,k}}{2 V \sqrt{3}}, \end{aligned} with $M_{i,j}= r_{i,j}e^{-k\Delta t_i} + \theta (1 - e^{-k\Delta t} ),$ $V^2 = \frac{\sigma^2}{2k}(1-e^{-2k\Delta t})$ and $$r_{i,j} = j\Delta r$$, where $$\Delta r := V \sqrt{3}$$ and $$\eta_{j,k} = M_{i,j} - r_{i+1,k}$$.

### Alternative construction of trinomial tree

We consider the process $y_t = e^{k t}(r_t - \theta)$

where $$r_t$$ follows a Vasicek model.

By Ito's formula, we get $dy_t = \sigma e^{k t }dW_t.$

The conditional mean and variance are then

$\mathbb{E} ( y_t ) | \mathcal{F}_s ) = y_{s},$ $\mathbb{V} ( y_t ) | \mathcal{F}_s ) = \frac{\sigma^2}{2k}(e^{2kt}-e^{2ks}).$

In the graphs, we represent both the trees for $$y_t$$ and for $$r_t$$.

#### Basic Tree

We build the basic tree for the process $$y_t$$ with $\Delta y_{i} = V_i \sqrt{3}$ and $V_i=\sqrt{ \frac{\sigma^2}{2k}(e^{2 k t_{i}}-e^{2 k t_{i-1}}) }.$ Once we build the tree for $$y_t$$, we multiply the nodes $$y_{i,j}$$ by $$e^{-k i \Delta t}$$ and we add $$\theta$$ in order to obtain $$r_t$$.

#### Tree with boundaries conditions

We notice that $$y_t$$ follows a normal distribution with $\mathbb{E} ( y_t )= y_{0},$ $\mathbb{V} ( y_t ) = \sqrt{ \frac{\sigma^2}{2k}( e^{2 k t} - 1 ) }.$

As we did for the standard construction, at each time step we constrain the process $$y_t$$ to stay between two choosen quantiles.

Once we build the tree for $$y_t$$, we make the computations to transform it in the tree for $$r_t$$.

#### Tree with the Hull-White method

The equivalence of the conditional mean and variance and the other conditions that we saw in the general framework, applied to the process $$y_t$$, bring us to \begin{aligned} p_u &= \frac{1}{6}+ \frac{\eta_{j,k}^2}{6 V_{i}^2} + \frac{\eta_{j,k}}{2 V_i \sqrt{3}},\\ p_m &= \frac{1}{2} - \frac{\eta_{j,k}^2}{3 V_i^2},\\ p_u &= \frac{1}{6}+ \frac{\eta_{j,k}^2}{6 V_{i}^2} - \frac{\eta_{j,k}}{2 V_i \sqrt{3}}, \end{aligned} with $M_{i,j}= y_{i,j},$ $V_{i}^2 = \frac{\sigma^2}{2k}(e^{2 k t_{i}}-e^{2 k t_{i-1}}),$ $y_{i,j} = j\Delta y_i,$ where $$\Delta y_i := V_i \sqrt{3}$$ and $$\eta_{j,k} = M_{i,j} - y_{i+1,k}$$.

Once the tree build for $$y_t$$, we can build the one for $$r_t$$.