random variables - How to use Halton sequence in monte carlo simulation

Does anybody know how to use the Halton pseudo random technique in monte carlo simulation. I'm able to generate the sequences and I know they are correct. I checked a couple of numbers from different sequences. But how do I use these numbers when I want to generate a path? Do I only use one base number and use this vector for generating asset paths? For different paths I wouldn't use the same numbers but I won't change the base, or do I need the change the base?

Hopefully somebody can explain me this.

Answer

First I provide a brief description of Halton sequences. A Halton sequence is a deterministic sequence of numbers that provides well-spaced 'draws' from an interval and provides negative correlation between simulated probability for individuals.

• Generation is based on a prime number


• Sequence is constructed based on finer and finer prime-based divisions of sub-intervals of unit interval

Example

• 
  

  prime = 3

  
  


• 
  

  0, 1/3, 2/3, 3/3

  
  
  
  
  • 1/3, 2/3 (length is 3^1 - 1)
  
  
  
  


• 0, 1/9, 2/9, 3/9, 4/9, 5/9, 6/9, 7/9, 8/9, 9/9
  
  
  
  
  • 3/9, 6/9, 1/9, 4/9, 7/9, 2/9, 5/9, 8/9 (length is 3^2 - 1)
  
  
  
  


• 0, 1/27, 2/27, 3/27, 4/27, 5/27, 6/27, 7/27, 8/27, 9/27, 10/27, 11/27, 12/27, 13/27, 14/27, 15/27, 16/27, 17/27, 18/27, 19/27, 20/27, 21/27, 22/27, 23/27, 24/27, 25/27, 26/27, 27/27
  
  
  
  • 3/9, 6/9, 1/9, 4/9, 7/9, 2/9, 5/9, 8/9, 1/27, 10/27, 19/27, 4/27, 13/27, 22/27, 2/27, 7/27, 16/27, 25/27, 2/27, 11/27, 20/27, 5/27, 14/27, 23/27, 8/27, 17/27, 26/27 (length is 3^3 - 1)
  
  
  
  

A quick explanation for this long sequence.

• 0, 1/27 [9], 2/27 [18]


• 9/27 [1], 10/27 [10], 11/24 [19]


• 18/27 [2], 19/27 [11], 20/27 [20]


• 3/27 [3], 4/27 [12], 5/27 [21]


• 12/27 [4], 13/24 [13], 14/27 [22]


• 21/27 [5], 22/27 [14], 23/27 [23]


• 6/27 [6], 7/27 [15], 8/27 [24]


• 15/27 [7], 16/27 [16], 17/27 [25]



• 24/27 [8], 25/27 [17], 26/27 [26]

Hopefully the pattern is clear. Now, let's say that I take the sequence of length 8,

3/9, 6/9, 1/9, 4/9, 7/9, 2/9, 5/9, 8/9.

I want to find the value of a European call option with payoff at time $t$ of $max(0, S(t) - K)$ where $K$ is the strike price and $S(t)$ is the stock price at $t$. Let's say that the risk neutral process for the stock is

$$dS(t)/S(t) = (r-\delta)dt + \sigma \tilde{dZ}(t)$$

where $dZ(t) = \phi dt + dZ(t)$. Then $d\ln(S(t)) = (r - \delta - 0.5\sigma^2) dt + \sigma \tilde{dZ(t)}$ so that $\ln(S(t)/S(0)) \sim N(m = (r-\delta - 0.5\sigma^2)t, v = \sigma \sqrt{t})$ where $\delta$ is the continuously compounded dividend rate on the stock, $r$ is the risk-free interest rate and $\sigma$ is the volatility.

First we can use the inversion method to transform the uniform number into random normal numbers. The first number would be $N^{-1}(1/3)$ = -0.43. This is the quantile function of the standard normal distribution with $N(-0.43) = 1/3$. The transformed standard normal numbers are -0.43, 0.43, -1.22, -0.139, 0.765, -0.765, 0.139, 1.22. Denote a standard normal number by $z_j$. Then a normal random number from our distribution, $n_j = v z_j + m_j$.

