2
$\begingroup$

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.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
3
$\begingroup$

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$.

Improve this answer
$\endgroup$
7
  • $\begingroup$ You can also generate intermediate stock prices between S(0) and S(1). For instance, if you want to have S(0), S(1/2), S(1), then generate random numbers -> use these to calculate S(1/2). Then generate new random numbers and use your S(1/2) stock prices and new random numbers to calculate S(1) prices. $\endgroup$
    – nathanesau
    Jul 5, 2015 at 22:29
  • $\begingroup$ Nathanesau, by random numbers for intermediate stock prices you mean the numbers from the Haltorn sequence right? When running these calculation all your numbers for generating the different stock paths are coming from the same base numbers, right? What I understand now so far is that you only use another base if you have more dimensions, so if you have a basket of 3 stock then you will use 3 different bases to generate halton numbers. So using an unique base per stock/dimension to generate the asset paths? $\endgroup$
    – Oamriotn
    Jul 6, 2015 at 6:09
  • $\begingroup$ Thanks Nathanesau. So this means that you use another base for every intermediate step. My final question is: What do you do when you have more dimensions, say you have a basket with 3 different stock. Next to that do you get any troubles when using really high base numbers. For example when you ujse a base of 1999 you get really "strange" Halton numbers (looks like a linear line from zero to one), which I see from all high base numbers! $\endgroup$
    – Oamriotn
    Jul 8, 2015 at 15:10
  • $\begingroup$ For 3 different stock, use different bases for each path, for each stock. For instance S, Q, M are three stocks. Then to get S(1/2), S(1), Q(1/2), Q(1), M(1/2), M(1) you need to generate 6 different set of numbers. However, after you have generated a large number of sequences, you could start re-using the bases. For instance, use bases 2,3, 5, ... 514, then use base 2 again. For base 514, first numbers will be 1/514, 2/514, ... 513/514. If you only take the first 10 numbers of this sequence then you stock prices will be too low. In this case either use 513 numbers or shuffle and take first 10 $\endgroup$
    – nathanesau
    Jul 8, 2015 at 15:52
  • $\begingroup$ Halton generates from a uniform distribution. Therefore linear line from zero to one is what you would expect. $\endgroup$
    – nathanesau
    Jul 8, 2015 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.