5.1 Binomial Processes

One of the simplest stochastic processes is an ordinary random walk, a process whose increments $Z_t = X_t - X_{t-1}$ from time $t-1$ to time $t$ take exclusively the values +1 or -1. Additionally, we assume the increments to be i.i.d. and independent of the starting value $X_0$. Hence, the ordinary random walk can be written as:

$$X_t = X_0 + \sum^t_{k=1} \, Z_k \qquad , \, \, t = 1, 2, \ldots$$ (5.1)

$X_0, Z_1, Z_2, \ldots$ independent and

$$\P(Z_k = 1) = p \quad , \quad \P(Z_k = - 1) = 1 - p$$   for all $$\, k \, .$$

Letting the process go up by $u$ and go down by $d$, instead, we obtain a more general class of binomial processes:

$$\P(Z_k = u) = p \, , \quad \P(Z_k = - d) = 1 - p$$   für alle $$\, \, k \, ,$$

where $u$ and $d$ are constant ($u$=up, $d$=down).

Linear interpolation of the points $(t, X_t)$ reflects the time evolution of the process and is called a path of an ordinary random walk. Starting in $X_0=a$, the process moves on the grid of points $(t, b_t), \, \, t = 0,1,2,\ldots, \, \, b_t = a - t,\ a-t+1, \ldots, \, a + t .$ Up to time $t$, $X_t$ can grow at most up to $a+t$ (if $Z_1 = \ldots = Z_t = 1$) or can fall at least to $a-t$ (if $Z_1 = \ldots = Z_t = -1$). Three paths of an ordinary random walk are shown in Figure 4.1 ($p=0.5$), 4.2 ($p=0.4$) and Figure 4.3 ($p=0.6$).

Fig.: Three paths of a symmetric ordinary random walk. ($2\sigma$)-intervals around the drift (which is zero) are given as well. SFEBinomp.xpl

Fig.: Three paths of an ordinary random walk with $p=0.4$. ($2\sigma$)-intervals around the drift (which is the line with negative slope) are given as well. SFEBinomp.xpl

Fig.: Three paths of an ordinary random walk with $p=0.6$. ($2\sigma$)-intervals around the drift (which is the line with positive slope) are given as well. SFEBinomp.xpl

For generalized binomial processes the grid of possible paths is more complicated. The values which the process $X_t$ starting in $a$ can possibly take up to time $t$ are given by

$$b_t = a + n \cdot u - m \cdot d \, , \, \,$$   where $$\, n, m \ge 0 \, , \quad n + m = t \, .$$

If, from time 0 to time $t$, the process goes up $n$ times and goes down $m$ times then $X_t = a + n \cdot u - m \cdot d .$ That is, $n$ of $t$ increments $Z_1, \ldots, Z_t$ take the value $u$, and $m$ increments take the value $-d$. The grid of possible paths is also called a binomial tree.

The mean of the symmetric ordinary random walk $(p = \frac{1}{2})$ starting in 0 ($X_0 = 0$) is for all times $t$ equal to 0 :

$$\mathop{\text{\rm\sf E}}[X_t] = 0 \qquad \text{\rm for\ all\ } \, t\ .$$

Otherwise, the random walk has a trend or drift, for $( p > \frac{1}{2})$ it has a positive drift and for $( p < \frac{1}{2})$ it has a negative drift. The process grows or falls in average:

$$\mathop{\text{\rm\sf E}}[X_t] = t \cdot (2p-1) \, ,$$

since it holds for all increments $\mathop{\text{\rm\sf E}}[Z_k] = 2p-1 \, .$ Hence, the trend is linear in time. It is the upward sloping line in Figure 4.3 ($p=0.6$) and the downward sloping line in Figure 4.2 ($p=0.6$).

For the generalized binomial process with general starting value $X_0$ it holds analogously $\mathop{\text{\rm\sf E}}[Z_k] = (u + d) p - d$ and thus:

$$\mathop{\text{\rm\sf E}}[X_t] = \mathop{\text{\rm\sf E}}[X_0] + t \cdot \{(u + d) p - d \} \, .$$

As time evolves the set of values $X_t$ grows, and its variability increases. Since the summands in (4.1) are independent and $\mathop{\text{\rm Var}}(Z_k) = \mathop{\text{\rm Var}}(Z_1)$ for all $k$, the variance of $X_t$ is given by (refer to Section 3.4):

$$\mathop{\text{\rm Var}}(X_t) = \mathop{\text{\rm Var}}(X_0) + t \cdot \mathop{\text{\rm Var}}(Z_1) \, .$$

Hence, the variance of $X_t$ grows linearly with time. So does the standard deviation. For the random walks depicted in Figure 4.1 ($p=0.5$), Figure 4.2 ($p=0.4$) and Figure 4.3 ($p=0.6$) the intervals $[\mathop{\text{\rm\sf E}}[X_t] - 2\sigma(X_t); \mathop{\text{\rm\sf E}}[X_t] + 2\sigma(X_t)]$ are shown as well. For large $t$ , these intervals should contain 95% of the realizations of processes.

The variance of the increments can be easily computed. We use the following result which holds for the binomial distribution. Define

$$Y_k = \frac{Z_k + d}{u +d} \, = \ \left\{ \begin{array}{ll}1 \qua... ...t{\rm if\ } \, Z_k = u\\ 0 & \text{\rm if\ } \, Z_k = - d \end{array} \right.$$

or

$$Z_k = (u + d) \, Y_k - d$$ (5.2)

we obtain the following representation of the binomial process

$$X_t = X_0 + (u + d) \, B_t - td$$ (5.3)

where

$$B_t = \sum^t_{k=1} \, Y_k$$ (5.4)

is a $B (t,p)$ distributed random variable.

Given the distribution of $X_0$, the distribution of $X_t$ is specified for all $t$. It can be derived by means of a simple transformation of the binomial distribution $B (t,p)$. From equations (4.2) to (4.4) we obtain for $X_0 = 0$:

$$\mathop{\text{\rm Var}}(X_t) = t (u + d)^2 \, p(1-p)$$

and for large $t$ the distribution of $X_t$ can be approximated by:

$${\cal L}(X_t) \approx N (t \{ (u+d) p-d \}, \, t (u+d)^2 \, p(1-p)).$$

For $p = \frac{1}{2} , u = d = \Delta x$, the following approximation holds for ${\cal L}(X_t)$:

$$N (0,t \cdot (\Delta x )^2).$$

Figure 4.4 shows the fit for $t=100$.

Fig.: The distribution of 100 paths of an ordinary symmetric random walk of length $100$ and a kernel density estimation of 100 normally distributed random variables. SFEbinomv.xpl