Let's assume that $\sigma = 0.3$, $r = 0.05$, $\delta = 0$ and $t=1$ is the time to expiration. Then $m = (0.05 - 0 - 0.5*0.3^2) = 0.005$ and $v = 0.30$. The first transformed normal number is $0.30 (-0.43) + 0.005 = -0.124$. The list of numbers is

• -0.124, 0.134, -0.361, -0.0369, 0.234, -0.2244, 0.0469, 0.3712

Then we take $x_j = exp(n_j)$ to get the log-normal random numbers. The first log-normal random number is $exp(-0.124) = 0.883$. The list of numbers i

• 0.883, 1.14, 0.697, 0.964, 1.264, 0.80, 1.048, 1.45.

Let's say that the initial stock price is $S(0) = 40$. Then the stock prices at expiration, $S(1) = S(0) x_j$. The first stock price is 40 * 0.883 = 35.33. The list of stock prices are shown, following by the payoffs with $K=40$ for a European call.

• S(1): 35.33, 45.75, 27.87, 38.55, 50.57, 31.96, 41.92, 57.98


• Payoff(1): 0, 5.75, 0, 0, 10.57, 0, 1.92, 17.98

The average payoff is 3.286. The time 0 estimated price of the option is $C = exp(-0.05) 3.286 = 4.53$. The Black-Scholes price of the option is 5.692502. If we use 26 numbers, our price becomes 4.89.

EDIT 1

I will provide an example of what I mean by intermediate price - I will use the Halton sequence above to estimate the price of a Geometric Average Price Call with $K=40$. Note that there is a closed form Black Scholes formula for this option shown here.

$u$ = 3/9, 6/9, 1/9, 4/9, 7/9, 2/9, 5/9, 8/9

$z$ = -0.43, 0.43, -1.22, -0.1397, 0.765, -0.765, 0.1397, 1.22

$n$ = 0.089, 0.094, -0.2564, -0.027, 0.165, -0.160, 0.032, 0.2614

$x$ = 0.915, 1.10, 0.774, 0.973, 1.18, 0.852, 1.03, 1.30

$S_{1/2}$ = 36.60, 43.94, 30.95, 38.93, 47.16, 34.09, 41.31, 51.95

Let's now use a different set of Halton numbers (with prime = 2). The sequence is 1/2, 1/4, 3/4, 1/8, 5/8, 3/8, 7/8, 1/16, 9/16, 5/16, ... but we only want the first 8 numbers. Note that the stock price $36.69 = 36.60 * 1.0025$

$u$ = 1/2, 1/4, 3/4, 1/8, 5/8, 3/8, 7/8, 1/16

$z$ = 0.00, -0.674, 0.674, -0.115, 0.3189, -0.3189, 1.15, -1.534

$n$ = 0.0025, -0.1405, 0.1455, -0.2415, 0.070, -0.0651, 0.2465, -0.3229

$x$ = 1.0025, 0.8689, 1.16, 0.785, 1.072, 0.9370, 1.28, 0.724

$S_{1}$ = 36.69, 38.17, 35.80, 30.58, 50.59, 31.95, 52.86, 37.61

The geometric averages are $( S_{1/2} S_{1} )^{1/2}$. For instance, $36.64 = (36.60 * 36.69)^{0.5}$

$G$ = 36.64, 40.95, 33.289, 34.50, 48.845, 33.00, 46.73, 44.21

The value of the option for each of these averages is shown below. Note that $max(0, 36.64 - 40) = 0$ and $max(0, 40.954 - 40) = 0.95433$.

$V$ = 0.00, 0.954, 0.00, 0.00, 8.85, 0.00, 6.73, 4.21

The option price is estimated to be $\overline{V} e^{-r (1)} = 2.59 e^{-0.05} = 2.47$.